Interior Point Methods and Column Generation: From Sparse Approximations to Discrete Optimal Transport

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 such problems may be solved efficiently
by interior point methods, especially if those are combined with column
generation and iterative linear algebra techniques.