二阶分裂算法及其应用

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.

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

参考文献

[1] Glowinski R, Marroco A. 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] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation [J]. Computers Mathematics with Applications, 1976, 2(1): 17-40.
[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] Yang Q, Chen G, Wang T. 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.
[5] Schizas D, Ribeiro A, Giannakisg B. Consensus in ad hoc WSNs with noisy links-part I: Distributed estimation of deterministic signals [J]. IEEE Transactions on Signal Processing, 2008, 56(1): 350-364.
[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] Kan K, Fung S W, Ruthotto L. PNKH-B: A projected newton|Krylov method for large-scale bound-constrained optimization [J]. SIAM Journal on Scientific Computing, 2021, 43(5): 704- 726.
[9] Wang F H, Cao W F, Xu Z B. Convergence of multi-block Bregman ADMM for nonconvex composite problems [J] . Science China (Information Sciences), 2018, 61(12): 1-12.
[10] Curtis F E, Robinson D P, Royer C W, et al. Trust-region Newton-CG with strong secondorder complexity guarantees for nonconvex optimization [J]. SIAM Journal on Optimization, 2021, 31(1): 518-544.
[11] Gould N I, Robinson D P, Thorne H S. On solving trust-region and other regularised subproblems in optimization [J]. Mathematical Programming, 2010, 2(1): 21-57.
[12] Hazan E, Koren T. A linear-time algorithm for trust region problems [J]. Mathematical Programming, 2016, 158(1-2): 363-381.
[13] Nesterov Y, Polyak B T. Cubic regularization of Newton method and its global performance [J]. Mathematical Programming, 2006, 108(1): 177-205.
[14] Cartis C, Gould N, Toint P L. Adaptive cubic regularisation methods for unconstrained optimization, Part I: Motivation, convergence and numerical results [J]. Mathematical Programming, 2011, 127(2): 245-295.
[15] Jiang B, Lin T, Ma S, et al. Structured nonconvex and nonsmooth optimization: Algorithms and iteration complexity analysis [J]. Computational Optimization and Applications, 2019, 72: 115-157.
[16] Aravkin A Y, Baraldi R, Orban D. A proximal quasi-Newton trust-region method for nonsmooth regularized optimization [J]. SIAM Journal on Optimization, 2022, 32(2): 900-929.
[17] Xu P, Roosta F, Mahoney M W. Newton-type methods for non-convex optimization under inexact Hessian information [J]. Mathematical Programming, 2020, 25(3): 78-92.
[18] Zhang Y, Zhang N, Sun D, et al. An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems [J]. Mathematical Programming, 2020, 179: 223-263.
[19] Wang F, Cao W, Xu Z. Convergence of multi-block Bregman ADMM for nonconvex composite problems [J]. Science China Information Sciences, 2018, 61(12): 122-148.
[20] Bai J, Hager W W, Zhang H. An inexact accelerated stochastic ADMM for separable convex optimization [J]. Computational Optimization and Applications, 2022, 81: 479-518.
[21] Bai J, Chang X, Li J, et al. Convergence revisit on generalized symmetric ADMM [J]. SIAM Journal on Optimization, 2021, 70: 149-168.
[22] Bai J, Li J, Xu F, et al. Generalized symmetric ADMM for separable convex optimization [J]. Computational Optimization and Applications, 2018, 70: 129-170.
[23] Cartis C, Gould N, Toint P L. Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function-and derivative-evaluation complexity [J]. Mathematical Programming, 2011, 127(2): 295-319.
[24] Cartis C, Gould N, Toint P L. Complexity bounds for second-order optimality in unconstrained optimization [J]. Journal of Complexity, 2012, 28(1): 93-108.
[25] Moré J J, Sorensen D C. Computing a trust region step [J]. SIAM Journal on Scientific Computing, 1983, 4(3): 553-572.
[26] Steihaug T. The conjugate gradient method and trust regions in large scale optimization [J]. SIAM Journal on Numerical Analysis, 1983, 20(3): 626-637.
[27] Goldstein T, O’Donoghue B, Setzer S, et al. Fast alternating direction optimization methods [J]. SIAM Journal on Imaging Sciences, 2014, 7(3): 1588-1623.
[28] Cartis C, Gould N, Toint P 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.