A Lagrange-Newton algorithm for sparse nonlinear programming

• 成果类型: Article
• 署名作者: Zhao, Chen; Xiu, Naihua; Qi, Houduo; Luo, Ziyan
• 署名单位: Beijing Jiaotong University; University of Southampton
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01719-x
• 发表日期: 2022
• 页码: 903-928
• 关键词: optimality conditions; signal recovery; PURSUIT; approximation; minimization; selection

摘要

The sparse nonlinear programming (SNP) problem has wide applications in signal and image processing, machine learning and finance, etc. However, the computational challenge posed by SNP has not yet been well resolved due to the nonconvex and discontinuous to-norm involved. In this paper, we resolve this numerical challenge by developing a fast Newton-type algorithm. As a theoretical cornerstone, we establish a first-order optimality condition for SNP based on the concept of strong beta-Lagrangian stationarity via the Lagrangian function, and reformulate it as a system of nonlinear equations called the Lagrangian equations. The nonsingularity of the corresponding Jacobian is discussed, based on which the Lagrange-Newton algorithm (LNA) is then proposed. Under mild conditions, we establish the locally quadratic convergence and its iterative complexity estimation. To further demonstrate the efficiency and superiority of our proposed algorithm, we apply LNA to two specific problems arising from compressed sensing and sparse high-order portfolio selection, in which significant benefits accrue from the restricted Newton step.