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.
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
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.
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
Inequality constraints can be incorporated, e.g., in order to handle obstacle problems.
- Uzawa, H. (1958). "Iterative methods for concave programming". In Arrow, K. J.; Hurwicz, L.; Uzawa, H. Studies in linear and nonlinear programming. Stanford University Press.
- Elman, H. C.; Golub, G. H. (1994). "Inexact and preconditioned Uzawa algorithms for saddle point problems". SIAM J. Num. Anal. 31 (6): 1645–1661. doi:10.1137/0731085.
- Bramble, J. H.; Pasciak, J. E.; Vassilev, A. T. (1997). "Analysis of the inexact Uzawa algorithm for saddle point problems". SIAM J. Num. Anal. 34 (3): 1072–1982. doi:10.1137/S0036142994273343.
- Zulehner, W. (1998). "Analysis of iterative methods for saddle point problems. A unified approach". Math. Comp. 71: 479–505. doi:10.1090/S0025-5718-01-01324-2.
- 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. 55. pp. 91–102. doi:10.1007/978-3-540-34469-8_8.