\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,amsfonts}

\newcommand{\x}{\boldsymbol{x}}
\newcommand{\y}{\boldsymbol{y}}
\newcommand{\h}{\boldsymbol{h}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\renewcommand{\r}{\boldsymbol{r}}
\renewcommand{\u}{\boldsymbol{u}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\renewcommand{\k}{\boldsymbol{k}}
\newcommand{\z}{\boldsymbol{z}}
\newcommand{\e}{\mathrm{e}}
\renewcommand{\i}{\mathrm{i}}
\renewcommand{\d}{\boldsymbol{d}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Range}{\operatorname{Range}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Span}{\operatorname{Span}}
\renewcommand{\dim}{\operatorname{dim}}
\renewcommand{\Lambda}{\boldsymbol{\lambda}}
\newcommand{\grad}{\boldsymbol{\nabla}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\def\nl{\vphantom\vdots\\}

\begin{document}

\title{Numerical Methods II}
\author{Problem Set 7}
\date{due in class, May 5, 2004}
\maketitle

The following set of questions concerns the quadratic penalty method
for solving the equality-constrained minimization problem
\begin{subequations}
\begin{gather}
  \text{minimize } f(\x) \\
  \text{subject to } \h(\x) = 0
\end{gather}
  \label{e.problem}
\end{subequations}
where $f \colon \R^n \to \R$ and $h \colon \R^n \to \R^q$.  We assume
throughout that $f$ and $h$ are at least twice continuously
differentiable. 

Recall that $\x$ is called a \emph{regular point} if $\h(\x) = 0$ and
the $q\times n$ matrix $\grad \h (\x)$ has full rank.

\paragraph{Necessary Condition} Suppose $\x^* \in \R^n$ solves problem
\eqref{e.problem}.  
Then
\begin{itemize}
\item[(i)] there exists a vector of Lagrange multipliers $\Lambda^* \in
  \R^q$ such that
\begin{equation}
  \grad f(\x^*) +  \grad \h(\x^*)^T {\Lambda^*} = 0 \,.
\end{equation}
\end{itemize}
If $\x^*$ is a regular point, then the vector of Lagrange multipliers
is unique.

\paragraph{Sufficient Condition} Suppose $\x^* \in \R^n$ satisfies the
constraint $\h (\x^*) = 0$, condition (i), and
\begin{itemize}
\item[(ii)] the Hessian matrix $H = \operatorname{Hess} (f +
   \h^T \Lambda^*)(\x^*)$ is positive definite on the tangent plane
   to the constraint manifold.  In other words,
\begin{equation}
  \x^T H \x > 0 \qquad
  \text{for all } \x \neq 0
  \text{ with } \grad \h \, \x   = 0 \,.
\end{equation}
\end{itemize}
Then $\x^*$ is a strict local minimizer of problem \eqref{e.problem}.

\paragraph{Penalty Method} The penalty method for solving
\eqref{e.problem} is the following.  Solve the unconstrained
minimization problem
\begin{equation}
  p_\alpha(\x) = f(\x) + \frac\alpha2 \, \| \h(\x) \|^2
\end{equation}
for a fixed value of $\alpha$.  If the constraint is not satisfied to
sufficient accuracy, increase $\alpha$ and repeat.

\begin{enumerate}

\item \emph{Monotonicity of the penalty method.} Let $0 < \alpha <
  \beta$, and let $\x^*$ and $\y^*$ denote the minimizers of
  $p_\alpha$ and $p_\beta$, respectively.  Prove the following
  statements.

\begin{enumerate}
  \item $p_\alpha (\x^*) \leq p_\beta (\y^*)$
  \item $\| \h(\x^*) \| \geq \| \h(\y^*) \|$

    \emph{Hint:} Show that $p_\alpha(\x^*) \leq p_\alpha(\y^*)$ and
    $p_\beta(\y^*) \leq p_\beta(\x^*)$.  Add both inequalities and off you
    go.

  \item $f(\x^*) \leq f(\y^*)$.

\end{enumerate}

\item \emph{Ill-conditioning of the penalty method.}  Show that the
  minimization problem for $p_\alpha$ gets increasingly
  ill-conditioned as $\alpha$ becomes large.

\emph{Hint:} You have to show that $\operatorname{Hess}
p_\alpha(\x^*)$ has eigenvalues of very different magnitude.  This is
the case if you can find two unit vectors $\u$ and $\v$ so that $\u^T
\operatorname{Hess} p_\alpha(\x^*) \u$ and $\v^T \operatorname{Hess}
p_\alpha(\x^*) \v$ have very different magnitude.

\item \emph{Continuous dependence of the solution of the penalty
  parameter.} Let $\mu = 1/\alpha$ and write out the necessary
  condition for a minimizer of $p_\alpha$ as
\[
  F (\x, \Lambda) =
  \begin{pmatrix}
     \grad^T f + \grad^T \h^T \, \Lambda \\
     \h - \mu \, \Lambda
  \end{pmatrix} = 0 \,.
\]
Show that, provided that the solution $(\x^*,\Lambda^*)$ satisfies the
sufficient condition (ii), and provided that $\x^*$ is a regular
point, that $\x^*$ and $\Lambda^*$ vary continuously with $\mu$ near
$\mu^*=0$ by verifying that $\grad_{(\x,\Lambda)} F(\x^*, \lambda^*;
\mu^*)$ is nonsingular.  (I.e., the chief condition of the implicit
function theorem is satisfied.)


\end{enumerate}
  



\end{document}
