Applications of Interior Point methods: from Sparse Approximations to Discrete Optimal Transport

This is a talk given by Prof Jacek Gondzio as part of the Online Seminar Series Machine Learning NeEDS Mathematical Optimization, https://congreso.us.es/mlneedsmo/

Abstract:

A variety of problems in modern applications of optimization require a selection of a ‘sparse’ solution, a vector with preferably few nonzero entries. Such problems may originate from very different applications in computational statistics, signal or image processing or compressed sensing, finance, machine learning and discrete optimal transport, to mention just a few. Sparse approximation problems are often solved with dedicated and highly specialised first-order methods of optimization. In this talk I will argue that these problems may be very efficiently solved by the more reliable optimization techniques which involve some use of the (inexact) second-order information as long as this is combined with appropriately chosen iterative techniques of linear algebra, such as for example methods from the Krylov-subspace family. Two particular classes of methods, the Newton Conjugate Gradient and the Interior Point Method will be interpreted as suitable homotopy type approaches and will be applied to solve problems arising from: compressed sensing, multi-period portfolio optimization, classification of data coming from functional Magnetic Resonance Imaging, restoration of images corrupted by Poisson noise, classification via regularized logistic regression, and discrete optimal transport. In all these cases, the performance of the proposed methods will be compared against competitive first-order methods. Computational evidence will be provided to demonstrate that specialized second-order methods compare favourably and often outperform the cutting-edge first-order methods.

More information

Link to the talk: https://eu.bbcollab.com/guest/5591917a6d0441ae8e2f7c3f15d461af

Organisers

The organizers of the Online Seminar Series Machine Learning NeEDS Mathematical Optimization
Emilio Carrizosa, IMUS-Instituto de Matemáticas de la Universidad de Sevilla
Thomas Halskov, Copenhagen Business School
Kseniia Kurishchenko, Copenhagen Business School
Cristina Molero-Río, IMUS-Instituto de Matemáticas de la Universidad de Sevilla
Jasone Ramírez-Ayerbe, IMUS-Instituto de Matemáticas de la Universidad de Sevilla
Dolores Romero Morales, Copenhagen Business School