广义交替近似梯度算法的线性收敛分析

运筹学学报 ›› 2014, Vol. 18 ›› Issue (3): 1-12.

• 运筹学 • 下一篇

广义交替近似梯度算法的线性收敛分析

万芮¹, 徐姿^1,*

1. 上海大学理学院数学系, 上海 200444

出版日期:2014-09-15 发布日期:2014-09-15
通讯作者: 徐姿 E-mail:xuzi@shu.edu.cn
基金资助:
国家自然科学基金资助项目(No. 11101261)

On the linear convergence of the general alternating proximal gradient method for convex minimization

WAN Rui¹, XU Zi^1,*

1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Online:2014-09-15 Published:2014-09-15

摘要/Abstract

摘要： 针对两个可分凸函数的和在线性约束下的极小化问题, 在交替方向法的框架下, 提出广义的交替近似梯度算法. 在一定的条件下, 该算法具有全局及线性收敛性. 数值实验表明该算法有好的数值表现.

关键词: 交替方向法, 广义交替近似梯度算法, 全局收敛, Q-线性收敛

Abstract: In this paper, we propose a general alternating proximal gradient method for linear constrained convex optimization problems with the objective containing two separable functions. Our method is based on the framework of alternating direction method of multipliers. The global and linear convergence of the proposed method is established under certain conditions. Numerical experiments show that the algorithm has good numerical performance.

Key words: alternating direction method of multipliers, general alternating proximal gradient method, global convergence, Q-linear convergence

中图分类号:

O224

万芮, 徐姿. 广义交替近似梯度算法的线性收敛分析[J]. 运筹学学报, 2014, 18(3): 1-12.

WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization[J]. Operations Research Transactions, 2014, 18(3): 1-12.

参考文献

Yang J, Zhang Y. Alternating direction algorithms for l_{1} problems in compressive sensing [J]. SIAM Journal on Scientific Computing, 2011, 33: 250-278.

Cand\grave{\rm e}s E J, Recht B. Exact matrix completion via convex optimization [J]. Foundations of Computational Mathematics, 2009, 9: 717-772.
Cand\grave{e}s E J, Tao T. The power of convex relaxation: near-optimal matrix completion [J]. IEEE Translations on Information Theory, 2009, 56: 2053-2080.
Yang J, Zhang Y. Alternating direction algorithms for l_{1} problems in compressive sensing [J]. SIAM Journal on Scientific Computing, 2011, 33: 250-278.
Qin Z W, Goldfarb D, Ma S Q. An alternating direction method for total variation denoising [EB/OL]. [2013-10-05]. http://arxiv.org/pdf/1108.1587.pdf.

Wang Y, Yang J, Yin W T, et al. A new alternating minimization algorithm for total variation image reconstruction [J]. SIAM Journal on Imaging Sciences, 2008, 1: 248-272.

Yuan X M. Alternating direction methods for sparse covariance selection selection [EB/OL]. [2013-09-10]. http://www.optimization-online.org/DB\_FILE/2009/09/2390.pdf

Goldfarb D, Ma S Q. Fast multiple splitting algorithms for convex optimization [J]. SIAM Journal on Optimization, 2012, 22(2): 533-556.
Goldfarb D, Ma S Q, Scheinberg K. Fast alternating linearization methods for minimizing the sum of two convex functions [J]. Mathematical Programming Series A, 2013, 141(1-2): 349-382.
Yang J, Zhang Y. Alternating direction algorithms for l_{1} problems in compressive sensing [J]. SIAM Journal on Scientific Computing, 2011, 33: 250-278.
He B S, Yuan X M. On non-ergodic convergence rate of douglas-rachford alternating direction method of multipliers multipliers [EB/OL]. [2013-10-07]. http://www.math.hkbu.edu.hk1-xmyuan/Paper/ADM-HY-Jan16.pdf.

Goldstein T, Donoghue B O, Setzer S, et al. Fast alternating direction optimization methods [R]. California: University of California, Los Angeles, 2012, 12-35.

Deng W, Yin W T. On the global and linear convergence of the generalized alternating direction method of multipliers [R]. State of Texas: Rice University, 2012, 12-14.

Ma S Q. Alternating proximal gradient method for convex minimization [EB/OL]. [2013-08-20]. http://www.optimization-online.org/DB\_FILE/2012/09/3608.pdf.

Zou H, Hastie T. Regularization and variable selection via the melastic net [J]. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2005, 67(2): 301-320.

[1]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[2]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[3]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[4]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[5]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[6]	冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30.
[7]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[8]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[9]	陈元媛, 高岩, 刘志敏, 杜守强. 一类特殊优化问题的光滑梯度法[J]. 运筹学学报, 2017, 21(2): 119-125.
[10]	田朝薇, 张立卫. 从常步长梯度方法的视角看不可微凸优化增广Lagrange方法的收敛性[J]. 运筹学学报, 2017, 21(1): 111-117.
[11]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[12]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[13]	卢越, 张继宏, 张立卫. 一类二次规划逆问题的交替方向数值方法[J]. 运筹学学报, 2014, 18(2): 1-16.
[14]	杜守强. Goldstein线搜索下Levenberg-Marquardt方法的全局收敛性[J]. 运筹学学报, 2012, 16(4): 105-111.
[15]	赵奇, 张燕. 求解极小极大问题的非单调过滤算法[J]. 运筹学学报, 2012, 16(2): 91-104.

广义交替近似梯度算法的线性收敛分析

On the linear convergence of the general alternating proximal gradient method for convex minimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价