Zero-One Composite Optimization: Lyapunov Exact Penalty and a Globally Convergent Inexact Augmented Lagrangian Method

Penghe Zhang (), Naihua Xiu () and Ziyan Luo ()
Additional contact information
Penghe Zhang: School of Mathematics and Statistics, Beijing Jiaotong University, Beijing 100044, People’s Republic of China
Naihua Xiu: School of Mathematics and Statistics, Beijing Jiaotong University, Beijing 100044, People’s Republic of China
Ziyan Luo: School of Mathematics and Statistics, Beijing Jiaotong University, Beijing 100044, People’s Republic of China

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2602-2625

Abstract: We consider the problem of minimizing the sum of a smooth function and a composition of a zero-one loss function with a linear operator, namely the zero-one composite optimization problem (0/1-COP). It has a vast body of applications, including the support vector machine (SVM), calcium dynamics fitting (CDF), one-bit compressive sensing (1-bCS), and so on. However, it remains challenging to design a globally convergent algorithm for the original model of 0/1-COP because of the nonconvex and discontinuous zero-one loss function. This paper aims to develop an inexact augmented Lagrangian method (IALM), in which the generated whole sequence converges to a local minimizer of 0/1-COP under reasonable assumptions. In the iteration process, IALM performs minimization on a Lyapunov function with an adaptively adjusted multiplier. The involved Lyapunov penalty subproblem is shown to admit the exact penalty theorem for 0/1-COP, provided that the multiplier is optimal in the sense of the proximal-type stationarity. An efficient zero-one Bregman alternating linearized minimization algorithm is also designed to achieve an approximate solution of the underlying subproblem in finite steps. Numerical experiments for handling SVM, CDF, and 1-bCS demonstrate the satisfactory performance of the proposed method in terms of solution accuracy and time efficiency.

Keywords: Primary: 90C26; 49M37; 65K10; zero-one composite optimization problem; Lyapunov exact penalty; inexact augmented Lagrangian method; global convergence; application (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.0320 (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:49:y:2024:i:4:p:2602-2625

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 ().