Convergence of a Class of Stationary Iterative Methods for Saddle Point Problems

doi:10.1007/s40305-019-00249-w

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (2): 195-204.doi: 10.1007/s40305-019-00249-w

所属专题： Continuous Optimization

收稿日期:2018-08-23 修回日期:2019-04-25 出版日期:2019-06-30 发布日期:2019-06-30
通讯作者: Yin Zhang E-mail:yinzhang@cuhk.edu.cn,yzhang@rice.edu

Convergence of a Class of Stationary Iterative Methods for Saddle Point Problems

Yin Zhang^1,2

1 Institute for Data and Decision Analytics, The Chinese University of Hong Kong, Shenzhen 518172, China;
2 Department of Computational and Applied Mathematics, Rice University, Houston 77005, United States of America

Received:2018-08-23 Revised:2019-04-25 Online:2019-06-30 Published:2019-06-30
Contact: Yin Zhang E-mail:yinzhang@cuhk.edu.cn,yzhang@rice.edu
Supported by:
This paper is a polished version of the Rice University technical report CAAMTR10-24, which was a work supported in part by the National Natural Science Foundation (No. DMS-0811188) and Office of Navy Research (No. N00014-08-1-1101). It was later also supported in part by a research Grant administrated by the Shenzhen Research Institute of Big Data. The wording in this abstract, as in some other places, has been modified from the original version. All cited publications appear prior to the year 2011.

摘要/Abstract

Abstract: A unified convergence theory is derived for a class of stationary iterative methods for solving linear equality constrained quadratic programs or saddle point problems. This class is constructed from essentially all possible splittings of the submatrix residing in the (1,1)-block of the augmented saddle point matrix that would produce non-expansive iterations. The classic augmented Lagrangian method and alternating direction method of multipliers are two special members of this class.

Key words: Saddle point problem, Quadratic program, Matrix splitting, Stationary iterations, Spectral radius, Q-linear convergence

中图分类号:

. [J]. Journal of the Operations Research Society of China, 2019, 7(2): 195-204.

Yin Zhang. Convergence of a Class of Stationary Iterative Methods for Saddle Point Problems[J]. Journal of the Operations Research Society of China, 2019, 7(2): 195-204.

参考文献 8

[1]	Benzi, M., Golub, G.H., Liesen, J.:Numerical solution of saddle point problems. Acta Numer. 14, 1-137(2005)
[2]	Hestenes, M.R.:Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303-320(1969)
[3]	Powell, M. J. D.:A method for nonlinear constraints in minimization problems. Optimization, R. Fletcher, ed., Academic Press, New York, NY, pp. 283-298(1969)
[4]	Uzawa, H.:Iterative methods for concave programming. In:Arrow, K.J., Hurwicz, L., Uzawa, H. (eds.) Studies in Linear and Nonlinear Programming, pp. 154-165. Stanford University Press, Stanford (1958)
[5]	Glowinski, R., Marrocco, A.:Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires. Rev. Francaise dAut. Inf. Rech. Oper. R-2, 41-76(1975)
[6]	Gabay, D., Mercier, B.:A dual algorithm for the solution of nonlinear variational problems via finiteelement approximations. Comput. Math. Appl. 2, 17-40(1976)
[7]	Zulehner, W.:Analysis of iterative methods for saddle point problems:a unified approach. Math. Comput. 71(238), 479-505(2001)
[8]	Zhang, J., Shang, J.:A class of Uzawa-SOR methods for saddle point problems. Appl. Math. Comput. 216, 2163-2168(2010)

Convergence of a Class of Stationary Iterative Methods for Saddle Point Problems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 8

相关文章 1

编辑推荐

Metrics

本文评价