二阶分裂算法及其应用

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

摘要/Abstract

摘要：

本文针对一类大规模可分非凸优化问题, 结合三次正则化和信赖域方法求解子问题, 同时利用非精确Hessian信息提出二阶分裂算法, 证明了算法的全局收敛性, 并刻画了算法的复杂度$ O\left( {{\varepsilon ^{ - 2}}}\right)$。应用该算法求解机器学习中的一类非凸二元分类问题, 数值实验结果验证了算法的有效性。

关键词: 大规模可分非凸优化, 二阶分裂算法, 非精确Hessian信息, 全局收敛性, 算法复杂度, 非凸二元分类问题

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

中图分类号:

O221.2
O224

谭子琳, 罗洪林. 二阶分裂算法及其应用[J]. 运筹学学报（中英文）, 2025, 29(4): 121-140.

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

图/表 7

表1

表2

图1

表3

图2

图3

表4

参考文献 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]	刘鹏杰, 江羡珍, 宋丹. 一类具有充分下降性的谱共轭梯度法[J]. 运筹学学报, 2022, 26(4): 87-97.
[2]	单锡泉, 李梅霞, 刘瑾瑜. 求解张量随机互补问题的光滑牛顿算法[J]. 运筹学学报, 2022, 26(2): 128-136.
[3]	张慧玲, 赛·闹尔再, 吴晓云. 修正PRP共轭梯度方法求解无约束最优化问题[J]. 运筹学学报, 2022, 26(2): 64-72.
[4]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[5]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[6]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[7]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[8]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[9]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[10]	万龙. 有关单机两代理排序问题的两个结果[J]. 运筹学学报, 2015, 19(2): 54-60.
[11]	万龙. 二阶数乘问题的一个最优算法[J]. 运筹学学报, 2014, 18(3): 99-103.
[12]	赵奇, 张燕. 求解极小极大问题的非单调过滤算法[J]. 运筹学学报, 2012, 16(2): 91-104.
[13]	张雨浓, 李学忠, 张智军, 李钧. 一种基于LVI求解二次规划问题的数值算法[J]. 运筹学学报, 2012, 16(1): 21-30.
[14]	简金宝, 韦小鹏, 曾汉君, 潘华琴. 一般约束优化基于识别函数的模松弛算法[J]. 运筹学学报, 2011, 15(2): 28-44.