examples/maxcut.m fails

[Yufan Huang]

Dear manopt team,

Thanks for developing such an amazing toolbox! 

I just began exploring solving some graph-related SDPs using manopt. 

I begin with the maxcut.m code in the examples.

However, it didn't converge as expected.

Below is a minimal working example.

function Test_maxcut(graph)

    % maybe need to change the path
    A = load(['~/datasets/graphs/', graph, '.mat']).A;

    A = abs(A);
    n = size(A, 1);
    D = diag(sum(A, 2));
    L = D - A;
    r = ceil(sqrt(8*n+1)/2);  
    [x, cutvalue, cutvalue_upperbound, Y] = maxcut(L, r);
end

and I call Test_maxcut('G1') where G1 is the first graph from Gset. I observed that the smallest eigenvalue of S stays around ~0.01 for a few iterations and becomes NaN starting from rr = 14. I feel a bit confused because this experiment seems almost identical to those in the paper "The non-convex BurerMonteiro approach works on smooth semidefinite programs". Here for my own needs, I make sure all edges have positive weights.

Are there any options I need to change?

Best Regards,

Yufan

[Nicolas Boumal]

Hello Yufan,

Thanks for describing this observation here. A few things:

1) I modified the example file maxcut.m just now (pushed to github). It used to rely on elliptopefactory by default, which is indeed the geometry described in the source paper for that example (by Journée et al., 2010). However, that is a quotient geometry which breaks down when the rank drops. This is problematic since the whole point is to converge to a matrix of lesser rank. The fix is easy (and was included as commented code in the file for a while): replace elliptopefactory by obliquefactory (product of spheres). This geometry doesn't break when the rank drops; it's conceptually simpler; and the computations are the same / slightly simpler.

2) That example is not meant to be particularly efficient (e.g., it increase the rank one by one, whereas it's more efficient to make bigger jumps; also it computes all sorts of extra things for logging etc.). The purpose of that file is more to serve as an example of how to use some of the more sophisticated features of Manopt (including logging special statistics suc has matrix-vector products, and solving a Manopt problem in a loop).

3) After some digging, I found the code that I wrote to run those experiments from the NeurIPS 2016 paper: here they are attached. The "_incremental" version calls the base version in succession for several ranks, jumping by more than 1. That's called "Manopt+" in the paper. Notice that these are using obliquefactory.

4) I didn't see the issue you mentioned about lambdamin(S) hovering at about .01 though. Can you see if the problem persists and post more details if so?

Best,

Nicolas

[Nicolas Boumal]

I made the whole code to reproduce those experiments from the NeurIPS 2016 paper available here:

https://github.com/NicolasBoumal/maxcut/tree/main