\section{Quadratic Programming}\label{S:ExerciseSolutionsQuadraticProgrammming}
\setcounter{progress_ck_counter}{0}

\be
\item

\be
\item The Hessian of $f$ is $\ds \begin{bmatrix} 10 & 0 & 4 \\ 0 & 16 & 0 \\ 4 & 0 & 2 \end{bmatrix}$.
If $\ds \vecp=\begin{bmatrix} 1 \\ 2 \\ -1\end{bmatrix}$, $\ds A=\begin{bmatrix} 1 & -1 & 1 \\ 1 & 2 & 1 \end{bmatrix}$,
and $\ds \vecb=\begin{bmatrix} 1 \\ -3\end{bmatrix}$, then the problem is given as

\begin{align*}
 \mbox{ minimize }  f(\vecx)&= \frac{1}{2} \vecx^t Q \vecx +\vecp^t\vecx  \\
	\mbox{ subject to} & \\
	A\vecx &= \vecb.
	\end{align*}	

\item The eigenvalues of $Q$ are $\lambda=1$ (repeated) and $\lambda=2$, so $Q$
is positive definite and the problem is convex. Thus,
\begin{align*}
\begin{bmatrix} \muvec_0 \\ \vecx_0 \end{bmatrix}
&= \begin{bmatrix}
0_{m\times m} & A \\
A^t & Q
\end{bmatrix}^{-1}\begin{bmatrix} \vecb \\ -\vecp \end{bmatrix} \\
&= \begin{bmatrix} -44/9 \\ 65/9 \\ -1/3 \\ -4/3 \\ 0 \end{bmatrix}.
\end{align*}

\noi The problem then has its solution given by $\vecx_0=\ds \begin{bmatrix} 1/3 \\ -4/3 \\ 0 \end{bmatrix}$. The
corresponding objective value is $\ds f(1/3,-4/3)=\frac{106}{9}$.
\ee

\item
\be
\item The matrix $Q$ is indefinite. However, the partitioned matrix,
$\ds \begin{bmatrix}
0_{m\times m} & A \\
A^t & Q
\end{bmatrix}$ is still invertible so that

\begin{align*}
\begin{bmatrix} \muvec_0 \\ \vecx_0 \end{bmatrix}
&= \begin{bmatrix}
0_{m\times m} & A \\
A^t & Q
\end{bmatrix}^{-1}\begin{bmatrix} \vecb \\ -\vecp \end{bmatrix} \\
&= \begin{bmatrix} -259/311 \\ 178/311 \\ -191/311 \\ -11/311 \\ -142/311 \end{bmatrix}.
\end{align*}

\noi Thus, the problem has a unique KKT point,
$\ds \vecx_0=\begin{bmatrix} -191/311 \\ -11/311 \\ -142/311 \end{bmatrix}$, with
corresponding multiplier vector, $\ds \muvec_0=\begin{bmatrix} -259/311 \\ 178/311 \end{bmatrix}$. The bordered
Hessian becomes
\begin{equation*}
B=\begin{bmatrix} 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & -4 & 0 & 1 \\ -1 & -4 & 1 & -2 & 0 \\ 2 & 0 &-2 & 3 & 1 \\
-1 & 1 & 0 & 1 & 3 \end{bmatrix}.
\end{equation*}

\newpar
In this case there are $n=3$ decision variables and $m=2$ equality constraints. Since the
determinants of both $B$ and its leading principal minor of order 4 are positive, we see
that $\vecx_0$ is the solution.

\item The problem has a unique KKT point given by $\ds \vecx_0=\begin{bmatrix} 6 \\ 13/4 \\ 1/4 \end{bmatrix}$
with corresponding multiplier vector, $\ds \lambdavec_0=\begin{bmatrix} 5/2 \\ 3 \\ 0 \end{bmatrix}$. At
$\vecx_0$ only the first two constraints of $C\vecx \leq \vecd$ are binding. Thus, we
set $\ds \tilde{C}=\begin{bmatrix} -1 & 2 & 2 \\ 1 & -1 & 3 \end{bmatrix}$ and
$\ds \tilde{\vecd}=\begin{bmatrix} 1 \\ 2 \end{bmatrix}$, in which case

