I encountered some optimization problem on the special Euclidean group SE(3) at work and wonder how to solve it. The current approach of my colleagues was to use a local parametrization of the manifold and then applying a function from a standard optimization toolbox. However I am also aware of the recent developments on optimization problems on manifolds (see e.g. http://www.eeci-institute.eu/GSC2011/Photos-EECI/EECI-GSC-2011-M5/book_AMS.pdf). This way there is no parametrization needed. Is there any other advantage? Have the two approached been compared somewhere?
$\begingroup$
$\endgroup$
2
-
4$\begingroup$ Try manopt.org $\endgroup$– SuvritCommented Oct 28, 2016 at 22:23
-
5$\begingroup$ Since you're asking specifically about matrix manifolds, you should take a look at Absil et al.'s book Optimization Algorithms on Matrix Manifolds, press.princeton.edu/titles/8586.html. The main advantage is indeed not needing a parametrization (which can be very unwieldy and prevent good descent steps, which suffer from additional smallness conditions if the parametrization is only local). The disadvantage is that you need to compute geodesics (which replace the vector-space descent directions), which can be very expensive to compute. $\endgroup$– Christian ClasonCommented Oct 29, 2016 at 8:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
To complement Christian Clason's comment: there is usually no need to compute geodesics to optimize over manifolds directly. The usual replacement used for optimization purposes is called a retraction. A retraction is an approximation of the exponential map (which generates geodesics), accurate up to first order. For various manifolds of practical interest, computationally inexpensive retractions are known. For example, for the sphere, retracting the tangent vector $u$ at $x$ is often done as $R_x(u) = \frac{x+u}{\|x+u\|_2}$. For $u$ small, this agrees with the exponential of $u$ at $x$ up to first order.
Edit: in addition to Absil et al.'s excellent book, you may also find my introduction to optimization on manifolds helpful: http://www.nicolasboumal.net/book.
-
$\begingroup$ How difficult is it to compute 2nd order retractions, at least for some cases? Even if it takes much longer to compute than 1st order retraction, might it possibly save enough top level algorithm iterations as to speed up the solution, and maybe even make the solution process more robust? Even though 1st order retraction is enough to produce quadratic convergence of a (trust region, say) Newton method, might 2nd order retraction improve robustness and performance, especially for the most of the algorithm solution path when quadratic convergence has not yet kicked in? $\endgroup$ Commented Jun 5, 2017 at 18:28
-
1$\begingroup$ It is difficult to say if second-order retractions could help reduce the total number of required iterations. However, it is known that using second-order retractions can be useful to guarantee convergence to second-order critical points (as shown by my colleagues and myself in arxiv.org/abs/1605.08101). Also, computing second-order retractions is often inexpensive: Malick and Absil showed that, for Riemannian submanifolds of R^n, orthogonal projection to the manifold is a second-order retraction (see also example above for the sphere): epubs.siam.org/doi/abs/10.1137/100802529. $\endgroup$ Commented Jun 13, 2017 at 14:41