Category Archives: Optimization

Optimizing in smooth waters: optimization on manifolds

Optimization

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)

Approximation Algorithms, Optimization

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

Optimization

A 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 →