mlpack  git-master
LovaszThetaSDP Class Reference

This function is the Lovasz-Theta semidefinite program, as implemented in the following paper: More...

Public Member Functions

 LovaszThetaSDP ()
 
 LovaszThetaSDP (const arma::mat &edges)
 Initialize the Lovasz-Theta SDP with the given set of edges. More...

 
const arma::mat & Edges () const
 
arma::mat & Edges ()
 
double Evaluate (const arma::mat &coordinates)
 
double EvaluateConstraint (const size_t index, const arma::mat &coordinates)
 
const arma::mat & GetInitialPoint ()
 
void Gradient (const arma::mat &coordinates, arma::mat &gradient)
 
void GradientConstraint (const size_t index, const arma::mat &coordinates, arma::mat &gradient)
 
size_t NumConstraints () const
 

Detailed Description

This function is the Lovasz-Theta semidefinite program, as implemented in the following paper:

S. Burer, R. Monteiro "A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization." Journal of Mathematical Programming, 2004

Given a simple, undirected graph G = (V, E), the Lovasz-Theta SDP is defined by:

min_X{Tr(-(e e^T)^T X) : Tr(X) = 1, X_ij = 0 for all (i, j) in E, X >= 0}

where e is the vector of all ones and X has dimension |V| x |V|.

In the Monteiro-Burer formulation, we take X = R * R^T, where R is the coordinates given to the Evaluate(), Gradient(), EvaluateConstraint(), and GradientConstraint() functions.

Definition at line 103 of file aug_lagrangian_test_functions.hpp.

Constructor & Destructor Documentation

◆ LovaszThetaSDP() [1/2]

◆ LovaszThetaSDP() [2/2]

LovaszThetaSDP ( const arma::mat &  edges)

Initialize the Lovasz-Theta SDP with the given set of edges.

The edge matrix should consist of rows of two dimensions, where dimension 0 is the first vertex of the edge and dimension 1 is the second edge (or vice versa, as it doesn't make a difference).

Parameters
edgesMatrix of edges.

Member Function Documentation

◆ Edges() [1/2]

const arma::mat& Edges ( ) const
inline

Definition at line 130 of file aug_lagrangian_test_functions.hpp.

◆ Edges() [2/2]

arma::mat& Edges ( )
inline

Definition at line 131 of file aug_lagrangian_test_functions.hpp.

◆ Evaluate()

double Evaluate ( const arma::mat &  coordinates)

◆ EvaluateConstraint()

double EvaluateConstraint ( const size_t  index,
const arma::mat &  coordinates 
)

◆ GetInitialPoint()

const arma::mat& GetInitialPoint ( )

◆ Gradient()

void Gradient ( const arma::mat &  coordinates,
arma::mat &  gradient 
)

◆ GradientConstraint()

void GradientConstraint ( const size_t  index,
const arma::mat &  coordinates,
arma::mat &  gradient 
)

◆ NumConstraints()

size_t NumConstraints ( ) const

The documentation for this class was generated from the following file: