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

Abstract

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

CLC Number:

O224

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.

References

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]	LI Chaoqiong, LI Feng. A partial parallel splitting LQP alternating direction method of multipliers for solving monotone variational inequalities [J]. Operations Research Transactions, 2020, 24(1): 101-114.
[2]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.
[3]	. A sufficient descent conjugate gradient method for nonlinear unconstrained optimization problems [J]. Operations Research Transactions, 2018, 22(3): 59-68.
[4]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[5]	JIAN Jinbao, LAO Yixian, CHAO Miantao, MA Guodong. ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization [J]. Operations Research Transactions, 2018, 22(2): 79-92.
[6]	YANG Junfeng. An algorithmic review for total variation regularized data fitting problems in image processing [J]. Operations Research Transactions, 2017, 21(4): 69-83.
[7]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.
[8]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[9]	TIAN Zhaowei, ZHANG Liwei. A look at the convergence of the augmented Lagrange method for nondifferentiable convex programming from the view of a gradient method with constant stepsize [J]. Operations Research Transactions, 2017, 21(1): 111-117.
[10]	HANG Dan, YAN Shijian. Convergence of nonmonotonic Perry-Shanno's memoryless quasi-Newton method with parameters [J]. Operations Research Transactions, 2016, 20(4): 85-92.
[11]	MA Guodong, JIAN Jinbao. A feasible sequential systems of linear equations algorithm for inequality constrained optimization [J]. Operations Research Transactions, 2015, 19(4): 48-58.
[12]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.
[13]	DU Shouqiang. Global convergence of the Levenberg-Marquardt method with Goldstein line search [J]. Operations Research Transactions, 2012, 16(4): 105-111.
[14]	ZHAO Qi, ZHANG Yan. A Nonmonotoe Filter Method For Minimax Problems [J]. Operations Research Transactions, 2012, 16(2): 91-104.
[15]	ZHANG Yu-Nong, LI Xue-Zhong, ZHANG Zhi-Jun, LI Jun. An LVI-based Numerical Algorithm for Solving Quadratic Programming Problems [J]. Operations Research Transactions, 2012, 16(1): 21-30.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments