< Back to previous page

Publication

Newton-type alternating minimization algorithm for convex optimization

Journal Contribution - Journal Article

We propose a Newton-type alternating minimization algorithm (NAMA) for solving structured nonsmooth convex optimization problems where the sum of two functions is to be minimized, one being strongly convex and the other composed with a linear mapping. The proposed algorithm is a line-search method over a continuous, real-valued, exact penalty function for the corresponding dual problem, which is computed by evaluating the augmented Lagrangian at the primal points obtained by alternating minimizations. As a consequence, NAMA relies on exactly the same computations as the classical alternating minimization algorithm (AMA), also known as the dual-proximal gradient method. Under standard assumptions, the proposed algorithm converges with global sublinear and local linear rates, while under mild additional assumptions, the asymptotic convergence is superlinear, provided that the search directions are chosen according to quasi-Newton formulas. Due to its simplicity, the proposed method is well suited for embedded applications and large-scale problems. Experiments show that using limited-memory directions in NAMA greatly improves the convergence speed over AMA and its accelerated variant.
Journal: IEEE Transactions on Automatic Control
ISSN: 0018-9286
Issue: 2
Volume: 64
Pages: 697 - 711
Publication year:2018
BOF-keylabel:yes
IOF-keylabel:yes
BOF-publication weight:3
CSS-citation score:1
Authors:International
Authors from:Higher Education
Accessibility:Closed