In numerical mathematics, the Uzawa iteration is an algorithm for solving saddle point problems. It is named after Hirofumi Uzawa and was originally introduced in the context of concave programming.[1]

Basic idea

edit

We consider a saddle point problem of the form

 

where   is a symmetric positive-definite matrix. Multiplying the first row by   and subtracting from the second row yields the upper-triangular system

 

where   denotes the Schur complement. Since   is symmetric positive-definite, we can apply standard iterative methods like the gradient descent method or the conjugate gradient method to solve

 

in order to compute  . The vector   can be reconstructed by solving

 

It is possible to update   alongside   during the iteration for the Schur complement system and thus obtain an efficient algorithm.

Implementation

edit

We start the conjugate gradient iteration by computing the residual

 

of the Schur complement system, where

 

denotes the upper half of the solution vector matching the initial guess   for its lower half. We complete the initialization by choosing the first search direction

 

In each step, we compute

 

and keep the intermediate result

 

for later. The scaling factor is given by

 

and leads to the updates

 

Using the intermediate result   saved earlier, we can also update the upper part of the solution vector

 

Now we only have to construct the new search direction by the Gram–Schmidt process, i.e.,

 

The iteration terminates if the residual   has become sufficiently small or if the norm of   is significantly smaller than   indicating that the Krylov subspace has been almost exhausted.

Modifications and extensions

edit

If solving the linear system   exactly is not feasible, inexact solvers can be applied.[2][3][4]

If the Schur complement system is ill-conditioned, preconditioners can be employed to improve the speed of convergence of the underlying gradient method.[2][5]

Inequality constraints can be incorporated, e.g., in order to handle obstacle problems.[5]

References

edit
  1. ^ Uzawa, H. (1958). "Iterative methods for concave programming". In Arrow, K. J.; Hurwicz, L.; Uzawa, H. (eds.). Studies in linear and nonlinear programming. Stanford University Press.
  2. ^ a b Elman, H. C.; Golub, G. H. (1994). "Inexact and preconditioned Uzawa algorithms for saddle point problems". SIAM J. Numer. Anal. 31 (6): 1645–1661. CiteSeerX 10.1.1.307.8178. doi:10.1137/0731085.
  3. ^ Bramble, J. H.; Pasciak, J. E.; Vassilev, A. T. (1997). "Analysis of the inexact Uzawa algorithm for saddle point problems". SIAM J. Numer. Anal. 34 (3): 1072–1982. CiteSeerX 10.1.1.52.9559. doi:10.1137/S0036142994273343.
  4. ^ Zulehner, W. (1998). "Analysis of iterative methods for saddle point problems. A unified approach". Math. Comp. 71 (238): 479–505. doi:10.1090/S0025-5718-01-01324-2.
  5. ^ a b Gräser, C.; Kornhuber, R. (2007). "On Preconditioned Uzawa-type Iterations for a Saddle Point Problem with Inequality Constraints". Domain Decomposition Methods in Science and Engineering XVI. Lec. Not. Comp. Sci. Eng. Vol. 55. pp. 91–102. CiteSeerX 10.1.1.72.9238. doi:10.1007/978-3-540-34469-8_8. ISBN 978-3-540-34468-1.

Further reading

edit