Multivariate Riemannian manifold optimization problems

[shuai chen]

Dear Professor,

Sorry to be a bother. I was learning about Riemannian optimization and found a question.

If the following multivariate non-convex optimization problem arises, is it still possible to continue to use Manopt to solve it?

e.g.

I will be appreciated for your reply, thank you very much!

Sincerely,

Chen shuai

[Ronny Bergmann]

Hi Chen Shuai,

the last constraint might be a bit complicated to form a nice (maybe call it single) manifold.

But one could consider that problem on the product manifold of two spheres (for x and y) and keep the last constraint. One obtains a constraint optimisation problem on this product manifold and could use the algorithms described by Liu & Boumal (2019), for example their Augnmented Lagangrian. 

In the Matlab version of Manopt these are not directly available, but Liu has a git repository that extends manopt to use these. In the Julia variant (if you are open to using another programming language) these are available; but you can also see a short summary ALM (and the link to the aforementioned paper at https://manoptjl.org/stable/solvers/augmented_Lagrangian_method/

Best

Ronny 

[Nicolas Boumal]

Hello,

You can parameterize your search space in a nice way using the Stiefel manifold of size n x 2.  Indeed, your constraints are equivalent to the Stiefel constraints up to a linear change of variable. Here are the details:

Say [u, v] is a matrix of size n x 2 such that u and v are orthonormal vectors (so, it is a valid point on the manifold stiefelfactory(n, 2):  u and v have unit norm, and they are orthogonal).

Then, you could let x = u, and compute y as a function of u and v. Geometrically, the idea is that u and v are orthogonal, and we want to form y by rotating v somewhat in the plane formed by u and v, until x and y form the correct angle (that is, to ensure <x, y> = c).

Explicitly:

Set x = u.

Set y = cos(t) u + sin(t) v  where we need to solve for t first, in such a way that <x, y> = c.

(Notice that, by design, the norm of y is indeed 1.)

Since <x, y> = <u, cos(t) u + sin(t) v> = cos(t), it follows that cos(t) = c and sin(t) = sqrt(1 - c^2).

Thus, do this:

x = u

y = c*u + sqrt(1-c^2)*v

 -- this is just a linear change of variable:  [x, y] = [u, v] * [1, c ; 0, sqrt(1-c^2)].

Now create your Manopt optimization problem structure to optimize over stiefelfactory(n, 2). A matrix X on that manifold (your optimization variable) has two columns: u = X(:, 1) and v = X(:, 2). Compute x and y from u and v as above. Now use those in your cost function.

After you defined manopt.M = stiefelfactory(n, 2); and problem.cost = ...;  you can try to use automatic differentiation:  problem = manoptAD(problem); 

If that does not work, you will need to compute the gradient yourself. There is a linear transformation between [u, v] and [x, y], so that will affect your gradient, but it's nothing too complicated.

Best,

Nicolas

[Pierre Absil]

It may make sense to have in Manopt a "doubly generalized Stiefel manifold": \{X \in R^{n\times p}: X^T B X = C\} for some B, C \succ 0. The problem below is then readily addressed with p=2, B = I_n, C = [1, c; c 1].  -PA

[Nicolas Boumal]

Hello Pierre-Antoine -- I agree. Even more generally, it would be good to have tools in Manopt that make it simpler to optimize on a manifold that is a diffeomorphic image of another (this would cover the case here without the need to create and maintain a factory nearly identical to Stiefel, and it would cover quite a few other cases as well). I'll keep that in mind.

[Ronny Bergmann]

HI Nicolas, Hi Pierre-Antoine,

that indeed sounds like a very nice idea for a generic manifold; one would probably need the diffeo, its inverse, and the differentials of both (to be stored within this generic manifold) and could then check how and which functions could then be provided in a generic way.

I can also keep that in mind for the Julia version – maybe even as a topic for a master thesis (if that is ok; the next ones start in January) – from a Julia version one could probably also with not so much effort generate a Matlab version (and vice versa of course).

[Nicolas Boumal]

Hello Ronny,

For optimization through a diffeomorphism, you might find the following paper relevant (it treats a more general case):

https://link.springer.com/article/10.1007/s10107-024-02058-3

(Levin, Kileel, Boumal -- The effect of smooth parametrizations on nonconvex optimization landscapes -- 2024)

You'd have $\varphi : M \to X$ there as the diffeomorphism, where $M$ and $X$ would both be smooth manifolds now (of the same dimension) and $f, g$ are the cost functions, with $g = f \circ \varphi$.

Section 2.6 considers the case where $\varphi$ is a submersion: that's the case if we have a diffeomorphism of course, so all of that applies.

Lemma 3.11 provides the formulas relating the gradient and Hessian of $g$ to those of $f$. It involves three objects that come from varphi:  D\varphi (that's the "L" map in the paper), the adjoint of that thing (with respect to the Riemannian metrics on M and X), and the Hessian of varphi composed with a linear function (one would implement either that, or the Q map in the paper; but likely the former is more convenient).

What remains is retractions. There, the easiest would be to have access both to varphi and its inverse, so that you can just go through varphi, retract there, and travel back. The vector you're retracting would also be pushed through D\varphi. There is a section in the book AMS08 that argues you can build a retraction by going through a chart; the proof there is really arguing that you can retract through a diffeomorphism (it may even be written in that form;  writing this from memory, so to be checked).

For a student, a very first exercise might be to work out how to optimize over a sphere of radius $r > 0$ given an implementation of the sphere for radius 1. That provides a way to check that all the concepts click, and it's easy to check that the code is doing the right thing, before moving on.

Best,

Nicolas

[Ronny Bergmann]

Hello Nicolas,

thanks for the literature. Yes, I also had these ideas in mind that one at least needs \varphi, its inverse and differential.

I will start a small note collecting these ideas and try to interest a student in looking at this and implementing it.

Thanks for the comments.

Best

Ronny

[Nicolas Boumal]

Hello,

Manopt now has a new feature: lifts.

See documentation here: https://www.manopt.org/lifts.html

This makes it easy to optimize through a change of variable: we just need to encode the main properties of the change of variable in a lift structure, then pass it with our problem through the tool manoptlift.

In the discussion from this thread, it would look something like this (I didn't test this):

R = [1, c ; 0, sqrt(1-c^2)];

lift.embedded = true; % see documentation page

lift.M = stiefelfactory(n, 2);

lift.N = euclideanfactory(n, 2);

lift.phi = @(Y) Y  * R;

lift.Dphi = @(Y, V) V * R;

lift.Dphit = @(Y, U) U * R;

lift.hesshw = @(Y, V, W) zeros(n, 2);

Define your cost function in problem.cost = @(X) ... , ideally also its gradient and Hessian (ignoring any constraints, just the Euclidean things), then pass that problem structure to manoptlift. It outputs a new problem structure: run trustregions or some other solver on that. Then push the output through lift.phi to get your final answer.

Happy to help if this is still relevant.

[Ronny Bergmann]

That looks. like a really cool feature. I have two students starting with programming projects in August. Have not yet fully decided what they should do, but something like a `LiftedManifold` for Julia sounds nice as well. I will keep that in mind.

[Nicolas Boumal]

And it's not restricted to lifting manifolds: you can lift nonsmooth sets too. For example, a ball in R^n is just a sphere in R^n+1 projected down by trimming one dimension. Also, the simplex is just the image of the sphere after squaring each entry. So it's more LiftedSets, or perhaps SmoothLifts (since it's useful that phi is smooth on a smooth manifold ; it's the image of that manifold through phi that, conveniently, does not need to be smooth).

--
http://www.manopt.org
---
You received this message because you are subscribed to the Google Groups "Manopt" group.
To unsubscribe from this group and stop receiving emails from it, send an email to manopttoolbo...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/manopttoolbox/0e32da8e-73af-4514-b86c-b15ab1884c24n%40googlegroups.com.

[Ronny Bergmann]

Thanks for the clarification, sure, then SmoothLilft is the best name here.