Second Order Sufficient Conditions for the Discretized Problems

The control problems (P) and (EB) defined in the previous sections lead after suitable discretization to nonlinear finite-dimensional optimization problems of the form

$$\min F^h(z)\quad\mbox{subject to}\quad G^h(z)=0,\quad H(z)\le0$$ (4.1)

where $z$ comprises the discretized control and state variables.

A discretization (P$_h$) of (P) is given in section 2 while the elliptic problem is assumed to be discretized as described in detail in [16,18]. $G^h(z)$ symbolizes the state equation and boundary conditions while $H(z)$ denotes both pointwise control and state constraints, the only constraints of inequality type prescribed above. Thus, alternatively, it can be written as

$$z_l\le z\le z_u$$ (4.2)

where components of $z_l(z_u)$ are taken as $-\infty(\infty)$ if no constraint is imposed on the component.

We state the well-known SSC for (4.1), assuming $z\in\mathbf{R}^n$, $G^h:\mathbf{R}^n\to\mathbf{R}^m$, $m<n$. Let $z^*$ be an admissible point satisfying the first-order necessary optimality conditions with associated Lagrange multipliers $\mu^*$ and $\lambda^*$. Let further

$$N(z^*)=(\nabla G^h(z^*),\nabla H_a(z^*))$$

be a column-regular $n\times(m+p)$ matrix where $m+p<n$ and $\nabla H_a(z^*)$ denotes the gradients of the $p$ active inequality constraints. Let finally $N=QR$ be a QR decomposition and $Q=(Q_1,Q_2)$ a splitting into the first $m+p$ and the remaining columns.

The point $z^*$ is a strict local minimizer if a $\gamma>0$ exists such that, see, for example, [26]

$$\lambda_{\min}(L_2(z^*))=\gamma>0.$$ (4.3)

Here $L_2(z^*)$ is the projected Hessian of the Lagrangian

$$L_2(z^*)=Q^T_2(\nabla^2F^h(z^*)-\mu^{*T}\nabla^2G^h(z^*))Q_2.$$

No Hessian of $H$ appears on the right due to its linearity. Next, we will detail how condition (4.3) will be checked for the discrete versions of both the parabolic and the elliptic control problems. As was already done in [16,18] the control problems are written in the form of AMPL [7] scripts. This way, a number of nonlinear optimization codes can be utilized for their solution. It had been an observation in our previous work that from the currently available codes only LOQO [27] is able to solve all the problems effectively and for sufficiently fine discretizations. The following is independent of the solver used.

After computing a solution an AMPL stub (or $*.nl$) file is written as well as a file with the computed Lagrange multipliers. This allows to check the SSC (4.3) with the help of a Fortran, alternatively, a C or Matlab, program.

This program reads the files and verifies first the necessary first-order optimality conditions, the column regularity of $N(z^*)$ and the strict complementarity. For this, it utilizes routines provided by AMPL which permit evaluation of the objective and constraint gradients. Next, the the QR decomposition of $N(z^*)$ is computed by one of the methods exploiting sparsity. We have utilized the algorithm described in [22]. AMPL also provides a routine to multiply the Hessian of the Lagrangian times a vector. This is called with the columns of $Q_2$ and thus $L_2(z^*)$ can be formed. Its eigenvalues are computed with LAPACK routine DSYEV and the smallest eigenvalue $\gamma=\gamma_h$ is determined. The use of this eigenvalue routine is possible since the order of the matrices corresponding to the "free" control variables is moderate. In case of distributed control problems when this number may be on the order of the state variables, a sparse solver, preferably just for finding the minimal eigenvalue, will have to be used.