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{array}{cc}\vspace{7pt} \textnormal{minimize}& \frac{1}... ...line{u} \leqslant u \leqslant \overline{u}\ \ a.e. \end{array}$$

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.