The multiproximal linearization method for convex composite problems

Jérôme Bolte, Zheng Chen and Edouard Pauwels
Additional contact information
Zheng Chen: Zhejiang University [Hangzhou, China]
Edouard Pauwels: IUT Paul Sabatier - Institut Universitaire de Technologie - Paul Sabatier - UT3 - Université Toulouse III - Paul Sabatier - UT - Université de Toulouse

Post-Print from HAL

Abstract: Composite minimization involves a collection of smooth functions which are aggregated in a nonsmooth manner. In the convex setting, we design an algorithm by linearizing each smooth component in accordance with its main curvature. The resulting method, called the Multiprox method, consists in solving successively simple problems (e.g., constrained quadratic problems) which can also feature some proximal operators. To study the complexity and the convergence of this method, we are led to prove a new type of qualification condition and to understand the impact of multipliers on the complexity bounds. We obtain explicit complexity results of the form O(1k) involving new types of constant terms. A distinctive feature of our approach is to be able to cope with oracles involving moving constraints. Our method is flexible enough to include the moving balls method, the proximal Gauss–Newton's method, or the forward–backward splitting, for which we recover known complexity results or establish new ones. We show through several numerical experiments how the use of multiple proximal terms can be decisive for problems with complex geometries.

Keywords: Composite optimization; Convex optimization; Complexity; First order methods; Proximal Gauss-Newton's method; Prox-linear method (search for similar items in EconPapers)
Date: 2020-07
References: Add references at CitEc
Citations:

Published in Mathematical Programming, 2020, 182 (1/2), pp.1-36. ⟨10.1007/s10107-019-01382-3⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-03170605

DOI: 10.1007/s10107-019-01382-3

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().