A Homogeneous Second-Order Descent Method for Nonconvex Optimization

被引:0
作者
Zhang, Chuwen [1 ]
He, Chang [1 ]
Jiang, Yuntian [1 ]
Xue, Chenyu [1 ]
Jiang, Bo [1 ,2 ,3 ]
Ge, Dongdong [4 ]
Ye, Yinyu [5 ]
机构
[1] Shanghai Univ Finance & Econ, Res Inst Interdisciplinary Sci, Sch Informat Management & Engn, Shanghai 200433, Peoples R China
[2] Shanghai Univ Finance & Econ, Key Lab Interdisciplinary Res Computat & Econ, Minist Educ, Shanghai 200433, Peoples R China
[3] Shanghai Univ Finance & Econ, Dishui Lake Adv Finance Inst, Shanghai 200120, Peoples R China
[4] Shanghai Jiao Tong Univ, Antai Coll Econ & Management, Shanghai 200030, Peoples R China
[5] Stanford Univ, Inst Computat & Math Engn, Palo Alto, CA 94305 USA
基金
中国国家自然科学基金;
关键词
nonconvex optimization; nonlinear programming; global convergence; inexact algorithm; CUBIC REGULARIZATION; NEWTON METHOD; COMPLEXITY; EIGENVALUE; SUBPROBLEM; ALGORITHMS; CG;
D O I
10.1287/moor.2023.0132
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页数:32
相关论文
共 45 条
[41]   On cones of nonnegative quadratic functions [J].
Sturm, JF ;
Zhang, SZ .
MATHEMATICS OF OPERATIONS RESEARCH, 2003, 28 (02) :246-267
[42]  
Xu Y, 2018, ADV NEUR IN, V31
[43]  
Ye Y, 2005, Second order optimization algorithms I
[44]   New results on quadratic minimization [J].
Ye, YY ;
Zhang, SZ .
SIAM JOURNAL ON OPTIMIZATION, 2003, 14 (01) :245-267
[45]  
Zhang CW, 2023, Arxiv, DOI arXiv:2208.00208