English

运筹学学报 >

2015 , Vol. 19 >Issue 3: 57 - 70

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

运筹学

修正乘子交替方向法求解三个可分离算子的凸优化

展开
  • 1. 南京大学数学系, 南京, 210093； 2. 南京大学管理科学与工程国际研究中心, 南京, 210093

收稿日期: 2015-05-03

  网络出版日期: 2015-09-15

基金资助

 国家自然科学基金(No.11471156)

收起

Modified alternating directions method of multipliers for convex optimization with three separable functions

Expand
  • 1. Department of Mathematics, Nanjing University, Nanjing 210093, China; 2. International Centre of Management Science and Engineering, Nanjing University, Nanjing 210093, China

Received date: 2015-05-03

  Online published: 2015-09-15

Fold

摘要

指出直接推广的经典乘子交替方向法对三个算子的问题不能保证收敛的原因, 并且给出将其改造成收敛算法的相应策略. 同时, 在一个统一框架下, 证明了修正的乘子交替方向法的收敛性和遍历意义下具有O(1/t)~收敛速率.

关键词： 凸优化; 分裂收缩算法; 变分不等式; 统一框架; 收敛速率

本文引用格式

何炳生 . 修正乘子交替方向法求解三个可分离算子的凸优化[J]. 运筹学学报, 2015 , 19(3) : 57 -70 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.03.008

Abstract

In this paper, we indicate the reason of divergence, and illustrate the strategies which modify the alternating direction method of multipliers (ADMM) to a convergent one for the linearly constrained separable convex optimization with three individual functions. Finally, using a uniform framework, we give the simple proofs for the convergence and O(1/t) convergence rate in the ergodic sense of the ADMM-like methods.

Key words： convex optimization; splitting contraction methods; variational inequality; uniform framework; convergence rate

参考文献

Gabay D, Applications of the method of multipliers to variational inequalities, Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems, edited by M. Fortin and R. Glowinski, North Holland, Amsterdam, The Netherlands, 1983: 299-331.
Glowinski R, Numerical Methods for Nonlinear Variational Problems [M]. New York: Springer-Verlag, 1984.


何炳生. 凸优化和单调变分不等式的收缩算法 [EB/OL]. [2015-04-10].http://math.nju.edu.cn/\ \\hebma.

Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers [J]. Foun Trends Mach Learn, 2010, 3: 1-122.
He B S, Yuan X M. On the O(1/n) convergence rate of the alternating direction method [J]. SIAM J. Numerical Analysis, 2012, 50: 700-709.

He B S, Yuan X M. On non-ergodic convergence rate of Douglas-Rachford alternating directions method of multipliers [J]. Numerische Mathematik.

Chen C H, He B S, Ye Y Y, et al.  The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent [J]. to appear in Mathematical Programming, Series A.
 He B S, Tao M, Yuan X M. Alternating direction method with Gaussian back substitution for separable convex programming [J]. SIAM Journal on Optimization, 2012, 22: 313-340.
 He B S, Tao M, Yuan X M. A splitting method for separable convex programming [J]. IMA Journal of Numerical Analysis, 2015, 31: 394-426.
 Esser E, M\"oller M, Osher S, et al. A convex model for non-negative matrix factorization and dimensionality reduction on physical space [J]. IEEE Trans. Imag. Process., 2012, 21(7): 3239-3252.

何炳生. 凸优化的一阶分裂算法---变分不等式为工具的统一框架 [EB/OL]. [2015-04-10]. http://\\ math.nju.edu.cn/\ {}hebma.

He B S, Liu H, Wang Z R, et al. A strictly contractive Peaceman-Rachford splitting method for convex programming [J]. SIAM Journal on Optimization, 2014, 24: 1011-1040.

 
Options
文章导航

/

〈 〉