\begin{equation*}
B=\begin{bmatrix} 0 & 0 & -1 & 2 & 2 \\ 0 & 0 & 1 & -1 & -3 \\ -1 & 1 & 1 & -2 & 0 \\
2 & -1 & -2 & 3 & 1 \\ 2 & -3 & 0 & 1 & 3 \end{bmatrix}.
\end{equation*}

\noi There are $n=3$ decision variables, $m=0$ equality constraints, and $k=2$ binding
inequality constraints. Since the determinant of $B$ and its leading principal minor of order 4 are positive,
we see that $\vecx_0$ is the solution.

\item The are two KKT points. The first is given by
$\ds \vecx_0=\begin{bmatrix} -17/40 \\ -1/10 \\ 7/8 \\ 0 \end{bmatrix}$
with corresponding multiplier vectors, $\ds \lambdavec_0 \approx \begin{bmatrix} 0 \\ 1.5788 \end{bmatrix}$
and $\ds \muvec_0 \approx \begin{bmatrix} .4405 \\ -.2806 \\ 1.295 \end{bmatrix}$. The second
constraint is binding at $\vecx_0$, so we set
$\ds \tilde{C}=\begin{bmatrix} -1 & 3 & 1 & 0 \end{bmatrix}$ and
$\ds \tilde{\vecd}=\begin{bmatrix} 1 \end{bmatrix}$, in which case,
\begin{align*}
B&=\begin{bmatrix} 0_{3 \times 3} & 0_{3 \times 1} & A \\
0_{1 \times 3} & 0 & \tilde{C} \\
A^t & \tilde{C}^t & Q \end{bmatrix} \\
&= \begin{bmatrix} 0 & 0 & 0 & 0 1 & 2 & 3 & -1 \\
0 & 0 & 0 & 0 & 1 & 2 & 3 & -1 \\
0 & 0 & 0 & 0 & 0 & -5 & 4 & 2 \\
0 & 0 & 0 & 0 & 3 & 1 & 5 & 6 \\
0 & 0 & 0 & 0 & -1 & 3 & 1 & 0 \\
1 & 0 & 3 & -1 & 2 & 4 & 0 & 0  \\
2 & -5 & 1 & 3 & 4 & 7 & -2 & -1 \\
3 & 4 & 5 & 1 & 0 & -2 & -3 & -1 \\
-1 & 2 & 6 & 0 & 0 & -1 & -1 & 0
\end{bmatrix}
\end{align*}

\noi There are $n=4$ decision variables, $m=3$ equality constraints, and $k=1$ binding
inequality constraints. Since $n-m-k=0$, we only need to check that the determinant of $B$ itself has
the same sign as $(-1)^{m+k}=1$, which it does. Hence, $\ds \vecx_0=\begin{bmatrix} -17/40 \\ -1/10 \\ 7/8 \\ 0 \end{bmatrix}$ is a solution.

\newpar
The second KKT point is given by
$\ds \vecx_0 \approx \begin{bmatrix} 7.593 \\ -2.406 \\ -.9591 \\ -2.096 \end{bmatrix}$
with corresponding multiplier vectors, $\ds \lambdavec_0 =\begin{bmatrix} 0 \\ 0 \end{bmatrix}$
and $\ds \muvec_0 \approx \begin{bmatrix} -2.550 \\ 1.555 \\ -1.671 \end{bmatrix}$. In this case neither
inequality constraint is binding. Performing an analysis similar to that done for the first KKT point
leads to a situation in which the bordered Hessian test is inconclusive. In fact,
$\ds f(\vecx_0) \approx 12.1$, whereas
$\ds f\left( \begin{bmatrix} -17/40 \\ -1/10 \\ 7/8 \\ 0 \end{bmatrix}\right) \approx -1.138$
\ee

