\section{Sufficient Conditions for Local and Global Optimal Solutions}\label{S:ExerciseSolutions_optimality_sufficient_SOC}
\setcounter{progress_ck_counter}{0}

\be
\item If $\ds f(x_1,x_2)=e^{-\left(x_1^2+x_2^2\right)}$, then direct computations lead to the following results:

\begin{align*}
\nabla f(\vecx)= \begin{bmatrix} -2x_1f(x1,x2) \\ -2x_2f(x_1,x_2) \end{bmatrix}
\intertext{and}
H_f(\vecx)= \begin{bmatrix} (-2+4x_1^2)f(x1,x2) & 4x_1x_2f(x_1,x_2) \\
4x_1x_2f(x_1,x_2) & (-2+4x_2^2)f(x1,x2) \end{bmatrix}
\end{align*}

so that

\begin{align*}
\nabla f(\vecx_0)\approx \begin{bmatrix} -.2707 \\ -.2707 \end{bmatrix}
\intertext{and}
H_f(\vecx_0) \approx \begin{bmatrix} .2707 & .5413 \\ .5413 & .2702 \end{bmatrix}.
\end{align*}

\noi
Thus,
\begin{align*}
Q(\vecx )&= f(\vecx_0 )+ \nabla f(\vecx_0)^t ( \vecx-\vecx_0 )+ \frac{1}{2}(\vecx-\vecx_0)^t H_f(\vecx_0)(\vecx-\vecx_0) \\
&\approx 2.3007-1.895x_1-1.895x_2+.2707x_1^2+.2707x_2^2+1.0827x_1x_2
\end{align*}

\noi
The quadratic approximation together with $f$ are graphed in Figure \ref{Fi:s06x4x1}. The solution is given by
$\ds \vecx= \begin{bmatrix} 4.5 \\ 0 \end{bmatrix}$,
with $z=27$.

\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\includegraphics[width=1\linewidth]{ExerciseSolutions/images/s06x4x1.eps}
\caption{Plot of $f$ with quadratic approximation}
\label{Fi:s06x4x1}
\end{figure}

\item Calculations establish that Hessian of $f$ is given by $\ds H_f(\vecx)=\phi(\vecx) A$, where
$\ds \phi(\vecx)= \frac{1}{(74+.5x_1+x_2+x_3)^{1/10}}$ and where
\begin{equation*}
A=\begin{bmatrix} .045 & .09 & .09 \\ .09 & .19 & .19 \\ .09 & .19 & .19
\end{bmatrix}.
\end{equation*}

Observe that $\phi(\vecx) >0$ for $\vecx$ in $S$ and that $A$ is positive semidefinite. (Its
eigenvalues are .002, .423, and zero.)

\noi Now suppose that $\vecx_0$ belongs to $S$ and that $\lambda_0$ is an eigenvalue of
$\ds H_f(\vecx_0)$ with corresponding eigenvector $\vecv$. Then
\begin{align*}
\lambda_0 \vecv &= H_f(\vecx_0) \vecv \\
&= \phi(\vecx_0) A \vecv,
\end{align*}
implying $\ds \frac{\lambda_0}{\phi(\vecx_0)}$ is an eigenvalue of $A$. Since $\phi(\vecx_0) >0$
and each eigenvalue of $A$ is nonnegative, then $\lambda_0$ must be nonnegative as well. Hence,
$H_f(\vecx_0)$ is positive semidefinite, and $f$ is convex.


\item
\be
\item We have $\ds \nabla f(\vecx)=\begin{bmatrix} 2x_1+x_2-1 \\ x_1+4x_2-4 \end{bmatrix}$, which yields the critical point, $\ds \vecx_0=\begin{bmatrix} 0 \\ 1 \end{bmatrix}$.
Since $\ds H_f(\vecx)=\begin{bmatrix} 2 & 1 \\ 1 & 4 \end{bmatrix}$ has positive eigenvalues,
$\ds \lambda= 3 \pm \sqrt{2}$, we see that $f$ is strictly convex on $\R^2$ so that
$\vecx_0$ is a global minimum.

