Optimization Online


First Order Methods Beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems

Jerome Bolte (jerome.bolte***at***tse-fr.eu)
Shoham Sabach (ssabach***at***ie.technion.ac.il)
Marc Teboulle (teboulle***at***post.tau.ac.il)
Yakov Vaisbourd (yakov.vaisbourd***at***gmail.com)

Abstract: We focus on nonconvex and nonsmooth minimization problems with a composite objective, where the differentiable part of the objective is freed from the usual and restrictive global Lipschitz gradient continuity assumption. This longstanding smoothness restriction is pervasive in first order methods (FOM), and was recently circumvent for convex composite optimization by Bauschke, Bolte and Teboulle, through a simple and elegant framework which captures, all at once, the geometry of the function and of the feasible set. Building on this work, we tackle genuine nonconvex problems. We first complement and extend their approach to derive a full extended descent lemma by introducing the notion of smooth adaptable functions. We then consider a Bregman-based proximal gradient methods for the nonconvex composite model with smooth adaptable functions, which is proven to globally converge to a critical point under natural assumptions on the problem's data. To illustrate the power and potential of our general framework and results, we consider a broad class of quadratic inverse problems with sparsity constraints which arises in many fundamental applications, and we apply our approach to derive new globally convergent schemes for this class.

Keywords: Composite nonconvex nonsmooth minimization, proximal-gradient algorithms, descent lemma, Non Euclidean distances, Bregman distance, global convergence, Kudyka-{\L}osiajewicz proeprty, semi-algebraic functions, quadratic inverse problems, phase retrieval.

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 06/20/2017
Entry Accepted: 06/20/2017
Entry Last Modified: 06/20/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society