\item To show that
\begin{equation}\label{E:QPKKTPartionedMatrixInverse}
\begin{bmatrix}
0_{m\times m} & A \\
A^t & Q
\end{bmatrix}^{-1}
=  \begin{bmatrix} S^{-1} & -S^{-1}AQ^{-1} \\
-Q^{-1}A^t S^{-1} & Q^{-1}(Q+A^tS^{-1} A) Q^{-1}
\end{bmatrix},
\end{equation}
we will verify that the product of $\ds \begin{bmatrix}
0_{m\times m} & A \\
A^t & Q
\end{bmatrix}$ and $\ds  \begin{bmatrix} S^{-1} & -S^{-1}AQ^{-1} \\
-Q^{-1}A^t S^{-1} & Q^{-1}(Q+A^tS^{-1} A) Q^{-1}
\end{bmatrix}$ is the $(m+n)$-by-$(m+n)$ identity matrix. Viewing each of these two partitioned matrices as being comprised
of four blocks, we calculate four different products as follows:

\noi Top left block of product:
\begin{align}\label{E:QPBlock1}
0_{m\times m}S^{-1} - A Q^{-1}A^t S^{-1}
&= -AQ^{-1}A^t (-AQ^{-1}A^t)^{-1}  \\
&= I_{m \times m} \notag
\end{align}

\noi Bottom left block of product:
\begin{align}\label{E:QPBlock2}
A^t S^{-1} -Q Q^{-1}A^t S^{-1} &= A^t S^{-1} -A^t S^{-1}  \\
&= 0_{n \times m}
\end{align}

\noi Top right block of product:
\begin{align}\label{E:QPBlock3}
-0_{m\times m} S^{-1}AQ^{-1} + A Q^{-1}\left(Q+A^t S^{-1} A\right) Q^{-1}
&=A Q^{-1}\left(Q+A^t S^{-1} A\right) Q^{-1}  \\
&= A Q^{-1}Q Q^{-1}+AQ^{-1}A^t S^{-1} A Q^{-1} \notag \\
&=AQ^{-1}+AQ^{-1}A^t\left(-A Q^{-1} A^t\right)^{-1} A Q^{-1} \\
&= A Q^{-1}-I_{m \times m} A Q^{-1} \\
&= 0_{m \times n}
\end{align}

\noi Bottom right block of product:
\begin{align}\label{E:QPBlock4}
-A^t S^{-1}AQ^{-1} + Q Q^{-1}\left(Q+A^t S^{-1} A\right)Q^{-1}
&= -A^t S^{-1}AQ^{-1} + \left(Q+A^t S^{-1} A\right)Q^{-1} \\
&= -A^t S^{-1}AQ^{-1} + I_{n \times n} +  A^t S^{-1} A Q^{-1} \notag \\
&= I_{n \times n}.
\end{align}

\noi
If we combine the results of (\ref{E:QPBlock1})-(\ref{E:QPBlock4}), we see that
\begin{align*}
\begin{bmatrix}
0_{m\times m} & A \\
A^t & Q
\end{bmatrix} \begin{bmatrix} S^{-1} & -S^{-1}AQ^{-1} \\
-Q^{-1}A^t S^{-1} & Q^{-1}(Q+A^tS^{-1} A) Q^{-1}
\end{bmatrix} &= \begin{bmatrix} I_{m \times m} & 0_{m \times n}  \\ 0_{n \times m} & I_{n \times n}\end{bmatrix}\\
&=I_{m+n}.
\end{align*}




\item We seek to maximize the probability an individual is heterozygous, namely
$\ds 2x_1x_2+2x_1x_3+2x_2x_3$, subject to the constraints that $x_1$, $x_2$, and $x_3$ are nonnegative
and sum to 1. Equivalently, we seek to minimize $\ds f(\vecx)=-(2x_1x_2+2x_1x_3+2x_2x_3)$ subject
to these same constraints. Since the Hessian of $f$ is
$\ds \begin{bmatrix} 0 & -2 & -2 \\ -2 & 0 & -2 \\ -2 & -2 & 0 \end{bmatrix}$, our quadratic programming
problem, in matrix form, is given by

\begin{align*}
 \mbox{ minimize }  f(\vecx)&= \frac{1}{2} \vecx^t Q \vecx +\vecp^t\vecx  \\
	\mbox{ subject to} & \\
	A\vecx &= \vecb \\
