# Optimizing in smooth waters: optimization on manifolds

This is a guest post by Nicolas Boumal, a friend and collaborator from Université catholique de Louvain (Belgium), now at Inria in Paris (France), who develops Manopt: a toolbox for optimization on manifolds.

Optimization on manifolds is about solving problems of the form

$\mathrm{minimize}_{x\in\mathcal{M}} f(x),$

where $\mathcal{M}$ is a nice, known manifold. By “nice”, I mean a smooth, finite-dimensional Riemannian manifold.

# The little Grothendieck problem over O(d)

Today’s post is about a recent paper of mine with Christopher Kennedy and Amit Singer entitled “Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups”. Earlier this week, we finished a major revision to the paper (even the title was slightly changed) and I decided to take the opportunity to blog about it (in a previous blog post I blogged about an open problem that is raised by this work).

— Generalized orthogonal Procrustes Problem —

In this post I will motivate the problem using the orthogonal Procrustes problem: Given ${n}$ point clouds in ${\mathbb{R}^d}$ of ${k}$ points each, the generalized orthogonal Procrustes problem consists of finding ${n}$ orthogonal transformations that best simultaneously align the point clouds. If the points are represented as the columns of matrices ${A_1,\dots,A_n}$, where ${A_i \in \mathbb{R}^{d\times k}}$ then the orthogonal Procrustes problem consists of solving

$\displaystyle \min_{O_1,.. .,O_n \in O(d)} \sum_{i,j=1}^n ||O_i^T A_i - O_j^T A_j||_F^2. \ \ \ \ \ (1)$

Since ${||O_i^T A_i - O_j^T A_j||_F^2 = \|A_i\|_F^2+\|A_j\|_F^2 - 2\mathrm{tr}\left( (A_iA_j^T)^T O_i O_j^T \right)}$, (1) has the same solution as the complementary version of the problem

$\displaystyle \max_4{O_1,.. .,O_n \in O(d)} \sum_{i,j=1}^n \mathrm{tr}\left( C_{ij}^T O_i O_j^T \right), \ \ \ \ \ (2)$

where ${C\in\mathbb{R}^{dn\times dn}}$ has ${d\times d}$ blocks given by ${C_{ij} = A_iA_j^T}$. Note that ${C}$ is positive semidefinite.

In fact, we will focus on problems of the form (2), for any positive definite ${C\in\mathbb{R}^{dn\times dn}}$ (which encodes a few other problems, see more here).

# Computing sparse quadratic models in DFO

paper of mine (together with Katya Scheinberg and Luis Nunes Vicente) was recently awarded the 2013 INFORMS Optimization Society student paper prize and so I decided to use the occasion to restart my blog by writing a post about this work.

This paper, entitled “Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization”, was the basis of my Master Thesis back in 2010. In this post I will try to briefly explain the intuition and ideas behind the results in the paper, the actual paper is available here.

The framework is unconstrained optimization: one wants to minimize a (sufficiently smooth) function ${f:\mathbb{R}^n\rightarrow\mathbb{R}}$ over ${\mathbb{R}^n}$. In many applications, function evaluations are particularly expensive and one has no access to function derivatives (an example of this is if the goal is to optimize a set of parameters and each evaluation requires an expensive simulation). Motivated by these applications we are interested in optimizing ${f}$ without using its derivatives and using as few function evaluations as possible, this is known as Derivative-Free Optimization.