\item We have $\ds \nabla f(\vecx)=\begin{bmatrix} 2x_1-10x_2+4 \\ -10x_1+14x_2-8 \end{bmatrix}$, which yields the critical point, $\ds \vecx_0=\begin{bmatrix} -1/3 \\ 1/3 \end{bmatrix}$.
Since $\ds H_f(\vecx)=\begin{bmatrix} 2 & -10 & -10 & 14 \end{bmatrix}$ has mixed-sign eigenvalues,
$\ds \lambda= 8 \pm 2\sqrt{34}$, $\vecx_0$ is a saddle point.

\item We have $\ds \nabla f(\vecx)=\begin{bmatrix} -4x_1+6x_2-6 \\ 6x_1-10x_2+8 \end{bmatrix}$, which yields the critical point, $\ds \vecx_0=\begin{bmatrix} -3 \\ -1 \end{bmatrix}$.
Since $\ds H_f(\vecx)=\begin{bmatrix} -4 & 6 \\ 6 & -10 \end{bmatrix}$ has negative eigenvalues,
$\ds \lambda= -7 \pm 3\sqrt{5}$, we see that $f$ is strictly concave on $\R^2$ so that
$\vecx_0$ is a global maximum.

\item We have
$\ds \nabla f(\vecx)=\begin{bmatrix} 4x_1^3-24x_1^2+48x_1-32 \\ 8x_2-4 \end{bmatrix}$, which yields a single critical point at $\ds \vecx_0=\begin{bmatrix} 2 \\ 1/2 \end{bmatrix}$.
The Hessian simplifies to
$\ds H_f(\vecx)=\begin{bmatrix} 12(x_1-2)^2 & 0 \\ 0 & 8 \end{bmatrix}$ and has
 eigenvalues of $12(x_1-2)^2$ and $8$. Thus, $f$ is concave on $\R^2$ and
$\vecx_0$ is a global maximum.

\item We have
$\ds \nabla f(\vecx)=\begin{bmatrix} \cos(x_1)\cos(x_2) \\ -\sin(x_1)\sin(x_2) \end{bmatrix}$, which yields four critical points: $\ds \vecx_0=\pm \begin{bmatrix}  \pi /2 \\ 0 \end{bmatrix}$
and $\ds \vecx_0=\pm \begin{bmatrix} 0 \\  \pi /2\end{bmatrix}$.
The Hessian is
\begin{equation*}
H_f(\vecx)=\begin{bmatrix} -\sin(x_1)\cos(x_2) & -\cos(x_1)\sin(x_2)
\\ -\cos(x_1)\sin(x_2) & -\sin(x_1)\cos(x_2) \end{bmatrix},
\end{equation*}
which yields a repeated eigenvalue, $\lambda=-1$, when
$\ds \vecx_0=\begin{bmatrix} \pi /2 \\ 0\end{bmatrix}$, a repeated eigenvalue
$\lambda=1$, when
$\ds \vecx_0=\begin{bmatrix} -\pi /2 \\ 0\end{bmatrix}$, and eigenvalues
$\lambda = \pm 1$, when $\ds \vecx_0=\begin{bmatrix}  0 \\ \pm \pi /2 \end{bmatrix}$.
Thus, $\ds \vecx_0=\begin{bmatrix} \pi /2 \\ 0\end{bmatrix}$ is a local maximum,
$\ds \vecx_0=\begin{bmatrix} -\pi /2 \\ 0\end{bmatrix}$ is a local minimum, and
$\ds \vecx_0=\begin{bmatrix}  0 \\ \pm \pi /2 \end{bmatrix}$ are saddle points.

\item  We have
$\ds \nabla f(\vecx)=\begin{bmatrix} 2x_1/(x_1^2+1) \\ x_2 \end{bmatrix}$, which yields a single critical point at the origin. Since $f$ is differentiable
and nonnegative on $\R^2$, we conclude immediately that the origin
is a global minimum. In addition,
\begin{equation*}
 H_f(\vecx)=\begin{bmatrix} \frac{2(1-x_1)^2}{(x_1^2+1)^2} & 0 \\ 0 \\ 1 \end{bmatrix}.
\end{equation*}
The eigenvalues of this matrix are positive when $-1 < x_1 < 1$.
Thus $f$ is is strictly convex its given domain.