C\vecx &\leq \vecd,
	\end{align*}	
where $\ds A = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix}$, $\ds \vecb=1$,
$C=-I_3$, and $\vecd= \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$.

\newpar
The Lagrangian has a unique KKT point at $\ds \vecx_0=\begin{bmatrix} 1/3 \\ 1/3 \\ 1/3 \end{bmatrix}$,
with corresponding multiplier vectors, $\lambdavec_0=\begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$
and $\ds \muvec_0=\frac{4}{3}$, and corresponding objective value $\ds f(\vecx_0)=-\frac{2}{3}$. None
of the three inequality constraints are binding, so the bordered Hessian is simply

\begin{equation*}
B \begin{bmatrix} 0 & 1 & 1 & 1 \\
1 & 0 & -2 & -2 & -2 \\
1 & -2 & 0 & -2 \\
1 & -2 & -2 & 0
\end{bmatrix}
\end{equation*}

\noi In this case, $n=3$, $m=1$, and $k=0$, so we only need to check that $\det (B)$ has the same sign
as $(-1)^{m+k}=-1$. Since $\det (B)=-12$, $\vecx_0$ is optimal.

\item The solution of the bimatrix game is given by the solution of the quadratic programming
problem

\begin{align*}
 \min_{\vecz,\vecx,\vecy}  f(\vecz,\vecx,\vecy )&= \vece^t \vecz - \vecx^t (A+B) \vecy  \\
	\mbox{ subject to} & \\
	A^t \vecy &\leq z_1 \vece  \\
    B \vecx &\leq z_2 \vece  \\
    \vece^t \vecx &=1  \\
    \vece^t \vecy &=1  \\
    \vecx, \vecy &\geq  \notag,
    \end{align*}

If $B=-A$ and if we denote $\ds \vecz=\begin{bmatrix} w \\ -z \end{bmatrix}$, then
$\ds \begin{bmatrix} \vecz,\vecx,\vecy \end{bmatrix}$ is feasible
for the quadratic programming problem if and only if all 4 of the following conditions hold:
\be
\item $B \vecx \leq -z$,i.e.,
$A\vecx \geq z$,
\item $A^t \vecy \leq w$, i.e., $\vecy^t A \leq w$,
\item $\vece^t \vecx =1$, and
\item $\vece^t \vecy=1$.
\ee

\noi But for the 2 LPs that comprise the zero-sum matrix game, these 4 conditions hold if and only if both $\vecx$ and $\vecy$ are primal and dual
feasible, respectively, with corresponding objective values, $w$ and $z$. Thus the solution of the quadratic
programming problem coincides with the solutions of the LP and corresponding dual LP that comprise
the solution of the zero-sum matrix game.


\item One equilibrium solution arises when Driver A always drives straight and Driver B always swerves.
In this case, Driver A's pure strategy yields a payoff of 2 and Drivers B's a payoff of 0. An analogous result holds if the drivers' pure strategies are interchanged.

\newpar
To determine the mixed-strategy equilibrium, we set 
\begin{equation*}
Q = \begin{bmatrix} 0_{2 \times 2} & 0_{2 \times 2} & 0_{2 \times 2} \\
0_{2 \times 2} & 0_{2 \times 2} & -(A+B) \\
0_{2 \times 2} & -(A+B)^t & 0_{2 \times 2}
\end{bmatrix},
\end{equation*}
$\ds \vecp=\begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$,
and
\begin{equation*}
C=\begin{bmatrix} M_1 &  0_{2 \times 2} & A^t \\
M_2 & B &  0_{2 \times 2} \\
0_{2 \times 2} & -I_2  & 0_{2 \times 2} \\
  0_{2 \times 2} & 0_{2 \times 2}  & -I_2
  \end{bmatrix},
\end{equation*}
where $\ds M_1= \begin{bmatrix} -1 & 0 \\ -1 & 0 \end{bmatrix}$,
and $\ds M_2= \begin{bmatrix} 0 & -1 \\ 0 & -1 \end{bmatrix}$. We also set
$\vecd=\zerovec_{8 \times 1}$,
$\ds E=\begin{bmatrix} 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$,
and $\ds \vecb = \vece=\begin{bmatrix} 1 \\ 1 \end{bmatrix}$. 


