%From rbk5287@interval.usl.edu Sat Dec 17 02:39:25 1994
%From: "Kearfott R. Baker" <rbk5287@interval.usl.edu>

\documentstyle[IEEEtran]{article}
\begin{document}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ }


\newtheorem{algorithm}{Algorithm}
\newtheorem{remark}{Remark}
\newtheorem{definition}{Definition}

\newcommand{\iX}{{\bf X}}
\newcommand{\iXo}{{{\bf X}_0}}
\newcommand{\ix}{{\bf x}}
\newcommand{\ixl}{{\underline{x}}}
\newcommand{\ixu}{{\overline{x}}}
\newcommand{\Xp}{{\check X}}
\newcommand{\xp}{{\check x}}
\newcommand{\iXp}{{\bf{\check X}}}
\newcommand{\iXh}{{\hat{\bf X}}}
\newcommand{\ixh}{{\hat{\bf x}}}
\newcommand{\gradc}{{{\bf\nabla}{\bf C}}}
\newcommand\newX{{\iXh}_{\makebox{new}}}
\newcommand{\inewt}{{\bf N}(\iX,F)}
\newcommand{\iXtil}{{{\tilde{\bf X}}}}
\newcommand{\ixtil}{{{\tilde{\bf x}}}}
\newcommand{\iA}{{\bf A}}
\newcommand{\ia}{{\bf a}}
\newcommand{\iYA}{{\bf G}}
\newcommand{\iya}{{\bf g}}
\newcommand{\is}{{\bf s}}

\newcommand{\phiu}{{\overline{\phi}}}
\newcommand{\phil}{{\underline{\phi}}}

\newcommand{\todolist}{{\cal L}}
\newcommand{\unknownlist}{{\cal U}}
\newcommand{\completedlist}{{\cal C}}
\newcommand{\donecoords}{{\cal I}}
\newcommand{\donecoordsnew}{{\cal I}_{\makebox{\rm new}}}

