Fast First-Order Methods for Large-Scale Convex Optimisation

This DPhil (PhD) project will be primarily concerned with first-order matrix-free algorithms for large-scale convex optimisation.

Mathematical optimisation broadly relates to problems where one wants to find a quantifiably 'best' decision out of a set of permissible ones. One can easily see how this notion captures an incredibly broad set of problems, and, indeed, in their most general setting, these problems are very difficult to solve. However, a special class of so-called 'convex' problems is particularly amenable to be solved; furthermore, this class of problem can be used in algorithms tackling problems which are not convex. Convex optimisation has therefore seen a lot of research effort in recent decades.

One can also put optimisation algorithms/methods into different classes of their own. First-order methods fall into a 'lightweight' class which tends to be well-suited to problems of very large scale. Within these, matrix-free methods (where solutions of large systems of equations are not required) are even more appealing from a standpoint of computational expense.

These methods have become attractive as practitioners have come to expect to be able to solve extremely large problems frequently, but they have traditionally been associated with the weakness of achieving only low-accuracy solutions. However, recent academic work has shown that careful algorithmic enhancements can defeat this downside when solving linear optimisation problems (a special subclass of convex problems).

In a similar vein to this, I propose to design enhanced matrix-free first-order methods for more general classes of convex optimisation problems, as seen in applications including artificial intelligence, medical imaging, and materials science.

The methodology involved with this work will have two principal facets. On one front there are the mathematics of numerical convex optimisation, to suggest novel algorithmic approaches as well as to enable the derivation of formal theoretical guarantees that a particular class of problems can be solved within a given computational expense. On another front there is the computational work involved with implementing the proposed algorithms into efficient and easy-to-use software, which can ultimately be used by practitioners in a very broad range of settings.

There is good reason to think that this research will be highly impactful. In recent years, members of Prof. Paul Goulart's (my supervisor's) group have built an impressive track record with similarly minded work, leading to the release of optimisation software with tens of thousands of users in academic and industrial organisations.

Since this work pertains to the application of numerical/algorithmic approaches to approximately solve mathematical problems, it fits fundamentally into the EPSRC research area of Numerical Analysis. However, the industrial and academic settings which will motivate the practical challenges to be addressed by this research are far-ranging, and encompass EPSRC research areas including control engineering, digital signal processing, robotics, and engineering design.