Working Seminar on Formal Models, Discrete Structures, and Algorithms

Recent Trends in Convex Programming, with Applications

Jakub Mareček (The University of Nottingham)

When: October 24, 2pm

Where: room G2.91b

Abstract

There is a rich history of research in convex programming, going back at least to Lagrange. Perhaps surprisingly, though, there has also been a considerable progress in the past five years. Newly developed methods allow for the solution of instances with millions of variables. Thousands of practical applications have changed a number of fields in Engineering and may well change much in Combinatorial Optimisation as well. This talk provides a survey of the developments and presents a few applications co-developed by the presenter.

Step-by-step, the talk covers: – the role of conic programming in combinatorial optimisation – probabilistic guarantees for convex programming relaxations – accelerated first-order methods for convex programming – lock-free parallelisation of first-order methods – hardware implementations with applications in, among others, signal decoding for fast wireless internet (LTE), university course timetabling, parameter setting in scanning tunneling microscopes, and sales forecasting.