\newpar
Using Maple's \mf{QPSolve} command, we obtain a solution to the quadratic programming problem,
\begin{align*}
 \mbox{ minimize }  f(\vecw)&= \frac{1}{2} \vecw^t Q \vecw +\vecp^t\vecw  \\
	\mbox{ subject to} & \\
	E\vecw &= \vecb \\
C\vecw &\leq \vecd,
	\end{align*}	
given by 
\begin{align*} \vecw_0&= \begin{bmatrix} \vecz_0 \\ \vecx_0 \\ \vecy_0 \end{bmatrix}
&= \begin{bmatrix} 1/2 \\ 1/2 \\ 1/2 \\ 1/2 \\ 1/2 \\ 1/2\end{bmatrix}.
\end{align*}
Thus Driver A's equilibrium strategy consists of $\vecx_0=\begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}$, implying that he chooses to drive straight or to swerve with equal probabilities of $\ds \frac{1}{2}$ and
that his payoff is $\ds z_{0,1} = \frac{1}{2}$. Driver B's strategy and payoff are exactly the same.

\newpar
If we instead calculate the KKT points of the quadratic programming problem, we discover that there are exactly five:

\be
\item $\ds \vecw_0= \begin{bmatrix} 2 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \end{bmatrix}$,
with corresponding Lagrange multiplier vectors,
$\ds \lambdavec_0=\begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0\end{bmatrix}$
and $\ds \muvec_0=\begin{bmatrix} 2 \\ 0 \end{bmatrix}$, and with
objective value, $f(\vecw_0)=0$

\item $\ds \vecw_0= \begin{bmatrix} 0 \\ 2 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}$,
with corresponding Lagrange multiplier vectors,
$\ds \lambdavec_0=\begin{bmatrix} 0 \\ 1 \\ 1 \\ 0  \\ 1 \\ 0 \\ 0 \\ 1\end{bmatrix}$
and $\ds \muvec_0=\begin{bmatrix} 0 \\ 2 \end{bmatrix}$, and with
objective value, $f(\vecw_0)=0$

\item $\ds \vecw_0= \begin{bmatrix} 1/2 \\ 1/2 \\ 1/2 \\ 1/2 \\ 1/2 \\ 1/2 \end{bmatrix}$,
with corresponding Lagrange multiplier vectors,
$\ds \lambdavec_0=\begin{bmatrix} 1/2 \\ 1/2 \\ 1/2 \\ 1/2 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$
and $\ds \muvec_0=\begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}$, and with
objective value, $f(\vecw_0)=0$

\item $\ds \vecw_0= \begin{bmatrix} 1/4 \\ 5/4 \\ 1/4 \\ 3/4 \\ 3/4 \\ 1/4 \end{bmatrix}$,
with corresponding Lagrange multiplier vectors,
$\ds \lambdavec_0=\begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$
and $\ds \muvec_0=\begin{bmatrix} 0 \\ 1 \end{bmatrix}$, and with
objective value, $\ds f(\vecw_0)=\frac{1}{4}$

\item $\ds \vecw_0= \begin{bmatrix} 5/4 \\ 1/4 \\ 3/4 \\ 1/4 \\ 1/4 \\ 3/4 \end{bmatrix}$,
with corresponding Lagrange multiplier vectors,
$\ds \lambdavec_0=\begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$
and $\ds \muvec_0=\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, and with
objective value, $\ds f(\vecw_0)=\frac{1}{4}$
\ee

\noi The first two KKT points correspond to the two pure strategy equilibria and the third KKT to 
the mixed strategy equilibrium. That these are solutions of the original quadratic programming
problem can be verified by use of the bordered Hessian test. By mere inspection of objective values, we see that the latter two KKT points not solutions of the quadratic programming problem. In fact, the bordered Hessian test is inconclusive. Because these KKT points are not solutions of the problem, they do not constitute Nash equilibria.

\ee

\hrulefill

\newpar

\textbf{Solutions to Waypoints}


% PAGE 304

\endinput 


