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.
Contents
Basic idea
We consider a saddle point problem of the form
where
where
in order to compute
It is possible to update
Implementation
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
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
Now we only have to construct the new search direction by the Gram–Schmidt process, i.e.,
The iteration terminates if the residual
Modifications and extensions
If solving the linear system
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.