Journal of the Operations Research Society of China >

2019 , Vol. 7 >Issue 2: 195 - 204

DOI: https://doi.org/10.1007/s40305-019-00249-w

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

Expand
  • 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 date: 2018-08-23

  Revised date: 2019-04-25

  Online published: 2019-06-30

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.

Fold

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

Cite this article

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 . DOI: 10.1007/s40305-019-00249-w

References

[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)
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016