Penalty (weight) parameter

[Behnam M]

Hi There,
I skimmed through the paper suggested as for "optimization on manifolds with constraints", however, I was wondering if there is an implemented example of imposing penalty parameter (i.e. constraint 0<=  w_i  <=1) to each residual in the cost function? 
Does any of the built-in factories serve for this type of parameter?

Cheers,

[Nicolas Boumal]

Dear Behnam,

I do not understand the question. Can you provide more context?

Best,

Nicolas

[Behnam M]

Hi Nicolas,

Amending the previous message: the question is about constrained optimization and the simplified real-valued objective function is as below:

where p and q are 3D points. 
Indeed this problem should be copied K times, that is, we want to find K transformations (T) for K 3D points (p) to minimize their distance (after transformation) to the corresponding points (q). Here, the contribution of some residuals should be controlled using the weight (penalty) "w" as some of "p"s have a poor corresponding one in q. So we're dealing with SE(3)^K and  K-element  "w" per residual so we have T( : , : , i) and w( i ) where i=1:K.

The way I constructed the problem (except for the suitable factory for "w") in MATLAB is:

%%
M.R=rotationsfactory(3,K);
M.t=euclideanfactory(3,K);
M.w=???(1,K);
manifold = productmanifold(M);
problem.M=manifold;
problem.cost = @(x) CostFunction(x, p, q,K);
%%

Given "w", the penalty coefficient per residual, I am wondering how I can constrain w to [0 1] in the problem construction (or should I handle it mathematically somehow inside the CostFunction)?

Cheers,

[Nicolas Boumal]

Dear Benham,

If w is a variable in the optimization problem, then it is optimal to set w = 0. This is probably not the goal.

It seems to me that the variables of your optimization problem are only the SE(3) elements (K of them). In contrast, w is a parameter for the cost function. You can set it before defining your cost function (and it's up to you to make sure it's in [0, 1]). No need for a factory for it.

In your current presentation, it appears that the optimization problem is separable across the K repetitions: you mat be better off solving K problems with a single SE(3) each, instead of solving for the K elements simultaneously. But maybe there are other ingredients in your cost function / constraints that link the K copies together.

An additional note still about the particular cost function you displayed here for a single SE(3): I'd expect that this problem has an (in fact, many) explicit solution in closed form. But again, maybe this is because you simplified the cost function here to ask your question.

Best,

Nicolas

[Behnam M]

Dear Nicholas,
Thanks for the reply. Yes, the objective function presented here is so simple and is just a toy example to test how I can construct a constrained optimization and the transformations are actually tied together so that they should be solved altogether and the closed-form solution is not applicable in the real problem.
The weights w should be optimized in the minimization process as we don't know the contribution of residuals in advance. To summarize my question: I was wondering how I can constrain the values of w in the search for the optimal values. Is there any example of constrained optimization by MANOPT?
Best regards,

[Nicolas Boumal]

Hello again Behnam,

There are no examples in the examples/ folder, unfortunately.

One way is to implement a kind of augmented Lagrangian method to enforce your constraints. That's described in one of the papers you were referring to: https://arxiv.org/abs/1901.10000. There is open source code for that paper, using manopt, here: https://github.com/losangle/Optimization-on-manifolds-with-extra-constraints.

If all you need is to force each w_i to be in [0, 1], you could do a change of variable and let w_i = cos(z_i) for example; then you can optimize over z (unconstrained) instead of w.

If you need the w_i to be nonnegative and sum to 1 (w_1 + ... + w_n = 1), you could try the following:

 * use a change of variable w = z .^ 2 (entry-wise squared) where z is on a sphere (spherefactory).

 * If enforcing w_i > 0 (strictly positive), you could try the following factory for w, where you'd use n positive definite matrices  of size 1x1, and they sum to identity which in this case is 1: https://github.com/NicolasBoumal/manopt/blob/master/manopt/manifolds/symfixedrank/sympositivedefinitesimplexcomplexfactory.m

 * Handle w separately through some kind of projected gradient method or a Frank-Wolfe method, maybe in an alternating scheme.

That's all that comes to mind. I'd be curious to hear what works best for you and what wasn't fruitful.

Best wishes,

Nicolas