二阶分裂算法及其应用

doi:10.15960/j.cnki.issn.1007-6093.2025.04.011

Abstract

Abstract:

Combining cubic regularization and trust region method to solve the subproblem, we propose a second-order splitting algorithm for a class of large scale separable nonconvex optimization problems under inexact Hessian information. The global convergence result is obtained under some mild assumptions. It is proved that the algorithm needs at most $O\left( {{\varepsilon ^{ - 2}}} \right) $ evaluations to produce a $\varepsilon $-approximate stable solution. The algorithm is employed to solve a nonconvex binary classification problem in machine learning with nice numerical experiments results.

Key words: large scale separable non-convex optimization problems, second-order splitting algorithm, inexact Hessian information, global convergence, complexity analysis, nonconvex binary classification

CLC Number:

O221.2
O224

Zilin TAN, Honglin LUO. A second-order splitting method with its application[J]. Operations Research Transactions, 2025, 29(4): 121-140.

Figures/Tables 7

References 28

1	GlowinskiR,MarrocoA.Sur l'approximation, paréléments finis d'ordre un, et la résolution, par pénalisation-dualitéd'une classe de problèmes de Dirichlet non linéaires[J].Journal of Equine Veterinary Science,1975,2(R2):41-76.
2	GabayD,MercierB.A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J].Computers Mathematics with Applications,1976,2(1):17-40. doi: 10.1016/0898-1221(76)90003-1
3	Dhar S, Yi C, Ramakrishnan N, et al. ADMM based scalable machine learning on Spark[C]//IEEE International Conference on Big Data, 2015: 1174-1182.
4	YangQ,ChenG,WangT.ADMM-based distributed algorithm for economic dispatch in power systems with both packet drops and communication delays[J].IEEE/CAA Journal of Automatica Sinica,2020,7(3):842-852. doi: 10.1109/JAS.2020.1003156
5	SchizasD,RibeiroA,GiannakisgB.Consensus in ad hoc WSNs with noisy links-part Ⅰ: Distributed estimation of deterministic signals[J].IEEE Transactions on Signal Processing,2008,56(1):350-364. doi: 10.1109/TSP.2007.906734
6	Huebner N, Rink Y, Suriyah M, et al. Distributed AC-DC optimal power flow in the European transmission grid with ADMM[C]//55th International Universities Power Engineering Conference, 2020: 1-6.
7	Xu P, Roosta-Khorasani F, Mahoney M W. Second-order optimization for non-convex machine learning: An empirical study[C]//The 2020 SIAM International Conference on Data Mining, 2020: 199-207.
8	KanK,FungS W,RuthottoL.PNKH-B: A projected newton–-Krylov method for large-scale bound-constrained optimization[J].SIAM Journal on Scientific Computing,2021,43(5):704-726. doi: 10.1137/20M1341428
9	WangF H,CaoW F,XuZ B.Convergence of multi-block Bregman ADMM for nonconvex composite problems[J].Science China (Information Sciences),2018,61(12):1-12.
10	CurtisF E,RobinsonD P,RoyerC W,et al.Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization[J].SIAM Journal on Optimization,2021,31(1):518-544. doi: 10.1137/19M130563X
11	GouldN I,RobinsonD P,ThorneH S.On solving trust-region and other regularised subproblems in optimization[J].Mathematical Programming,2010,2(1):21-57.
12	HazanE,KorenT.A linear-time algorithm for trust region problems[J].Mathematical Programming,2016,158(1-2):363-381. doi: 10.1007/s10107-015-0933-y
13	NesterovY,PolyakB T.Cubic regularization of Newton method and its global performance[J].Mathematical Programming,2006,108(1):177-205. doi: 10.1007/s10107-006-0706-8
14	CartisC,GouldN,TointP L.Adaptive cubic regularisation methods for unconstrained optimization, Part Ⅰ: Motivation, convergence and numerical results[J].Mathematical Programming,2011,127(2):245-295. doi: 10.1007/s10107-009-0286-5
15	JiangB,LinT,MaS,et al.Structured nonconvex and nonsmooth optimization: Algorithms and iteration complexity analysis[J].Computational Optimization and Applications,2019,72,115-157. doi: 10.1007/s10589-018-0034-y
16	AravkinA Y,BaraldiR,OrbanD.A proximal quasi-Newton trust-region method for nonsmooth regularized optimization[J].SIAM Journal on Optimization,2022,32(2):900-929. doi: 10.1137/21M1409536
17	XuP,RoostaF,MahoneyM W.Newton-type methods for non-convex optimization under inexact Hessian information[J].Mathematical Programming,2020,25(3):78-92.
18	ZhangY,ZhangN,SunD,et al.An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems[J].Mathematical Programming,2020,179,223-263. doi: 10.1007/s10107-018-1329-6
19	WangF,CaoW,XuZ.Convergence of multi-block Bregman ADMM for nonconvex composite problems[J].Science China Information Sciences,2018,61(12):122-148.
20	BaiJ,HagerW W,ZhangH.An inexact accelerated stochastic ADMM for separable convex optimization[J].Computational Optimization and Applications,2022,81,479-518. doi: 10.1007/s10589-021-00338-8
21	BaiJ,ChangX,LiJ,et al.Convergence revisit on generalized symmetric ADMM[J].SIAM Journal on Optimization,2021,70,149-168.
22	BaiJ,LiJ,XuF,et al.Generalized symmetric ADMM for separable convex optimization[J].Computational Optimization and Applications,2018,70,129-170. doi: 10.1007/s10589-017-9971-0
23	CartisC,GouldN,TointP L.Adaptive cubic regularisation methods for unconstrained optimization. Part Ⅱ: Worst-case function-and derivative-evaluation complexity[J].Mathematical Programming,2011,127(2):295-319.
24	CartisC,GouldN,TointP L.Complexity bounds for second-order optimality in unconstrained optimization[J].Journal of Complexity,2012,28(1):93-108. doi: 10.1016/j.jco.2011.06.001
25	MoréJ J,SorensenD C.Computing a trust region step[J].SIAM Journal on Scientific Computing,1983,4(3):553-572. doi: 10.1137/0904038
26	SteihaugT.The conjugate gradient method and trust regions in large scale optimization[J].SIAM Journal on Numerical Analysis,1983,20(3):626-637. doi: 10.1137/0720042
27	GoldsteinT,O'DonoghueB,SetzerS,et al.Fast alternating direction optimization methods[J].SIAM Journal on Imaging Sciences,2014,7(3):1588-1623. doi: 10.1137/120896219
28	CartisC,GouldN,TointP L.On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming[J].SIAM Journal on Optimization,2011,21(4):1721-1739. doi: 10.1137/11082381X

