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
( A B B ∗ ) ( x 1 x 2 ) = ( b 1 b 2 ) , {\displaystyle {\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 {\displaystyle A} is a symmetric positive-definite matrix. Multiplying the first row by B ∗ A − 1 {\displaystyle B^{*}A^{-1}} and subtracting from the second row yields the upper-triangular system
( A B − S ) ( x 1 x 2 ) = ( b 1 b 2 − B ∗ A − 1 b 1 ) , {\displaystyle {\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 {\displaystyle S:=B^{*}A^{-1}B} denotes the Schur complement. Since S {\displaystyle S} is symmetric positive-definite, we can apply standard iterative methods like the gradient descent method or the conjugate gradient method to solve
S x 2 = B ∗ A − 1 b 1 − b 2 {\displaystyle Sx_{2}=B^{*}A^{-1}b_{1}-b_{2}}
in order to compute x 2 {\displaystyle x_{2}} . The vector x 1 {\displaystyle x_{1}} can be reconstructed by solving
A x 1 = b 1 − B x 2 . {\displaystyle Ax_{1}=b_{1}-Bx_{2}.\,}
It is possible to update x 1 {\displaystyle x_{1}} alongside x 2 {\displaystyle 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
… excerpt ends here. Continue reading the full article.
