About the checkgradient function

[seu...@gmail.com]

Hello,

I came across a question on the checkgradient function. I wonder whether the outcome of the function depends on the manifold since I obtained different outcomes when I apply the same cost function and Euclidean gradient to different manifolds.
For example, when I write my codes as follows:

manifold = complexcirclefactory(10);
problem.M = manifold;
problem.cost = @(x) x'*W*x;
problem.egrad = @(x) 2*W*x;
checkgradient(problem);

where W is a 10 by 10 symmetric matrix, the checkgradient function tells me I am correct. However, when I do it with

manifold = elliptopefactory(10,1);

the outcome will be totally different. I would appreciate it if you could tell me why on this. Thank you very much.

Alex

[Nicolas Boumal]

Hello Alex,

Short answer: no, the result of checkgradient should not depend on the manifold you use (if egrad is specified rather than grad, as is your case), but there is a catch here:

You may want to try with the complex oblique factory instead of elliptopefactory:

https://www.manopt.org/reference/manopt/manifolds/oblique/obliquecomplexfactory.html

The reason is that the elliptopefactory works with real numbers, not complex numbers. As a result, when you call it with (10, 1) as input, points on the manifold are represented as vectors of length 10 whose rows (actually, entries) have unit 2-norm (hence, are equal to +1 or -1). This is a discrete set of points (all vectors of \pm 1), which is a manifold of dimension 0. That's kind of a corner case which is not handled.

The complex oblique factory should solve your problem.

This example from Manopt 3.0 will surely help, as it is even the same cost function as yours:

https://www.manopt.org/reference/examples/elliptope_SDP_complex.html

Best,

Nicolas

[seu...@gmail.com]

Hi Nicolas,

Thank you for your reply. I understand your explanation for my question. As you said, I am exactly handling a problem whose variable is a vector, and each entry is either +1 or -1. So does it mean elliptopefactory cannot handle it, or I can use the real Oblique manifold?

Thank you.

Alex

[Nicolas Boumal]

Hello Alex,

You will want to relax your set of {+1, -1} vectors (exponential number of disconnected elements) to something connected and smooth. In manopt, the traditional way to do this amounts to working on "manifold = elliptopefactory(10,p);" or on the real oblique manifold, also of size 10 x p, where p >= 2. Of course, this will generate a solution which is not a vector of +-1, so at the end you'll need to "round".

This paper of mine with collaborators may be helpful:

"The non-convex Burer-Monteiro approach works on smooth semidefinite programs"

https://arxiv.org/abs/1606.04970

Relevant example code in Manopt 3.0:

https://manopt.org/reference/examples/elliptope_SDP.html  % real case, but notice how the number of columns is taken larger than 1 ; actually works with oblique factory, which I recommend.

https://manopt.org/reference/examples/maxcut.html % also real, specialized to max-cut, includes rounding and works with elliptope factory

Best,

Nicolas

[seu...@gmail.com]

Thanks a lot!

[Shayan zargari]

Dear Nicolas,

I have a SDP problem which is given by: 

max trace(RV)  

s.t.    diag(V)=1;

          rank(V)=1;

          V>=0;

when I use elliptopefactory(n, k), I will get a wrong solution. I would really appreciate it if you could help me with that.

[Shayan zargari]

I forgot to mentioned that all variables are complex.

[Nicolas Boumal]

Hello Shayan, 

Can you show your code here? 

Nicolas

[Shayan zargari]

Hi Nicolas,

Thank you very much for your prompt reply. It is equation 4 of the following paper.

https://arxiv.org/abs/1904.12199

[Nicolas Boumal]

Can you also show your code?

If you need complex variables elliptopefactory is not appropriate. I recommend you try obliquecomplexfactory, here: https://www.manopt.org/reference/manopt/manifolds/oblique/obliquecomplexfactory.html

[Shayan zargari]

Thank you so much.