English

运筹学学报 >

2025 , Vol. 29 >Issue 4: 121 - 140

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.04.011

论文

二阶分裂算法及其应用

  • 谭子琳 ,
  • 罗洪林
展开
  • 1. 重庆师范大学数学科学学院, 重庆 401331
罗洪林  E-mail: luohonglin@cqnu.edu.cn

收稿日期: 2022-11-16

  网络出版日期: 2025-12-11

基金资助

国家自然科学基金(11991024);国家自然科学基金(11771064);重庆市创新领军人才团队项目(CQYC20210309536);重庆市高校创新研究群体项目(20A110029);重庆市自然科学基金(KJZD-K 202500507)

版权

运筹学学报编辑部, 2025, 版权所有，未经授权，不得转载。
收起

A second-order splitting method with its application

  • Zilin TAN ,
  • Honglin LUO
Expand
  • 1. School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China

Received date: 2022-11-16

  Online published: 2025-12-11

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

摘要

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

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

本文引用格式

谭子琳 , 罗洪林 . 二阶分裂算法及其应用[J]. 运筹学学报, 2025 , 29(4) : 121 -140 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.011

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

参考文献

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.
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.
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.
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.
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.
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.
13 NesterovY,PolyakB T.Cubic regularization of Newton method and its global performance[J].Mathematical Programming,2006,108(1):177-205.
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.
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.
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.
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.
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.
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.
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.
25 MoréJ J,SorensenD C.Computing a trust region step[J].SIAM Journal on Scientific Computing,1983,4(3):553-572.
26 SteihaugT.The conjugate gradient method and trust regions in large scale optimization[J].SIAM Journal on Numerical Analysis,1983,20(3):626-637.
27 GoldsteinT,O'DonoghueB,SetzerS,et al.Fast alternating direction optimization methods[J].SIAM Journal on Imaging Sciences,2014,7(3):1588-1623.
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.
Options
文章导航

/

〈 〉