\section{Penalty Methods}\label{S:PenaltyMethods}
\setcounter{progress_ck_counter}{0}
%\setcounter{activity}{0}

\newpar
If an NLP is not convex or if it is convex and KKT points are difficult to determine
algebraically, numeric techniques provide an appropriate means for estimating the solution. As
was the case in Chapter \ref{C:Numeric_Methods}, we focus on the most elementary
tools, which, in the case of constrained NLPs, consist of the \emph{external penalty}
and \emph{barrier} methods. Both involve converting a constrained NLP to an unconstrained
one, at which point, algebraic or numeric methods for problems of this latter type are used.
By solving a sequence of unconstrained problems, we obtain, under ideal circumstances,
an approximate solution to the original NLP.

\subsection{The External Penalty Method}

We begin by considering NLP (\ref{E:LagrangianGeneralNLP}), which we restate here for the
sake of completeness:

\begin{align}\label{E:PenaltyMethodsGeneralNLP}
\mbox{ minimize } & f(\vecx )  \\
	\mbox{ subject to} \notag\\
	g_1(\vecx) &\leq 0 \notag\\
	g_2(\vecx) &\leq 0  \notag\\
	\vdots & \notag \\
    g_m(\vecx) &\leq 0.  \notag\\
   h_1(\vecx) &= 0 \notag\\
	h_2(\vecx) &= 0  \notag\\
	 \vdots & \notag \\
     h_p(\vecx) &= 0,  \notag
	\end{align}
where  $S \subseteq \R^n$ is convex and that all functions
are mappings from $S$ to $\R$.
\noi
The \emph{external penalty method} utilizes an \emph{augmented objective function} of the form
\begin{equation}\label{E:PenaltyMethodsAugmented}
\phi(\vecx)=f(\vecx)+M P(\vecx),
\end{equation}
where $M$ is a large positive number and where $P(\vecx)$ is a \emph{loss function}, which is nonzero precisely when $\vecx$ is infeasible.

\newpar
While there are many possible choices for $P$, one of the most common involves the piecewise-defined
function,
\begin{equation}\label{PenaltyMethodsMaximumFunction}
\max(x,0)=\begin{cases}
		x,	&\text{if $x>0$};\\
		0,	&\text{otherwise,}
	\end{cases}
\end{equation}

An elementary exercise shows that if $r>1$, then $\max(x,0)^r$ is differentiable
on $\R$ and if $r>2$, then it is also twice-differentiable there. We now define
\begin{equation}\label{PenaltyMethodsPenaltyFunction}
P(\vecx)= \sum_{i=1}^m \max(g_i(\vecx),0)^r +  \sum_{j=1}^p h_j(\vecx)^s.
\end{equation}
Note that $P(\vecx)$ is nonzero precisely if $\vecx$ is feasible for
(\ref{E:PenaltyMethodsGeneralNLP}). If $r=s=2$, $P$ is referred to as
a \emph{quadratic loss function}.

\newpar
We now define our \emph{augmented objective function} as given
in (\ref{E:PenaltyMethodsAugmented}):
\begin{align}\label{PenaltyMethodsAugmented2}
\phi(\vecx) &= f(\vecx) + M P(\vecx) \\
&= f(\vecx) + M \left(\sum_{i=1}^m \max(g_i(\vecx),0)^r +  \sum_{j=1}^p h_j(\vecx)^s\right). \notag
\end{align}

\noi
The key idea behind the external penalty method is to observe that for large values of $M$, the solution
to the unconstrained minimization problem,
\begin{equation}\label{PenaltyMethodsAugmentedMinimization}
\mbox{minimize } \phi(\vecx) \mbox{ where $\vecx$ belongs to $S$},
\end{equation}
is more likely to be feasible for
(\ref{E:PenaltyMethodsGeneralNLP}), owing to the presence of the penalty term. By solving
(\ref{PenaltyMethodsAugmentedMinimization}) using a progressively larger and larger values of
$M$, a process in itself that usually requires techniques from Chapter \ref{C:Numeric_Methods},
we hope to obtain a sequence of values that converges to the solution of (\ref{E:PenaltyMethodsGeneralNLP}). This technique can be summarized as follows:

\newpar
{\underbar{The External Penalty Method}} \newline
To obtain an approximate solution of NLP (\ref{E:PenaltyMethodsGeneralNLP}):
\be
\item Fix $r$ and $s$ in (\ref{PenaltyMethodsAugmented2}). If all functions in
(\ref{E:PenaltyMethodsGeneralNLP}) are twice-differentiable, then $r=s>2$ ensures
$\phi$ is twice-differentiable on $S$.
\item Fix $\lambda >0$ and $\rho>1$.
\item Set $k=1$ and solve (\ref{PenaltyMethodsAugmentedMinimization})
with $M= \lambda \rho^k$. If $r=s>2$, then second-order techniques,
such as Newton's Method or the Levenberg-Marquardt Algorithm, may prove useful
in this process. Call the resulting solution $\vecx_k$.
\item Let $k=k+1$ and return to the preceding step.
\item Terminate the process using some sort of stopping criteria. Typically, for a given
tolerance, $\epsilon$, termination occurs either when
$\left| \vecx_k - \vecx_{k+1} \right| < \epsilon$ or when $\ds \left| P(\vecx_k)-P(\vecx_{k+1}) \right|< \epsilon$.
\ee

