• 论文 •

### 求鞍点问题的新的原始-对偶算法

1. 南京师范大学数学科学学院, 南京 210023
• 收稿日期:2016-01-31 出版日期:2016-09-15 发布日期:2016-09-08

Zhang Chun, Cai Xingju, Han Deren. A NEW PRIMAL-DUAL ALGORITHM FOR SOLVING SADDLE-POINT PROBLEMS[J]. Journal of Numerical Methods and Computer Applications, 2016, 37(3): 167-178.

### A NEW PRIMAL-DUAL ALGORITHM FOR SOLVING SADDLE-POINT PROBLEMS

Zhang Chun, Cai Xingju, Han Deren

1. School of Mathematical Science, Nanjing Normal University, Nanjing 210023, China
• Received:2016-01-31 Online:2016-09-15 Published:2016-09-08

The primal-dual hybrid gradient algorithm for solving saddle-point problems is very popular in recent years, due to its simplicity and efficiency in dealing with problems especially those arising from image processing. In this paper, we propose a modified primal-dual hybrid gradient algorithm, where in the primal and dual steps, we first move along the gradient direction, and then solve the same proximal subproblems to generate the next iteration. Under suitable conditions, we prove the global convergence of the algorithm. We also report some preliminary numerical results and compare it with some state-of-the-art primal-dual gradient algorithms, showing the competitiveness of the new algorithm.

MR(2010)主题分类:

()
 [1] Arrow K J, Hurwicz L and Uzawa H. With contributions by H.B. Chenery, S.M. Johnson, S. Karlin, T. Marschak, and R.M. Solow., Studies in Linear and Non-Linear Programming, volume II of Stanford Mathematical Studies in the Social Science, Stanford Unversity Press, Stanford, California, 1958.[2] Bonettini S and Ruggiero V. On the convergence of primal-dual hybrid gradient algorithms for total variation image restoration[J]. J. Math. Imaging Vis., 2012, 44(3): 236-253.[3] Cai X J, Han D R and Xu L L. An improved first-order primal-dual algorithm with a new correction step[J]. Journal of Global Optimization, 2013, 57(4): 1419-1428.[4] Cai X J. A note on PPA with asymmetric linear term[J]. Journal of Optimization Theory and Applications, Under Review.[5] Chambolle A and Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging[J]. J. Math. Imaging Vis., 2011, 40: 120-145.[6] Douglas J and Rachford H H. On the numerical solution of the heat conduction problem in 2 and 3 space variables[J]. Trans. Amer. Math. Soc., 1956, 82: 421-439.[7] Esser E, Zhang X and Chan T. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[J]. SIAM J. Imaging Sci., 2010, 3: 1015-1046.[8] Glowinski R and Marrocco A. Approximation par éléments finis d'ordre un et résolution par pénalisation-dualité d'une classe de problèmes non linéaires[J]. R.A.I.R.O., R21975, 41-76.[9] He B S and Yuan X M. Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective[J]. SIAM J. Imaging Sci., 2012, 5: 119-149.[10] He B S. PPA-like contraction methods for convex optimization: A framework using variational inequality approach. Journal of Operations Research Society of China, 2016.[11] Korpelevich G M. The extragradient method for finding saddle points and other problems[J]. Ekonomika i Matematchskie Metody, 1976, 12: 747-756.[12] Lions P L and Mercier B. Splitting algorithms for the sum of two nonlinear operators[J]. SIAM J. Num. Anal., 1979, 16: 964-979.[13] Martinet B. Regularization d'inequations variationelles par approximations successives[J]. Revue Francaise d'Informatique et de Recherche Opérationelle, 1970, 4: 154-159.[14] Popov L D. A modification of the Arrow-Hurwitz method of search for saddle points[J]. Mat. Zametki, 1980, 28(5): 777-784.[15] Rockafellar R T. Monotone operators and the proximal point algorithm[J]. SIAM J. Con. Optim., 1976, 14: 877-898.[16] Rudin L, Osher S and Fatemi E. Nonlinear total variation based noise removal algorithms[J]. Physica D, 1992, 60: 227-238.[17] Weiss P, Blanc-Feraud L and Aubert G. Efficient schemes for total variation minimization under constraints in image processing[J]. SIAM J. Sci. Comput., 2009, 31(3): 2047-2080.[18] Zhang X, Burger M and Osher S. A unified primal-dual algorithm framework based on Bregman iteration[J]. J. Sci. Comput., 2010, 46(1): 20-46.[19] Zhu M Q and Chan T. An efficient primal-dual hybrid gradient algorithm for total variation image restoration. CAM Reports 08-34, UCLA, 2008.
 [1] 廖平. Hermitian鞍点矩阵的特征值估计[J]. 数值计算与计算机应用, 2017, 38(2): 123-129. [2] 朱雪芳. 求解鞍点问题的一类广义SSOR预条件子[J]. 数值计算与计算机应用, 2014, 35(2): 117-124. [3] 张春敏, 　杨月婷. 两种混合共轭梯度法的全局收敛性[J]. 数值计算与计算机应用, 2012, 33(2): 92-98. [4] 董晓亮, 高岳林, 何郁波. 一类基于Armijo搜索的改进DY共轭梯度法及其全局收敛性[J]. 数值计算与计算机应用, 2011, 32(4): 253-258. [5] 刘金魁, 杜祥林, 屈娟. 一种新的三项梯度下降算法[J]. 数值计算与计算机应用, 2011, 32(4): 283-292. [6] 潘春平, 王红玉. 一种求解鞍点问题的广义预条件对称-反对称分裂迭代法[J]. 数值计算与计算机应用, 2011, 32(3): 174-182. [7] 张丽炜, 倪勤. 解非线性等式约束优化问题的新锥模型信赖域算法[J]. 数值计算与计算机应用, 2010, 31(4): 279-289. [8] 董晓亮, 李郴良, 何郁波. 一类修正的DY 共轭梯度法及其全局收敛性[J]. 数值计算与计算机应用, 2010, 31(1): 1-7. [9] 王俊仙, 胡齐芽, 舒适. 求解 Maxwell 线性元鞍点系统的基于 HX 预条件子的 Uzawa 算法[J]. 数值计算与计算机应用, 2009, 30(4): 305-314. [10] 刘金魁, 王开荣, 杜祥林, 贾松芳. 一种新的非线性共轭梯度法及收敛性[J]. 数值计算与计算机应用, 2009, 30(4): 247-254. [11] 赵景余, 张国凤, 常岩磊. 求解鞍点问题的一种新的结构算法[J]. 数值计算与计算机应用, 2009, 30(2): 138-142. [12] 莫降涛,顾能柱,韦增欣. 修正PRP共轭梯度法的全局收敛性及其数值结果[J]. 数值计算与计算机应用, 2007, 28(1): 56-62. [13] 邵新慧,沈海龙,李长军,张铁. 求解鞍点问题的一般加速超松弛方法[J]. 数值计算与计算机应用, 2006, 27(4): 241-248. [14] 喻高航,关履泰. 大规模优化问题的一个具有充分下降性的共轭梯度算法[J]. 数值计算与计算机应用, 2006, 27(3): 183-190. [15] 白中治,安恒斌. 关于Newton-GMRES方法的有效变型与全局收敛性研究[J]. 数值计算与计算机应用, 2005, 26(4): 291-300.