A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based on the Augmented Lagrangian

• 成果类型: Article
• 署名作者: Zhu, Daoli; Zhao, Lei; Zhang, Shuzhong
• 署名单位: Shanghai Jiao Tong University; Shanghai Jiao Tong University; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shanghai Jiao Tong University; Shanghai Jiao Tong University; University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1350
• 发表日期: 2024
• 关键词: alternating direction method; CONVERGENCE; algorithms; DECOMPOSITION; minimization; continuity; sparsity; admm

摘要

Nonlinearly constrained nonconvex and nonsmooth optimization models play an increasingly important role in machine learning, statistics, and data analytics. In this paper, based on the augmented Lagrangian function, we introduce a flexible first-order primal-dual method, to be called nonconvex auxiliary problem principle of augmented Lagrangian (NAPP-AL), for solving a class of nonlinearly constrained nonconvex and nonsmooth optimization problems. We demonstrate that NAPP-AL converges to a stationary solution A/ ffififfi at the rate of o(1/ k ), where k is the number of iterations. Moreover, under an additional error bound condition (to be called HVP-EB in the paper) with exponent 61 E (0, 1), we further show the global convergence of NAPP-AL. Additionally, if 61 E 0, 1 ( ], then we further 2 more show that the convergence rate is in fact linear. Finally, we show that the well-known Kurdyka-Lojasiewicz property and the Ho center dot lderian metric subregularity imply the aforementioned HVP-EB condition. We demonstrate that under mild conditions, NAPP-AL can also be interpreted as a variant of the forward-backward operator splitting method in this context.