next up previous
Next: Verification of SSC Conditions Up: paper90 Previous: Known SSC Results for


Second Order Sufficient Conditions for the Discretized Problems

All three control problems (P), (EB), (ED) defined in the previous sections lead after suitable discretization to nonlinear finite-dimensional optimization problems of the form

\begin{displaymath}
\min F^h(z)\quad\mbox{subject to}\quad G^h(z)=0,\quad H(z)\le0
\end{displaymath} (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 problems are assumed to be discretized as described in detail in [16]-[19]. $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


\begin{displaymath}
z_l\le z\le z_u
\end{displaymath} (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


\begin{displaymath}
N(z^*)=(\nabla G^h(z^*),\nabla H_a(z^*))
\end{displaymath}

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, [24]


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

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


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

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]-[19] 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 [25] 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, it computes the QR decomposition of $N(z^*)$ with the help of LAPACK routine DGEQRF. This use of dense numerical linear algebra limits the problem size and will in future work be replaced by an approach exploiting sparsity. 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.


next up previous
Next: Verification of SSC Conditions Up: paper90 Previous: Known SSC Results for
Hans D. Mittelmann
2001-06-17