$ {{f_i}(a_i^{\top}x)} $	$ {\nabla _x}{f_i}(a_i^{\top}x) $	$ \nabla _x^2{f_i}(a_i^{\top}x) $	$ M $
$ {\left( {\frac{1}{{1 + {{\rm e}^{ - a_i^{\top}x}}}} - {b_i}} \right)^2} $	$ \frac{{2a_i^{\top}{{\rm e}^{ - a_i^{\top}x}}}}{{{{\left( {1 + {{\rm e}^{ - a_i^{\top}x}}} \right)}^2}}}\left( {\frac{1}{{1 + {{\rm e}^{ - a_i^{\top}x}}}} - {b_i}} \right) $	$ \frac{{{{\rm{e}}^{ - a_i^{\top}x}}\left( {{{\rm{e}}^{ - a_i^{\top}x}} - 1} \right)}}{{{{\left( {1{\rm{ + }}{{\rm{e}}^{ - a_i^{\top}x}}} \right)}^3}}}{a_i}a_i^{\top} $	$ 2{\left\\| {{a_i}} \right\\|^2} $

Name	Type	Class	Testing size	Feature
leukemia	classification	2	34	7 129
w8a	classification	2	49 749	301
a9a	classification	2	16 280	123
mnist	classification	10	60 000	781
kr-vs-kp	classification	2	3 196	37

名称	精确Hessian矩阵	近似Hessian矩阵
leukemia	8 247.61	6 629.79
w8a	613.10	28.97
a9a	71.35	7.55
mnist	10 423.89	56.97
kr-vs-kp	3.09	1.40

训练集	算法	迭代次数	$ T $/s
kr-vs-kp	二阶分裂算法	15	1.67
	ACR	35	1.88
leukemia	二阶分裂算法	60	6 629.79
	ACR	34	2 972.72
w8a	二阶分裂算法	17	28.69
	ACR	821	28.42
a9a	二阶分裂算法	45	10.14
	ACR	179	12.65

[1]	Maoran WANG, Xingju CAI, Zhongming WU, Deren HAN. First-order splitting algorithm for multi-model traffic equilibrium problems [J]. Operations Research Transactions, 2023, 27(2): 63-78.
[2]	LIU Pengjie, JIANG Xianzhen, SONG Dan. A class of spectral conjugate gradient method with sufficient descent property [J]. Operations Research Transactions, 2022, 26(4): 87-97.
[3]	Huiling ZHANG, Naoerzai SAI, Xiaoyun WU. Modified PRP conjugate gradient method for unconstrained optimization [J]. Operations Research Transactions, 2022, 26(2): 64-72.
[4]	Xiquan SHAN, Meixia LI, Jinyu LIU. Smoothing Newton method for the tensor stochastic complementarity problem [J]. Operations Research Transactions, 2022, 26(2): 128-136.
[5]	Liyuan CUI, Shouqiang DU. Projected Levenberg-Marquardt method for stochastic R₀ tensor complementarity problems [J]. Operations Research Transactions, 2021, 25(4): 69-79.
[6]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[7]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.
[8]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[9]	. A sufficient descent conjugate gradient method for nonlinear unconstrained optimization problems [J]. Operations Research Transactions, 2018, 22(3): 59-68.
[10]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[11]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.
[12]	TIAN Zhaowei, ZHANG Liwei. A look at the convergence of the augmented Lagrange method for nondifferentiable convex programming from the view of a gradient method with constant stepsize [J]. Operations Research Transactions, 2017, 21(1): 111-117.
[13]	HANG Dan, YAN Shijian. Convergence of nonmonotonic Perry-Shanno's memoryless quasi-Newton method with parameters [J]. Operations Research Transactions, 2016, 20(4): 85-92.
[14]	MA Guodong, JIAN Jinbao. A feasible sequential systems of linear equations algorithm for inequality constrained optimization [J]. Operations Research Transactions, 2015, 19(4): 48-58.
[15]	WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization [J]. Operations Research Transactions, 2014, 18(3): 1-12.

A second-order splitting method with its application

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 28

Related Articles 15

Recommended Articles

Metrics

Comments