manifold with boundary

[Bowen Li]

Greetings,

I am facing an optimization of the form: 

Problem A:

min f(x) over M, where M is a submanifold in R^d but with a boundary (say, a strip in the sphere) and f(x) is smooth and non-convex. 

In my case, this problem can also be equivalently formulated as 

Problem B:

min f(x) + h(x) over M', where h(x) is an indicator function of a convex set and M' is an embedded submanifold in R^d without boundary. 

Unfortunately, I didn't find any reference on manifold optimization for Problem A. 

For problem B, designing a Riemannian proximal (gradient or Newton) algorithm is possible. But it seems that the convergence analysis only works for the case where h is Lip-continuous. 

I really appreciate it if anyone could provide any references/comments on either Problem A or Problem B! Thank you so much in advance for your help!

[Ronny Bergmann]

Hi,

if the proximal map of f in B is available you could check for Douglas-Rachford, which works for Hadamard manifolds (and lower-semicontinuous f and h).

For Problem A it depends a lot whether you can implement retractions and similar tools on said manifold with a boundary? Maybe you can also phrase that as a constraint on the manifold – if you say it is a stripe on the sphere? Then you could look into constrained optimization on manifolds (ALM or EPM for example).

Best,

Ronny

[Nicolas Boumal]

Hello,

Indeed, there is no natural support for boundaries in Manopt or in the classical theory of Riemannian optimization.

One way is to use nonsmooth / constrained optimization techniques, as Ronny mentioned.

Sometimes, it's possible to smoothly parameterize your manifold with boundary, in which case you can optimize through that parameterization instead (and Manopt would apply).

For example, the simplex in R^n (which is not smooth) can be smoothly parameterized by entry-wise squaring the vectors on a unit sphere. That's a smooth parameterization that allows you to move any optimization problem on the simplex to an optimization problem on a sphere.

Likewise, you can smoothly parameterize the (nonsmooth) set of matrices of rank <= r using a factorization, as (L, R) -> LR*, where L and R have only r columns. (Notice that the set of matrices of rank = r is a smooth manifold, and can be handled directly in Manopt).

You can read more about this in a paper with Levin and Kileel if that seems relevant for your purposes: https://arxiv.org/abs/2207.03512

Best,

Nicolas