A Homogeneous Second-Order Descent Method for Nonconvex Optimization
Chuwen Zhang This research is partially supported by the National Natural Science Foundation of China (NSFC) [Grant NSFC-72150001, 72225009, 11831002] and the Natural Science Foundation of Shanghai [23ZR1445900]. School of Information Management and Engineering Shanghai University of Finance and Economics Dongdong Ge Antai College of Economics and Management Shanghai Jiao Tong University Chang He School of Information Management and Engineering Shanghai University of Finance and Economics Yuntian Jiang School of Information Management and Engineering Shanghai University of Finance and Economics Chenyu Xue School of Information Management and Engineering Shanghai University of Finance and Economics Bo Jiang School of Information Management and Engineering Shanghai University of Finance and Economics Yinyu Ye Department of Management Science and Engineering, Stanford University
Abstract
In this paper, we introduce a Homogeneous Second-Order Descent Method (HSODM) motivated from the homogenization trick in quadratic programming. The merit of homogenization is that only the leftmost eigenvector of a gradient-Hessian integrated matrix is computed at each iteration. Therefore, the algorithm is a single-loop method that does not need to switch to other sophisticated algorithms and is easy to implement. We show that HSODM has a global convergence rate of $O(\epsilon^{-3/2})$ to find an $\epsilon$ -approximate second-order stationary point, and has a local quadratic convergence rate under the standard assumptions. The numerical results demonstrate the advantage of the proposed method over other second-order methods.
中文速览
把非凸优化中难以统一处理"负曲率"和"牛顿步"这两类情形的问题，长期困扰着二阶优化算法的设计——现有方法要么需要在不同子程序之间来回切换，要么实现复杂。受二次规划齐次化技巧的启发，作者提出了一种新方法 HSODM（同质二阶下降法），核心思路是把梯度和海森矩阵整合成一个 (n+1) 维的"齐次矩阵"，然后只需在每次迭代中求该矩阵的最左特征向量（即最小特征值对应的方向）即可同时捕获梯度信息和负曲率，不再需要在不同算法模块间切换，形成一个干净的单循环方法。理论上，HSODM 以 O(ε⁻³/²) 的全局迭代复杂度收敛到 ε 近似二阶驻点，与立方正则化牛顿法持平，同时在标准假设下具有局部二次收敛速度；在 CUTEst 基准测试集上的数值实验也证实其表现优于经典信赖域法和立方正则化牛顿法。这项工作的重要意义在于，它提供了一个形式简洁、易于实现、理论保证完备的二阶非凸优化框架，有望成为实践者更友好的高效工具。
原文 arXiv:2211.08212;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2211.08212v7