Optimization over Sphere with disequalities

[Sirio Belga Fedeli]

Hi,

I have a question (sorry I'm completely new in the field), I m studying the following problem (x\inR^N):

min_{x\inS} H(x)

S:={ |x|^2=N, Ax<b}

where A is a MxN matrix and b is a Mx1 column vector. Has this manifold been developed? 

Best regards,
Sirio

[Nicolas Boumal]

Hello Sirio,

You can readily optimize over a sphere of radius one with spherefactory. In your case, if you scale your vector x by sqrt(N), this should allow you to handle the first part.

For the inequality constraints, we do not currently have code for this. My suggestion would be to try an augmented Lagrangian approach, where the inequalities would be replaced with penalty terms in the cost function with some weights, and the weights would be adapted iteratively.

If you try this approach, I would be interested in hearing how it goes.

Best wishes,

Nicolas

[Sirio Belga Fedeli]

Hi Nicola,

Sorry for disturbing again, I have finally found time to follow your suggestion for 

min_{x\inS}-1/2*x^T*Hx

S:={ |x|^2=1, Ax<0}

problem.cost  = @(x) -1/2*x'*(H*x)+c*P(A*x);
problem.egrad = @(x) -H*x+c*grad_x P(A*x);

Where H and A are NxN(Sym) and MxN matrices (H\in GOE and A real ginibre). The problem I encounter is the choice of the penalty c. I have tried several approaches from literature, nevertheless, the number of satisfied constraints is about M/2.

I presume is a problem of scaling?

Could you please suggest or have you in mind a way to update c?

 

Thank you a lot and sorry again for disturbing!

Sirio

[Sirio Belga Fedeli]

Sorry, Nicolas!

[Nicolas Boumal]

Hello Sirio,

For augmented Lagrangian approaches to deal with inequalities on manifolds, you can have a look at this paper, which also has code available on a public git repository: https://arxiv.org/abs/1901.10000 

Best of luck!

Nicolas