Uzawa iteration

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

 \begin{pmatrix} A & B\\ B^* & \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix}
         = \begin{pmatrix} b_1\\ b_2 \end{pmatrix},

where A is a symmetric positive-definite matrix. Multiplying the first row by B^* A^{-1} and subtracting from the second row yields the upper-triangular system

 \begin{pmatrix} A & B\\ & -S \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix}
         = \begin{pmatrix} b_1\\ b_2 - B^* A^{-1} b_1 \end{pmatrix},

where S := B^* A^{-1} B denotes the Schur complement. Since S is symmetric positive-definite, we can apply standard iterative methods like the gradient descent method or the conjugate gradient method to

 S x_2 = B^* A^{-1} b_1 - b_2

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

 A x_1 = b_1 - B x_2. \,

It is possible to update x_1 alongside x_2 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

 r_2 := B^* A^{-1} b_1 - b_2 - S x_2 = B^* A^{-1} (b_1 - B x_2) - b_2 = B^* x_1 - b_2,

of the Schur complement system, where

 x_1 := A^{-1} (b_1 - B x_2)

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

 p_2 := r_2.\,

In each step, we compute

 a_2 := S p_2 = B^* A^{-1} B p_2 = B^* p_1

and keep the intermediate result

 p_1 := A^{-1} B p_2

for later. The scaling factor is given by

 \alpha := p_2^* r_2 / p_2^* a_2

and leads to the updates

 x_2 := x_2 + \alpha p_2, \quad r_2 := r_2 - \alpha a_2.

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

 x_1 := x_1 - \alpha p_1.\,

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

 \beta := r_2^* a_2 / p_2^* a_2,\quad p_2 := r_2 - \beta p_2.

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

Modifications and extensions[edit]

If solving the linear system A x=b 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. 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. Num. Anal. 31 (6): 1645–1661. 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. Num. Anal. 34 (3): 1072–1982. doi:10.1137/S0036142994273343. 
  4. ^ 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. 
  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. 55. pp. 91–102. doi:10.1007/978-3-540-34469-8_8. 

Further reading[edit]