\item If $\ds f(x_1,x_2)=e^{-\left(\frac{x_1^2+x_2^2}{2}\right)}$,
then $\ds \nabla f(\vecx)=f(\vecx) \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$
so that $f$ has a single critical point at the origin. The Hessian simplifies
to $\ds H_f(\vecx)= f(\vecx) \begin{bmatrix} x_1^2-1 & x_1x_2 \\ x_1x_2 \\ x_2^2-1 \end{bmatrix}$,
which has eigenvalues in terms of $\vecx$ given by
$\ds \lambda = \begin{bmatrix} -f(\vecx) \\ (x_1^2+x_2^2-1)f(\vecx)\end{bmatrix}$.
Since $f(\vecx) > 0$
and $ x_1^2+x_2^2 <1$, we have that $f$ is strictly concave on its given domain and the
origin is a global minimum.
\ee

\item We have
$\ds \nabla f(\vecx)=A\vecx-\vecb$, which is the zero vector precisely when
$\vecx_0=A^{-1}\vecb$. The Hessian of $f$ is simply $A$, so $f$ is strictly convex (resp.
strictly concave) on $\R^n$
when $A$ is positive definite (resp. negative definite). Thus, $\vecx_0$ is the
unique global minimum (resp. unique global maximum) of $f$.

\newpar
When $\ds A= \begin{bmatrix} 2 & 1 \\ 1 & 3 \end{bmatrix}$, $\vecb= \begin{bmatrix} -1 \\ 4 \end{bmatrix}$, and $c=6$, $\ds \vecx_0=\begin{bmatrix} -7/5 \\ 9/5 \end{bmatrix}$. The eigenvalues of $A$ are $\ds \lambda = \frac{5 \pm \sqrt{5}}{2}$, so $\vecx_0$ is the global minimum.
	
\item Write $\ds \vecn=\begin{bmatrix} n_1 \\ n_2 \\ n_3 \end{bmatrix}$. Since
$\vecn \ne \zerovec$, we lose no generality by assuming $n_3 \ne 0$. Solving
$\vecn^t \vecx=d$ for $x_3$ yields $x_3$ as a function of $x_1$ and $x_2$:
\begin{equation*}
f:\R^2 \to \R \mbox{ where } f(x_1,x_2)= x_1^2+x_2^2 +\frac{(d-n_1x_1-n_2x_2)^2}{n_3^2}.
\end{equation*}
The critical point of $f$ is most easily computed using Maple and simplifies to
$\ds \vecx_0= \begin{bmatrix} n_1 d/\|\vecn\|^2, n_1 d/\|\vecn\|^2 \end{bmatrix}$
%\left(\frac{n_1d}{\|\vecn\|^2}, \frac{n_2d}{\|\vecn\|^2}\right)$.
The eigenvalues of the Hessian are $\lambda_1=2$ and
$\lambda_2= \frac{2\|\vecn\|^2}{n_3^2}$ so that $f$ is strictly convex
and $\vecx_0$ is the global minimum. The corresponding shortest distance
is $\frac{|d|}{\|\vecn\|}$

\newpar
For the plane $x_1+2x_2+x_3=1$, $\ds \vecn=\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}$
and $d=1$. In this case,
$\ds \vecx_0= \begin{bmatrix} 1/14 \\ 1/7 \\ 3/14 \end{bmatrix}$ with a corresponding
distance of $\ds \frac{1}{\sqrt{14}}$.

\item The gradient of $f$ is $\ds \nabla f(\vecx)= \begin{bmatrix} 4x_1^3 \\ 2x_2 \end{bmatrix}$,
which vanishes at the origin. Since $f$ is nonnegative and $f(\zerovec)=0$, we see that
$\vecx_0=\zerovec$ is the global minimum. The Hessian of $f$ at the origin is
$\ds H_f(\zerovec)=\begin{bmatrix} 0 & 0 & 0 & 2 \end{bmatrix}$, which is positive
semidefinite.

\newpar
The function $f(x_1,x_2)=-x_1^4+x_2^2$ has a saddle point at the origin because
$f(x_1,0)=-x_1^4$ has a minimum at $x_1=0$ and $f(0,x_2)=x_2^2$ has a maximum
at $x_2=0$. The Hessian of $f$ at the origin is again
$\ds H_f(\zerovec)=\begin{bmatrix} 0 & 0 & 0 & 2 \end{bmatrix}$.

