Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence

Jérôme Bolte, Shoham Sabach () and Marc Teboulle ()
Additional contact information
Shoham Sabach: Faculty of Industrial Engineering and Management, Technion—Israel Institute of Technology, Haifa 3200003, Israel
Marc Teboulle: School of Mathematical Sciences, Tel-Aviv University, Ramat-Aviv 69978, Israel

Mathematics of Operations Research, 2018, vol. 43, issue 4, 1210-1232

Abstract: We introduce a novel approach addressing global analysis of a difficult class of nonconvex-nonsmooth optimization problems within the important framework of Lagrangian-based methods. This genuine nonlinear class captures many problems in modern disparate fields of applications. It features complex geometries, qualification conditions, and other regularity properties do not hold everywhere. To address these issues, we work along several research lines to develop an original general Lagrangian methodology, which can deal, all at once, with the above obstacles. A first innovative feature of our approach is to introduce the concept of Lagrangian sequences for a broad class of algorithms. Central to this methodology is the idea of turning an arbitrary descent method into a multiplier method. Secondly, we provide these methods with a transitional regime allowing us to identify in finitely many steps a zone where we can tune the step-sizes of the algorithm for the final converging regime. Then, despite the min-max nature of Lagrangian methods, using an original Lyapunov method we prove that each bounded sequence generated by the resulting monitoring schemes are globally convergent to a critical point for some fundamental Lagrangian-based methods in the broad semialgebraic setting, which to the best of our knowledge, are the first of this kind.

Keywords: nonlinear composite minimization; nonconvex and nonsmooth minimization; Lagrangian-based methods; proximal method of multipliers; semialgebraic optimization; nonsmooth Kurdyka-?ojasiewicz property; global convergence (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0900 (application/pdf)

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:inm:ormoor:v:43:y:2018:i:4:p:1210-1232

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().