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

• 成果类型: Article
• 署名作者: Zhang, Penghe; Xiu, Naihua; Luo, Ziyan
• 署名单位: Beijing Jiaotong University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.0320
• 发表日期: 2024
• 页码: 2602-2625
• 关键词: alternating direction method; nonconvex; multipliers; minimization

摘要

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.