\noindent
An algorithm such as this, which involves solving a sequence of unconstrained problems, is an
example of a \emph{sequential unconstrained minimization technique} (SUMT).

\newpar
To demonstrate the algorithm using Maple, we consider the non-convex NLP
\begin{align}\label{E:SaddlePointsExample}
 \mbox{ minimize }  & f(\vecx )=x_1^2-x_2^2   \\
	\mbox{ subject to} \notag\\
	g_1(\vecx)&=x_1-x_2 \leq 0 \notag\\
    g_2(\vecx)&=x_1^2+x_2^2 -4 \leq 0 \notag\\
    g_3(\vecx)&=-x3 \leq 0, \notag\\
	\end{align}
whose solution is $\ds \vecx_{\bigstar} = \begin{bmatrix} 0 \\ 2 \end{bmatrix}$, where
only the second constraint is binding. Here is a portion
of a worksheet that performs the SUMT using the external penalty method. We have omitted the beginning
of the worksheet, which includes formulating the \mf{NewtonsMethod} procedure, as given in Section \ref{S:NewtonsMethod}.

\begin{maplelist}
\item \mf{with(VectorCalculus):}
\item \mf{f:=(x1,x2)-> x1$\wedge$2-x2$\wedge$2: \newline
\# Enter objective function.}
\item \mf{g1:=(x1,x2)->x1-x2:}
\item \mf{g2:=(x1,x2)->x1$\wedge$2+x2$\wedge$2-4:}
\item \mf{g3:=(x1,x2)->-x2:}
\item \mf{g:=(x1,x2)-><g1(x1,x2),g2(x1,x2),g3(x1,x2)>:} \newline
\mf{\# Enter vector-valued constraint function.}
\item \mf{P:=add(piecewise(g(x1,x2)[i]>=0,(g(x1,x2)[i])$\wedge$3),i=1..3):} \newline
\mf{\# Enter loss function.}
\item \mf{phi:=unapply(f(x1,x2)+M*P(x1,x2),[x1,x2]):} \newline
\mf{\# Create augmented objective function.}
\item \mf{N:=25:} \newline
\mf{\# Set maximum allowable number of SUMT iterations.}
\item \mf{lambda:=10:rho:=1.2:} \newline
\mf{\# Set penalty parameters.}
\item \mf{epsilon:=.01:}\newline
\mf{\# Set termination criteria}
\item \mf{initial:=[3,4]:}\newline
\mf{\# Initial seed for each call to Newton Method procedure.}
\item \mf{tolerance:=1:k:=1:x[0]:=initial: \newline
while (k<=N and tolerance >=.01) do \newline
x[k]:=NewtonsMethod(phi(lambda*rho$\wedge$k),initial,20,.01):\newline
\# Perform Newton's Method, with specified parameters, \newline
\# to minimize augmented objective function. \newline
tolerance:=Norm(convert(x[k]-x[k-1],Vector),Euclidean): \newline
k:=k+1:end do:}
\item \mf{x[k-1];}
\mo{[1.7846827 \, 10^(-59), 2.009667059]}
\end{maplelist}

\subsection{Convergence Issues}

Perhaps the greatest impediment to using the External Penalty Method effectively centers around the choice
of penalty parameters. In general, we desire that $M$ in
(\ref{PenaltyMethodsAugmented2}) be very large. For when this occurs, the solution
of (\ref{PenaltyMethodsAugmentedMinimization}) is more likely to be feasible for
(\ref{E:PenaltyMethodsGeneralNLP}). The difficulty stems from the fact that, while
this solution may be feasible for (\ref{E:PenaltyMethodsGeneralNLP}), it need not be
optimal.

\newpar
To see how this situation can arise in practice, we can merely change
the penalty parameters in the preceding worksheet to $lambda=1$ and $\rho=10$. The
result of such alterations is that the SUMT iterates converge to
$\ds \vecx \approx \begin{bmatrix}   1.2 \\ 1.6  \end{bmatrix}$. Like the solution of the NLP,
$\vecx$ is feasible and satisfies $\ds g_2(\vecx)=0$. However, it is not an optimal solution
since $f(\vecx) > f\left( \vecx_{\bigstar} \right)=-12$.







%\newpage
%\paragraph{
%Exercises Section \ref{S:SteepestDescent}}
%\input{Exercises_SteepestDescentMethod}
\endinput

