Skip to main content
Menu

Robust acceleration for first-order optimisation methods

Spotlight on ongoing work by Michael Garstka

Logo of Cosmo software package.

Algorithms for convex optimisation problems are used to make smart decisions in a large number of domains. They run inside the control-loops of delivery drones, warehouse robots, self-driving cars, and the energy management system of your office building. They help investment funds to rebalance their portfolios and are used to plan supply and delivery chains from production to your doorstep. It is well understood how to solve moderate-size problems to optimality. However, a recent trend is to incorporate more data into optimisation models which can take state-of-the-art interior-point solvers a long time to find a solution. First-order optimisation methods, like our solver package COSMO.jl, can solve very large problems to a moderate accuracy level, but need a lot of iterations to achieve high-accuracy solutions.

In my current project I am investigating how to use Anderson acceleration to speed up the convergence of non-smooth first-order methods. The method was originally developed to solve nonlinear integral equations in the 1960s and only gained popularity in the optimisation community in the last few years. Its main idea is to store a history of previous algorithm steps and form a new guess based on a combination of these historic steps. While this method works surprisingly well in practice it is not always reliable. Most of this project is about exploring how best to safeguard the method without sacrificing too much of the performance gain. The latest release of COSMO: https://github.com/oxfordcontrol/COSMO.jl uses a safeguarded version of Anderson acceleration in the background.

We tested six different problem sets from various applications. Our preliminary results (below) indicate a significant reduction in iterations (and solve time) needed to find a high-accuracy solution. If you want to find out more, take a look at our documentation where we show how to solve a range of example problems.