Andrei Draganescu
Optimal-order multigrid preconditioners for linear systems arising in the semi-smooth Newton solution of certain PDE-constrained optimization problems

Department of Mathematics and Statistics
UMBC
1000 Hilltop Circle
Baltimore
MD 21250
draga@umbc.edu
Jyoti Saraswat

We present a new technique for constructing multigrid preconditioners arising in the semi-smooth Newton solution process of optimization problems of the form

$$\min_{u\in L^2(\Omega)}\frac{1}{2}\Vert\mathcal{K} u- b\Vert^2 +\frac{\beta}{2}\Vert u\Vert^2 , \underline{u}\le u\le \overline{u} ,$$ (1)

where $\mathcal{K}:L^2(\Omega)\to\mathcal{Y}$ is a bounded linear operator, with the embedding $\mathcal{Y}\hookrightarrow L^2(\Omega)$ being compact, and $\Omega$ is a bounded Lipschitz domain. The problem (1) can be regarded as the reduced form of a PDE-constrained optimization problem with $\mathcal{K}$ being the solution operator of a PDE (for example, $\mathcal{K}=(-\Delta)^{-1}:L^2(\Omega)\to H_0^1(\Omega)$ ).

For a piecewise constant discretization of the control space $V_h$ , each semi-smooth Newton (outer) iteration requires the solution of a linear system whose matrix is a principal submatrix of $G_h=K_h^TK_h +\beta I$ , where $K_h$ is the matrix representing the discretization of $\mathcal{K}$ , and $h$ is the mesh size. In a large-scale context these (inner) linear systems are solved using preconditioned conjugate gradient. An earlier technique [1] produced a multigrid preconditioner $M_h$ for $G_h$ that satisfies, under reasonable conditions,

$$1- C\frac{h^{\frac{1}{2}}}{\beta} \le \frac{\left< M_h u, u\right... ...>} \le 1 + C\frac{h^{\frac{1}{2}}}{\beta}, \forall u\in V_h\setminus\{0\} .$$ (2)

As a result of (2), the number of inner linear iterations needed to solve the system at each outer iteration decreases with $h\downarrow 0$ . While this result is interesting from a theoretical point of view (and qualitatively consistent with the behavior of the preconditioner for the full system), its practicality is limited by the suboptimal factor $h^{1/2}$ in (2).

The new technique, relying on constructing larger coarse spaces than before, produces multigrid preconditioners $M_h$ that are able to capture the character of the operator $G_h$ in an optimal way, namely we have

$$1- C\frac{h}{\beta} \le \frac{\left< M_h u, u\right>}{\left< G_h u, u\right>} \le 1 + C\frac{h}{\beta}, \forall u\in V_h\setminus\{0\} .$$ (3)