主题：A Lagrange-Newton Algorithm for Sparse Nonlinear Programming（稀疏非线性规划的拉格朗日-牛顿算法）

主讲人：北京交通大学 罗自炎教授

主持人：经济数学学院 车茂林副教授

时间：2021年10月29日（周五）09:00

直播平台及会议ID：腾讯会议：362180283；密码：1029

主办单位：经济数学学院 科研处

主讲人简介：

罗自炎，女，北京交通大学理学院，教授、博士生导师。美国斯坦福大学、新加坡国立大学、英国南安普顿大学访问学者、香港理工大学研究助理。SCI论文30余篇，ESI高被引论文2篇。SIAM出版社英文专著1部，主持国家自然科学基金“面上”、“青年”基金项目、北京市自然科学基金重点项目各1项。2016年北京运筹学年会特邀大会报告;2017年第十一届全国数学规划学术会议青年专题特邀报告;2020.9亚太运筹学会Pre-APORS会议代表中国运筹学会做国家贡献论文报告，2020年获中国运筹学会青年科技奖提名奖，2021年北京市青年教师教学基本功比赛二等奖。主要研究兴趣：大规模稀疏低秩优化、张量优化与统计学习。

内容提要：

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 L0-norm involved. In this talk, 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.稀疏非线性规划（SNP）广泛应用于信号与图像处理、机器学习、金融等领域。然而，其中的L0范数的非凸非连续性，给SNP的求解带来计算上的挑战性。在本次报告中，我们将介绍一类快速的牛顿类型算法来求解SNP。首先我们提出强β—Lagrange稳定点并建立SNP的一阶最优性条件，并借助稀疏投影建立等价的Lagrange方程组来刻画这一稳定点。 通过分析这一方程组的Jacobi矩阵非奇异性，我们设计Lagrange-Newton算法（LNA）。在较弱的条件下，我们建立LNA算法的二次收敛速度与迭代复杂性。为进一步展示我们算法的有效性与优势，我们将LNA算法应用于几个具体问题，包括压缩感知与稀疏投资组合等。可以看出，算法中的限制Newton步使得我们的数值效果优势明显。