lrsdp_test.cpp File Reference

#include <mlpack/core.hpp>
#include <mlpack/core/optimizers/sdp/lrsdp.hpp>
#include "test_tools.hpp"

Include dependency graph for lrsdp_test.cpp:

Functions
	BOOST_AUTO_TEST_SUITE (LRSDPTest)
void	CreateLovaszThetaInitialPoint (const arma::mat &edges, arma::mat &coordinates)
	Create a Lovasz-Theta initial point.
void	SetupLovaszTheta (const arma::mat &edges, LRSDP< SDP< arma::mat >> &lovasz)
	Prepare an LRSDP object to solve the Lovasz-Theta SDP in the manner detailed in Monteiro + Burer 2004. More...
	BOOST_AUTO_TEST_CASE (Johnson844LovaszThetaSDP)
	johnson8-4-4.co test case for Lovasz-Theta LRSDP. More...
void	CreateSparseGraphLaplacian (const arma::mat &edges, arma::sp_mat &laplacian)
	Create an unweighted graph laplacian from the edges.
	BOOST_AUTO_TEST_CASE (ErdosRenyiRandomGraphMaxCutSDP)
	BOOST_AUTO_TEST_CASE (GaussianMatrixSensingSDP)
	BOOST_AUTO_TEST_SUITE_END ()
	keller4.co test case for Lovasz-Theta LRSDP. More...

Detailed Description

Author

Ryan Curtin

Tests for LR-SDP (core/optimizers/sdp/).

mlpack is free software; you may redistribute it and/or modify it under the terms of the 3-clause BSD license. You should have received a copy of the 3-clause BSD license along with mlpack. If not, see http://www.opensource.org/licenses/BSD-3-Clause for more information.

Function Documentation

BOOST_AUTO_TEST_CASE()

BOOST_AUTO_TEST_CASE

(

Johnson844LovaszThetaSDP

)

johnson8-4-4.co test case for Lovasz-Theta LRSDP.

See Monteiro and Burer 2004.

BOOST_AUTO_TEST_SUITE_END()

BOOST_AUTO_TEST_SUITE_END

(

)

keller4.co test case for Lovasz-Theta LRSDP.

This is commented out because it takes a long time to run. See Monteiro and Burer 2004.

BOOST_AUTO_TEST_CASE(Keller4LovaszThetaSDP) { Load the edges. arma::mat edges; data::Load("keller4.csv", edges, true);

The LRSDP itself and the initial point. arma::mat coordinates;

CreateLovaszThetaInitialPoint(edges, coordinates);

LRSDP<SDP<arma::mat>> lovasz(edges.n_cols, coordinates);

SetupLovaszTheta(edges, lovasz);

double finalValue = lovasz.Optimize(coordinates);

Final value taken from Monteiro + Burer 2004. BOOST_REQUIRE_CLOSE(finalValue, -14.013, 1e-2); // Not as much precision... The SB method came to -14.013, but M&B's method only came to -14.005.

Now ensure that all the constraints are satisfied. arma::mat rrt = coordinates * trans(coordinates); BOOST_REQUIRE_CLOSE(trace(rrt), 1.0, 1e-5);

All those edge constraints... for (size_t i = 0; i < edges.n_cols; ++i) { BOOST_REQUIRE_SMALL(rrt(edges(0, i), edges(1, i)), 1e-3); BOOST_REQUIRE_SMALL(rrt(edges(1, i), edges(0, i)), 1e-3); } }

SetupLovaszTheta()

void SetupLovaszTheta	(	const arma::mat &	edges,
		LRSDP< SDP< arma::mat >> &	lovasz
	)

Prepare an LRSDP object to solve the Lovasz-Theta SDP in the manner detailed in Monteiro + Burer 2004.

The list of edges in the graph must be given; that is all that is necessary to set up the problem. A matrix which will contain initial point coordinates should be given also.