Operator Splitting Methods and Software for Convex Optimisation

Add to your list(s) Download to your calendar using vCal

• Paul Goulart, University of Oxford
• Wednesday 14 November 2018, 14:00-15:00
• 1109B (CAP seminar room) .

If you have a question about this talk, please contact Giordano Scarciotti.

Abstract: This talk will present a general purpose solution method for convex optimisation problems with quadratic objectives based on the alternating direction method of multipliers (ADMM). We employ a novel operator splitting technique that requires the solution of a quasi-definite linear system with the same coefficient matrix in each iteration. Our algorithm is very robust, placing no requirements on the problem data such as positive definiteness of the objective function or linear independence of the constraint functions. For large-scale semidefinite programs (SDPs), we also employ decomposition strategies based on identifying chordal sparsity in the problem data to split large constraints into multiple smaller constraints. It is well-known that the iterates generated by ADMM will diverge if the optimisation problem is not feasible. Nevertheless, we show that it is possibly to reliably detect primal and dual infeasible problems from the algorithm iterates for a wide class of convex optimization problems including both quadratic and general conic programs. In particular, we show that in the limit the ADMM iterates either satisfy a set of first-order optimality conditions or produce a certificate of either primal or dual infeasibility. Based on these results, we propose termination criteria for detecting primal and dual infeasibility in ADMM . We have implemented our algorithm for quadratic programs in the open-source C-language solver OSQP (for quadratic programs) and in a Julia language prototype for general conic problems. OSQP has a small footprint, is library-free, and has been extensively tested on many problem instances from a wide variety of application areas. OSQP is the default QP solver in the Python package CVXPY and supports interfaces to several other programming languages.

Biography: Paul Goulart joined the University of Oxford in 2014 as an Associate Professor in Engineering Science and a Tutorial Fellow in Engineering Science. He received his SB and MSc degrees in Aeronautics and Astronautics from the Massachusetts Institute of Technology (MIT). Following his undergraduate studies he was a software developer in the flight operations centre for the Chandra X-Ray Observatory at the Harvard-Smithsonian Centre for Astrophysics, and later an engineer in the Autonomous Systems research group at the Charles Stark Draper Laboratory. In 2003 he was selected as a Gates Scholar at the University of Cambridge, where he received a PhD in Control Engineering in 2007. From 2007 to 2011 he was a Lecturer in control systems in the Department of Aeronautics at Imperial College London, and from 2011 to 2014 a Senior Researcher in the Automatic Control Laboratory at ETH Zurich. He is currently a member of the Control Group in the department of Engineering Science. His research interests are mainly in robust and high speed optimisation and control, with a wide range of application areas including fluid flows, economics and traffic networks.

This talk is part of the Control and Power Seminars series.

This talk is included in these lists:

• 1109B (CAP seminar room)
• Andrea Picciau's list
• Control and Power Seminars

Note that ex-directory lists are not shown.