Valentina De Simone, Daniela di Serafino, Jacek Gondzio, Spyros Pougkakiotis, Marco Viola
Abstract
Large-scale optimization problems that seek sparse solutions have
become ubiquitous. They are routinely solved with various specialized
first-order methods. Although such methods are often fast, they usually
struggle with not-so-well conditioned problems. In this paper, specialized
variants of an interior point-proximal method of multipliers are proposed
and analyzed for problems of this class. Computational experience
on a variety of problems, namely, multi-period portfolio optimization,
classification of data coming from functional Magnetic Resonance Imaging,
restoration of images corrupted by Poisson noise, and classification
via regularized logistic regression, provides substantial evidence
that interior point methods, equipped with suitable linear algebra,
can offer a noticeable advantage over first-order approaches.
Key words: Sparse Approximations, Interior Point Methods, Proximal Methods of Multipliers, Nonlinear Convex Programming, Solution of KKT Systems, Portfolio Optimization, Image Restoration, Classification in Machine Learning.