\item The function $f(\vecx)=x_1^4+x_2^4$ has a single critical point at $\vecx_0=\zerovec$, which
is a global minimum since $f$ is nonnegative and $f(\zerovec)=0$. The Hessian evaluated at $\vecx_0$ is the zero matrix, whose only eigenvalue is zero. Similarly,
$f(\vecx)=-x_1^4-x_2^4$ has a global maximum at $\vecx_0=\zerovec$, where
its Hessian is also the zero matrix.

\item 
\be
\item Player 1's optimal mixed strategy is the solution of
\begin{align*}
		 \mbox{maximize } &=z  \\
		\mbox{ subject to} \\
		2x_1-3x_2 &\geq z \\
		-x_1+4x_2 &\geq z \\
        x_1+x_2 &=1 \\
		x_1,x_2 &\geq 0,
		\end{align*}
which is given by $\ds \vecx_0=\begin{bmatrix} 7/10 \\ 3/10 \end{bmatrix}$,
with corresponding objective value $\ds z_0=\frac{1}{2}$.

\newpar
 Player 2's optimal mixed strategy is the solution of the corresponding dual LP,
\begin{align*}
		 \mbox{minimize } &=w  \\
		\mbox{ subject to} \\
		2y_1-y_2 &\leq w \\
		-3y_1+4y_2 &\leq w \\
        y_1+y_1 &=  1
		y_1,y_2 &\geq 0,
		\end{align*}
which is $\ds \vecy_0=\begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}$,
with corresponding objective value $\ds w_0=\frac{1}{2}$.

\item We have
\begin{align*}
f(x_1,y_1) &=\begin{bmatrix} y_1 \\ 1-y_1\end{bmatrix}^t A
\begin{bmatrix} x_1 \\ 1-x_1 \end{bmatrix} \\
&=10x_1y_1-5x_1-7y_1+4,
\end{align*}
whose gradient, $\ds \nabla f(x_1,y_1)$ vanishes at $\ds x_1=\frac{7}{10}$,
$\ds y_1=\frac{1}{2}$. The Hessian of $f$ is a constant matrix having eigenvalues
$\lambda=\pm 10$ so that this critical point is a saddle point. The game value is
$\ds f\left(\frac{7}{10},\frac{1}{2}\right)=\frac{1}{2}$.

\item The only solution of $f(x_1,y_1)=\frac{1}{2}$ is simply
$\ds \left(\frac{7}{10},\frac{1}{2}\right)$.

\item A game value 20\% higher than $\ds \frac{1}{2}$ is $\ds \frac{3}{5}$. The
equation $\ds f(x_1,y_1)=\frac{3}{5}$ simplifies to
\begin{equation*}
10x_1y_1-5x_1-7y_1+\frac{17}{5}=0.
\end{equation*}

The graph of this relation is shown in Figure \ref{Fi:s06x4x2}.

\begin{figure}[h]
\centering
\psfrag{x1axislabel}[Bc][Bc]{$x_1$}
\psfrag{x2axislabel}[Bc][Bc]{$y_1$}
\includegraphics[width=1\linewidth]{ExerciseSolutions/images/s06x4x2.eps}
\caption{The relation $\ds 10x_1y_1-5x_1-7y_1+\frac{17}{5}=0$.}
\label{Fi:s01x2x1a}
\end{figure}

\ee

\item Calculations, which are most easily performed with Maple, establish that
$\ds f(x_1,y_1) =\begin{bmatrix} y_1 \\ 1-y_1\end{bmatrix}^t A
\begin{bmatrix} x_1 \\ 1-x_1 \end{bmatrix}$
has a saddle point at $\ds x_1 = \frac{d-b}{a+d-b-c}$, $\ds y_1=\frac{d-c}{a+d-b-c}$. Since
\begin{equation*}
f\left( \frac{d-b}{a+d-b-c}, \frac{d-c}{a+d-b-c}\right)=\frac{ad-bc}{a+d-b-c},
\end{equation*}
the game is fair provided $\det A \ne 0$, or, in other words, if $A$ is noninvertible.

\ee