\newcommand{\R}[1]{{\Bbb R}^{#1}}

\newcommand {\If} {{\em IF }}
\newcommand {\Then} {{\em THEN }}
\newcommand {\Else} {{\em ELSE }}
\newcommand {\Endif} {{\em END IF}}
\newcommand {\return} {{\em RETURN }}
\newcommand {\Input} {{\em INPUT }}
\newcommand {\Exit} {{\em EXIT}}
\newcommand {\Dowhile} {{\em DO WHILE }}
\newcommand {\Do} {{\em DO }}
\newcommand {\Enddo} {{\em END DO }}

\newcommand \mig[1]{\left\langle #1 \right\rangle}
\newcommand \interior{{\makebox{{\rm int}}}}


\title{A Review of Techniques in the Verified
Solution of Constrained Global Optimization Problems}

\author{R.  Baker Kearfott}
\maketitle


\auffil{Department of Mathematics, University of Southwestern Louisiana,
U.S.L. Box 4-1010, Lafayette, Louisiana 70504-1010.
This work was supported in part by
National Science Foundation grant CCR-9203730}


Elements and techniques of state-of-the-art automatically verified
constrained global
optimization algorithms are reviewed.  These include, among other
things, a description of ways of rigorously verifying feasibility for
equality constraints and a careful consideration of the role of active
inequality constraints.   Previously developed algorithms and
general work on the subject are also listed.  Limitations of present
knowledge are mentioned, and advice is given on which techniques
to use in various contexts.

The basic problem to be considered is

\begin{eqnarray}
\makebox{minimize}\quad \phi(X) & & \nonumber \\
\makebox{subject to}\quad c_i(X) &=& 0, \quad i=1,\dots,m \label{eq:problem}\\
a_{i_j} \le &x_{i_j}& \le b_{i_j}, \quad j=1,\dots,q, \nonumber
\end{eqnarray}
where $X=(x_1,\dots,x_n)^T$.

Specific interval global optimization algorithms are considered to be
specific cases of a general pattern.  The basic ideas in this pattern
include a {\em check on the range\/} of $\phi$ and a {\em computational
existence / uniqueness\/} test.  We let $\iX=(\ix_1,\dots\ix_n)^T =
([\ixl_1,\ixu_1],\dots, [\ixl_n,\ixu_n])^T$ be the interval vector
(``box") representing the search region $\ixl_i\le x_i\le \ixu_i$, $1\le
i\le n$.  Such algorithms can maintain a list $\todolist$ of boxes $\iX$
to be processed, a list $\unknownlist$ of boxes the algorithm has
reduced to small diameter, and a list $\completedlist$ of boxes that
have been verified to contain critical points.  The pattern can then be
stated as:

\begin{algorithm} \label{alg:abstract} {\em (Abstract Branch-and-Bound
Pattern)}
\begin{enumerate}
\item Initialize $\todolist$ by placing the initial search region $\iXo$
in it.

\item \Dowhile $\todolist \ne \emptyset$.
\begin{enumerate}
\item Remove the first box $\iX$ from $\todolist$;

\item \label{step:process-x} {\em (Process $\iX$)} Do one of the
following:

\begin{itemize}
\item reject $\iX$;

\item reduce the size of $\iX$;

\item determine that $\iX$ contains a unique critical point, then find
the critical point to high accuracy.

\end{itemize}

\item \label{step:listops} Insert one or more boxes derived from $\iX$
onto $\todolist$, $\unknownlist$ or $\completedlist$, depending on the
size of the resulting box(es) from step~\ref{step:process-x} and whether
the (possible) computational existence test in that step has determined
a unique critical point.

\end{enumerate}
\end{enumerate}
\noindent{\bf End Algorithm~\ref{alg:abstract}}
\end{algorithm}

(Possibly optional) acceleration devices used in Algorithm~\ref{alg:abstract}
can be listed as:

\begin{algorithm} \label{alg:range-verify} {\em (Range Check and
Critical Point Verification)}

\begin{enumerate}

\item Input a box $\iX$ and the current best rigorous upper bound $\phiu$
on the global minimum.

\item \label{step:feasibility} {\em (Feasibility check; for constrained
problems only)}
\begin{enumerate}
\item \label{step:infeasibility} {\em (Exit if infeasibility is proven)}
\Do for
$i=1$ to
$m$:
\begin{enumerate}
\item Compute an enclosure $c_i(\iX)$ for the range of $c_i$ over $\iX$.
\item \If $0\not\in c_i(\iX)$ \Then \Exit.
\end{enumerate}
\item \label{step:prove-feasibility} Prove computationally, if possible,
that there exists at least one feasible point in $\iX$.
\end{enumerate}

\item \label{step:midpoint-test} {\em (Range check or ``midpoint test")}
\begin{enumerate}
\item
Compute a lower bound
$\phil(\iX)$ on the range of $\phi$ over $\iX$.
\item \If $\phil(\iX)<\phiu$ \Then \Exit.
\end{enumerate}

\item \label{step:update-phiu} {\em (Update the upper bound on the
minimum.)}
\If the problem is unconstrained or feasibility was
proven in step~\ref{step:prove-feasibility}, \Then
\begin{enumerate}
\item Use interval arithmetic to compute an upper bound $\phiu(\iX)$ of
the objective function $\phi$ over $\iX$.
\item $\phiu \leftarrow \min\{\phiu,\phiu(\iX)\}$.
\end{enumerate}

\item \label{step:monotonicity-test} {\em (``monotonicity test")}
\begin{enumerate}
\item Compute an enclosure $\nabla\phi(\iX)$ of the range of
$\nabla\phi$ over $\iX$. (Note: If $\iX$ is ``thin,", i.e.\ if
some bound constraints are active over $\iX$, then a {\em reduced
gradient\/} can be used.

\item \If $0\not\in\nabla\phi(\iX)$ \Then \Exit.
\end{enumerate}

\item \label{step:concavity-test} {\em (``concavity test")} If the
Hessian matrix\footnote{or reduced Hessian matrix, as in
step~\ref{step:monotonicity-test}}
$\nabla^2\phi$ cannot be positive definite anywhere in
$\iX$ \Then \Exit.

\item \label{step:reduction-verification} {\em (Quadratic convergence
and computational existence / uniqueness)} Use an interval Newton
method\footnote{possibly in a subspace, as in
steps~\ref{step:monotonicity-test} and \ref{step:concavity-test}}
(with the Fritz--John conditions in the constrained case) to
possibly do one or more of the following:
\begin{itemize}
\item reduce the size of $\iX$;
\item discard $\iX$;
\item verify that a unique critical point exists in $\iX$.
\end{itemize}

\item \label{step:bisection} {\em (Bisection or geometric tesselation)}
If step~\ref{step:reduction-verification} did not result in a sufficient
change in $\iX$, then bisect $\iX$ along a coordinate direction (or
otherwise tesselate $\iX$), returning all resulting boxes for subsequent
processing.

\end{enumerate}

\noindent{\bf End Algorithm~\ref{alg:range-verify}}
\end{algorithm}

Within the review paper, nine published algorithms are mentioned in
tables, giving information on which of the devices in
Algorithm~\ref{alg:range-verify} are used, as well as information concerning
the extent of reported numerical experiments.

Elements of such algorithms are also reviewed.  In particular, choices
involved in constructing interval Newton methods are outlined.  These
include choice of the method itself, choice of method of computing the
derivative matrix, choice of preconditioner, choice of base point, and
the form of the Fritz--John conditions for problem~\ref{eq:problem}.  A
unique part of this discussion is an observation concerning how to
combine a technique of Hansen with computations of interval slopes;
this discussion appears along with simple examples.  Also,
careful consideration is given of properties and choices for different
goals, such as:

\begin{itemize}
\item reducing the size of regions $\iX$, with quadratic
      convergence of the widths to zero;
\item computationally (but rigorously) proving existence
      of solutions within $\iX$;
\item proving that that there is a unique solution within $\iX$;
\item proving that there can be no solutions in $\iX$.
\end{itemize}

With regard to the treatment of constraints, differences in between
techniques that
\begin{itemize}
\item prove approximate feasibility,
\item rigorously prove feasibility, or
\item rigorously prove infeasibility
\end{itemize}
are clarified.  In particular, the need to rigorously prove feasibility
is explained, and a technique for
rigorously proving feasibility of equality constraints,
related to a technique of Hansen and explained in a concurrent paper
of the author, is reviewed.

There is also an extensive section on handling bound constraints. Several diagrams illustrate a tesselation process for bound constraints,
first appearing in a previous paper of the author,
while an algorithm for it is given in simple recursive form.  The process
can be viewed as traversing a ternary tree.  Implications concerning
computational complexity of bound constraints are discussed, and techniques
for rigorously pruning the tree are mentioned.  The techniques are
advocated, along with use of slack variables, for general inequality
constraints, as well as bound constraints.

Finally, there is a section detailing applications to date

Sixty-six  references appear.

{\bf Key words.} constrained global optimization,  verified computations,
interval computations, bound constraints.

{\bf AMS subject classifications.} 65K05, 90C26

\end{document}