next up previous
Next: Bibliography

Andrei Draganescu
Multigrid preconditioning of linear systems for interior point methods applied to a class of box-constrained optimal control problems

Department of Mathematics and Statistics
University of Maryland Baltimore County
Baltimore MD 21250
draga@umbc.edu
Cosmin Petra

In this work we construct and analyze multigrid preconditioners for operators of the form $ {\mathcal D}_{\lambda}+{\mathcal
K}_h^*{\mathcal K}_h$, where $ D_{\lambda}$ is the multiplication with a relatively ``smooth'' discrete function $ \lambda>0$ and $ {\mathcal K}_h$ is a discretization of a compact linear operator $ {\mathcal K}$. These systems arise when applying interior point methods to the distributed optimal control problem $ \min_u\frac{1}{2}(\vert\!\vert{\mathcal K}
u-f\vert\!\vert^2 +\beta\vert\!\vert u\vert\!\vert^2)$ with box constraints $ \underline{u}\leqslant u\leqslant\overline{u}$ on the control $ u$. The presented preconditioning technique is related to the one developed by Draganescu and Dupont in [1] for the associated unconstrained problem, and is intended for large-scale problems. As in [1], the quality of the resulting preconditioners is shown to increase as the resolution $ h\downarrow 0$ at a rate that is optimal with respect to $ h$ if the meshes are uniform, but decreases as the smoothness of $ \lambda$ declines. We test this algorithm first on a Tikhnov-regularized backward parabolic equation with $ [0,1]$ constraints and then on the elliptic-constrained optimization problem

\begin{displaymath}\begin{array}{cc}\vspace{7pt}
\textnormal{minimize}& \frac{1}...
...line{u} \leqslant u \leqslant \overline{u}\
\ a.e.
\end{array}\end{displaymath}      

In both cases it is shown that the number of linear iterations per optimization step, as well as the total number of fine-scale matrix-vector multiplications is decreasing with increasing resolution, thus showing the method to be potentially very efficient for truly large-scale problems.

This is joint work with Cosmin Petra from the Argonne National Laboratory.




next up previous
Next: Bibliography
root 2010-03-02