\be
\item For each of the following NLPs, explain why the NLP is not convex.
Then determine the KKT points and corresponding
multiplier vectors. Finally, verify that the restricted Lagrangian satisfies
the saddle point criteria. (Note: Determining the KKT points and corresponding
multiplier vectors can be accomplished using Maple as outlined at the end of
Section \ref{SS:SolvingConvexNLPs}

\be
\item \begin{align*}
		\mbox{minimize } f(x_1,x_2)&=x_1^2-x_2^2  \\
		\mbox{ subject to} \notag\\
		x_1-x_2 &\leq 0  \notag\\
		x_1^2+x_2^2 &\leq 4 \notag \\
		x_2 &\geq 0\notag
		\end{align*}

\item \begin{align*}
		\mbox{minimize } f(x_1,x_2)&=x_1x_2  \\
		\mbox{ subject to} \notag\\
		x_1^2+x_2^2 &\leq 1  \notag\\
		2x_1+3x_2 &\leq 3 \notag \\
		x_1 &\geq 0\notag
		\end{align*}

\item \begin{align*}
		\mbox{minimize } f(x_1,x_2)&=x_2^2-6x1+x_2^2-4x_2  \\
		\mbox{ subject to} \notag\\
		x_1^2+x_2^2 &\leq 9  \notag\\
        x_1^2-x_2^2 &\leq 0  \notag\\
        2x_1+x_2 &\leq 8 \notag \\
		\ph x_2 \leq 2\notag
		\end{align*}

\ee

\item Verify that the restricted Lagrangian for the \CMC NLP satisfies the saddle point criteria
at its optimal solution.

\item Consider the convex NLP

\begin{align*}
\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
	\end{align*}
where $f,g_1,g_2,\ldots,g_m$ are each differentiable, convex functions defined on some convex
set $S \subseteq \R^n$. In this
problem, we show that if $\vecx_0$ is a KKT point with corresponding multiplier vector, $\lambdavec_0$,
then $(\vecx_0,\lambdavec_0)$ is a saddle point of the restricted Lagrangian. In other words,
we establish the two inequalities that comprise (\ref{E:SaddlePointsSaddleDefinitionInequality}).

\be
\item Suppose that $\lambdavec$ is a vector in $\R^m$ having nonnegative
components $\lambda_i$, where $1 \leq i \leq m$. To show that
$\ds \widetilde{L}(\vecx_0,\lambdavec) \leq \widetilde{L}(\vecx_0,\lambdavec_0)$,
first express the difference $\ds \widetilde{L}(\vecx_0,\lambdavec,\muvec) - \widetilde{L}(\vecx_0,\lambdavec_0,\muvec_0)$ in terms of $f,g_1,g_2,\ldots,g_m$
and the components of $\lambdavec$ and $\lambdavec_0$.
\item To establish that $ \ds \widetilde{L}(\vecx_0,\lambdavec_0)
\leq \widetilde{L}(\vecx,\lambdavec_0)$, start by expressing the
difference $ \ds \widetilde{L}(\vecx_0,\lambdavec_0)
- \widetilde{L}(\vecx,\lambdavec_0)$ in terms of $f,g_1,g_2,\ldots,g_m$
and the Lagrange multipliers, $\lambda_{0,1}, \lambda_{0,2}, \ldots \lambda_{0,m}$.
\item Now apply Theorem \ref{Th:convexity_FOC_linear_approx_inequality} to each
of the functions $f,g_1,g_2,\ldots,g_m$ from (c) in order to show that
\begin{equation*}
\widetilde{L}(\vecx_0,\lambdavec_0)
- \widetilde{L}(\vecx,\lambdavec_0) \leq -\left(\nabla f(\vecx_0)^t +
\jacobian_{\vecg}(\vecx_0)^t\lambda_0\right)( \vecx-\vecx_0 ).
\end{equation*}
\item Finally, apply equation (\ref{E:LagrangianFritzJohnFormula}) to the right-hand side of
the previous inequality.
\ee

\ee

