(Geodesic) convexity of my objective on the Grassmannian?

[Matthew T.C. Li]

Hello there,

I have observed for my problem that TrustRegions with manopt converges to the same solution irrespective of the initial point. My conjecture is that my objective function is (geodesically?) convex, but I don't yet have the background knowledge to prove this. If there is anybody in this community who has familiarity with my problem,  could you please point me to some relevant references?

I am hoping a description at this level of generality suffices to capture my  problem.

Let A and B denote symmetric positive definite matrices of size d by d, and let C=A-B+2*I, where I is the identity matrix. We also define Cinv to be the inverse of C, assumed to exist. I would like to find Vr in Grassman(d,r) which maximizes

objective(Vr) = trace(Vr.T*B*Vr) - logdet(Vr.T*Cinv*Vr).

Using Lagrange multipliers and some algebraic manipulation, I obtain the following necessary and sufficient conditions for Vr to be a critical point:

(i) Vr.T*[A, B]*Vr = [Vr.T*A*Vr, Vr.T*B*Vr] where [A,B] = A*B-B*A is the matrix commutator, and

(ii) Vp.T*(A+B+A*B-B*B)*Vr = Vp.T*(A-B)*Vr*Vr.T*B*Vr, where Vp denotes any orthogonal complement to Vr.

I'm struggling to analytically determine feasible points of this, let alone show that only one exists. (Note that any r eigenvectors of A or B satisfies (i), but not necessarily (ii)).

My hope is that a more direct argument using geodesic convexity exists. (Or, if I am allowed to dream, that a direct analytical solution exists!)

Thank you in advance for your help,

Matt

[Nicolas Boumal]

Hello Matt,

Neat observation.

We can't hope for geodesic convexity on the Grassmann manifold (or on the Stiefel manifold) because it is compact (see for example Cor. 11.10 in my book).

However, that doesn't mean we can't have benign non-convexity.

To show that all local optima are global optima is still a bit of an art. You have the right idea when you started by writing down the necessary optimality conditions at first order. You likely need the conditions at second-order too, because a smooth function on a compact manifold has at least two critical points: a max and a min; we can't have both of them being optimal (unless the cost function is constant).

I don't have more specific suggestions at this point. Perhaps you'd find this blog post about the benign landscape of f(X) = Trace(A X* B X) on the orthogonal group to be useful in some ways.

One more thing: sometimes, non-convex problems do have local minima that have small attraction basins, and as a result we don't see them often in random experiments. It can also be the case that local minima exist for some data matrices (A, B, C), but that they don't for random A, B, C with high probability. If any of these situations applies to your problem, then they would prevent a direct proof that second order critical points are optimal. Just something to keep in mind.

 -- If you find the time to report back, I'm certainly curious to hear more about your findings.

Best,

Nicolas

[Matt Li]

Hi Nicolas,

Thanks for the prompt response! Yes, I was confused originally since
visualizing Grass(d=2,r=1), i.e., the circle, suggested to me that
it's impossible to have continuous, geodesically convex functions. I
appreciate the reference to your book towards making this intuition
formal. I will also certainly study your blog post closely.

When I have more answers I will report back (the context in which this
problem appears is also quite interesting, at least to me). Thanks for
releasing an excellent software package, and for maintaining this
community!

Best,
Matt

> --
> http://www.manopt.org
> ---
> You received this message because you are subscribed to a topic in the Google Groups "Manopt" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/manopttoolbox/f9YRZUDlWHI/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to manopttoolbo...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/manopttoolbox/86df735c-ce32-435c-8e2d-9540e1ae14ecn%40googlegroups.com.