Shannon Criteria

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.

Basic idea

We consider a saddle point problem of the form

$\left(\begin{array}{cc}A& B\\ B^{*}& \end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}{b}_1\\ b_2\end{array}\right),$

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

$\left(\begin{array}{cc}A& B\\ & -S\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}{b}_1\\ b_2-B^{*}{A}^{-1}{b}_1\end{array}\right),$

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

We start the conjugate gradient iteration by computing the residual

$r_2:=b_2-B^{*}{A}^{-1}{b}_1-S{x}_2=b_2-B^{*}{A}^{-1}(b_1-B{x}_2)=b_2-B^{*}{x}_1,$

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,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,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

If solving the linear system $Ax=b$ exactly is not feasible, inexact solvers can be applied.

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

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