English

运筹学学报 >

2022 , Vol. 26 >Issue 2: 16 - 30

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

 

随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

展开
  • 1. 重庆师范大学数学科学学院，重庆 401331
    2. 重庆师范大学计算机与信息科学学院，重庆 401331
罗洪林  E-mail: luohonglin@cqnu.edu.cn

收稿日期: 2021-03-08

  网络出版日期: 2022-05-27

基金资助

国家自然科学基金(11991024);国家自然科学基金(11771064);重庆市高校创新研究群体项目(CXQT20014);重庆市创新领军人才项目团队(CQYC20210309536);重庆市科技局(cstc2021jcyj-msx300)

收起

A stochastic Bregman ADMM with its application in training sparse structure SVMs

Expand
  • 1. School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China
    2. School of Computer and Information Science, Chongqing Normal University, Chongqing 401331, China

Received date: 2021-03-08

  Online published: 2022-05-27

Fold

摘要

针对具有多块可分结构的非凸优化问题提出了一类新的随机Bregman交替方向乘子法，在周期更新规则下, 证明了该算法的渐进收敛性; 在随机更新的规则下, 几乎确定的渐进收敛性得以证明。数值实验结果表明, 该算法可有效训练具有离散结构的支持向量机。

关键词： 多块可分离的非凸优化问题; Bregman度量; 随机交替方向乘子法; 渐进收敛性; 支持向量机

本文引用格式

吕袈豪, 罗洪林, 杨泽华, 彭建文 . 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用[J]. 运筹学学报, 2022 , 26(2) : 16 -30 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.002

Abstract

A new stochastic Bregman multiplier alternating direction method (S-B-ADMM) is proposed for non-convex optimization problems with multiple separable blocks. It is shown that the sequence produced by the S-B-ADMM under the periodic update rule converges asymptotically to a stationary solution of the Lagrangian function of the original problem. Under the random update rule, we prove the almost surely convergence of the sequence produced by the S-B-ADMM. Numerical experiments results illustrate the feasibility of the S-B-ADMM for training sparse structural support vector machines.

Key words： non-convex optimization problems with multiple separable blocks; Bregman divergence; stochastic ADMM; asymptotic convergence; support vector machine

参考文献

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 (2): 41- 76.
2 Gabay D , Mercier B . A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers and 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 Huebner N, Rink Y, Suriyah M, et al. Distributed AC-DC optimal power flow in the european transmission grid with ADMM[C]//The 55th International Universities Power Engineering Conference (UPEC), 2020: 1-6.
5 Schizas I , Ribeiro A , Giannakis G . Consensus in ad hoc WSNS with noisy links-parti: Distributed estimation of deterministic signals[J]. IEEE Journal of Selected Topics in Signal Processing, 2008, 56 (3): 350- 364.
6 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.
7 何炳生. 凸优化和单调变分不等式收缩算法的统一框架[J]. 中国科学, 2018, 48 (02): 4- 21.
8 Yang L , Pong T K , Chen X . An alternating direction method of multipliers for nonconvex background/foreground extraction[J]. Frontiers of Mathematics in China, 2012, 4 (2): 1- 22.
9 Xu Y , Yin W , Wen Z , et al. An alternating direction algorithm for matrix completion with nonnegative factors[J]. Frontiers of Mathematics in China, 2012, 7 (2): 365- 384.
10 Forero P A , Cano A , Giannakis G B . Distributed clustering using wireless sensor networks[J]. IEEE Journal of Selected Topics in Signal Processing, 2011, 5 (4): 707- 724.
11 Liavas A P , Sidiropoulos N D . Parallel algorithms for constrained tensor factorization via the alternating direction method of multipliers[J]. IEEE Transactions on Signal Processing, 2014, 63 (20): 50- 63.
12 Wen Z , Yang C , Liu X , et al. Alternating direction methods for classical and ptychographic phase retrieval[J]. Inverse Problems, 2012, 28 (11): 115- 132.
13 Xu Y , Yin W , Wen Z , et al. An alternating direction algorithm for matrix completion with nonnegative factors[J]. Frontiers of Mathematics in China, 2012, 7 (2): 365- 384.
14 Hong M , Luo Z Q , Razaviyayn M . Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems[J]. SIAM Journal on Optimization, 2014, 26 (1): 3836- 3840.
15 Liu M , Jian J . An ADMM-based SQP method for separably smooth nonconvex optimization[J]. Journal of Inequalities and Applications, 2020, 12 (1): 2- 17.
16 Themelis A , Patrinos P . Douglas-Rachford splitting and ADMM for nonconvex optimization: Tight convergence results[J]. SIAM Journal on Optimization, 2020, 30 (1): 149- 181.
17 Bai J , Li J , Xu F , et al. Generalized symmetric ADMM for separable convex optimization[J]. Computational Optimization and Applications, 2017, 70 (1): 129- 170.
18 张艳娜, 申远, 孙黎明. 求解结构型优化问题的随机步长ADMM下降算法[J]. 工程数学学报, 2019, 36 (002): 123- 137.
19 Chao M , Deng Z , Jian J . Convergence of Linear Bregman ADMM for Nonconvex and Nonsmooth Problems with Nonseparable Structure[J]. Complexity, 2020, 26 (02): 1- 14.
20 Wang F , Cao W , Xu Z B . Convergence of multi-block Bregman ADMM for nonconvex composite problems[J]. Science China Information Sciences, 2018, 61 (12): 122- 148.
21 Bertsekas D P , Tsitsiklis J N . Neuro-Dynamic Programming[M]. BelBmont: Athena Scientific, 1996.
22 Tsochantaridis I , Joachims T , Hofmann T , et al. Large margin methods for structured and interdependent output variables[J]. Journal of Machine Learning Research, 2006, 6 (2): 1453- 1484.
23 Balamurugan P, Posinasetty A, Shevade S. ADMM for training sparse structural SVMs with augmented l1 regularizers[C]//SIAM International Conference on Data Mining, 2016: 684-692.
24 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.
Options
文章导航

/

〈 〉