Category Archives: Optimization

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.

Continue reading Optimizing in smooth waters: optimization on manifolds

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).

Continue reading The little Grothendieck problem over O(d)

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.

Continue reading Computing sparse quadratic models in DFO