\hfill \thepage}
%}
\input{tcilatex}
\begin{document}
\vspace{1pt}Penalty Methods
For Chong/Zak Section 22.2
Brief synopsis
Author: Robert Beezer
History:
1999/04/20\qquad First version. \ Based on notes from Uhl/Peressini/Sullivan
\vspace{1pt}
\begin{enumerate}
\item The problem: \ \ minimize \ $f(x)$, \ subject to \ $g_{i}(x)\leq 0$,
\ $1\leq i\leq m$. \ (Inequality constraints)\bigskip
\item Strategy: \ Convert to an unconstrained problem and use previous
techniques. \ This will involve a penalty for being ``outside'' of the
constrained region.\bigskip
\item Device: \ For a constraint \ $g(x)$ \ define
\[
g^{+}\left( x\right) =\left\{
\begin{array}{r}
g^{+}(x)\text{ \ if \ }g(x)\geq 0 \\
0\text{ \ if \ }g(x)\leq 0
\end{array}
\right|
\]
Now define
\[
P_{k}(x)=\ f(x)+k\sum_{i=0}^{m}g_{i}^{+}(x)
\]
So if we choose \ $k$ \ large enough, we will force the function to be
minimized and to head for inside the boundary.\bigskip
\item Examples:
\begin{enumerate}
\item $g(x)=x^{2}-8$
\item $g(x,y)=28-x^{2}-2y^{2}\bigskip $
\end{enumerate}
\item While this looks like a good idea, the functions above are not
differentiable, so we can't use things like Newton's Method to minimize
these functions. \ Instead, employ \ $\left( g^{+}\left( x\right) \right)
^{2}$ \ so we get the objective function
\[
P_{k}(x)=\ f(x)+k\sum_{i=0}^{m}\left( g_{i}^{+}\left( x\right) \right) ^{2}
\]
To differentiate note that
\[
\frac{d}{dx}\ \left( g^{+}\left( x\right) \right) ^{2}=2\ \left( g^{+}\left(
x\right) \right) \left( g^{\prime }(x)\right)
\]
\item Problem (Uhl/Peressini/Sullivan Example 6.2.5)
min \ $x^{2}+y^{2}$, \ subject to \ $x+y\geq 1$.
Draw a picture of the situation.
Then \
\[
g\left( x,y\right) =1-x-y
\]
and
\[
P_{k}(x,y)=x^{2}+y^{2}+k\left( g^{+}\left( x,y\right) \right) ^{2}
\]
Using standard techniques from earlier chapters, the gradient is zero for $%
P_{k}(x,y)$ \ at
\begin{enumerate}
\item $(0,0)$ \ if we consider the constrained region, yet this point is
not there, so we need not consider it.
\item Or, outside of the constrained region at a solution to
\[
2x-2k(1-x-y)=0\text{, \ }2y-2k(1-x-y)=0
\]
which is
\[
x=\frac{k}{1+2k}\text{, \ \ }y=\frac{k}{1+2k}
\]
\end{enumerate}
Note the behavior of these critical points as we increase \ $k$.\bigskip
\item An alternative approach is to use an iterative algorithm and crank up
\ $k$ \ as we go.\bigskip
\item Problem: \ \ (messy, not presented) \
Consider \ $f(x,y)=x^{4}+y^{4}-4xy+1$. \ \ It has a pair of minima, at \ $%
(1,1)$ \ and \ at \ $(-1,-1)$. \ Constrain the domain to be \ a circle
around the point \ $(1,1)$ \ of radius \ $1$ \ (i.e. \ $(x-1)^{2}+(y-1)^{2}%
\leq 1$) \ and use the other minimum as a starting point for an iterative
procedure.
Now \ $g(x,y)=(x-1)^{2}+(y-1)^{2}-1$. \ \ Use steepest descent with a
starting point of \ $x^{(0)}=(-1,1)$. \ Set \ $k=10$.
(Can't use Newton's method since we don't have a second derivative!)
The gradient of \ $P_{k}(x,y)$ \ is then
\[
\nabla
P_{k}(x,y)=(4x^{3}-4y+20g^{+}(x,y)(2(x-1)),4y^{3}-4x+20g^{+}(x,y)(2(y-1)))
\]
Then \ $\nabla P_{k}(-1,-1)=(-560,-560)$. \ (Coincidentally pointing right
back at the other minimum!), so we form
\[
\phi _{0}(t)=P_{k}(-1-t(-560),-1-t(-560))
\]
When \ $t$ \ puts this point outside of the constrained region ($0