\be
\item Consider the quadratic programming problem given by
\begin{align*}
 \mbox{minimize} f(x_1, x_2) &=5x_1^2+4x_1x_3+8x_2^2+x_3^2+x1+2x_2-x_3  \\
	\mbox{ subject to} \\
	 x_1-x_2+x_3 &= 1\\
	x_1+2x_2+x_3 &=-3.
	\end{align*}	
\be
\item Rewrite the problem in the standard form (\ref{E:QPGeneralForm}). (Hint: The matrix
$Q$ is simply the Hessian of $f$.)
\item Explain why the problem is convex. Then determine its solution using formula
(\ref{E:QPKKTPartionedMatrix}).
\ee

\item Solve each of the following nonconvex, quadratic programming problems.

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

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

\item
\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 Q=\begin{bmatrix} 2 & 4 & 0 & 0 \\ 4 & 7 & -2 & -1 \\
0 & -2 & -3 & -1 \\ 0 & -1 & -1 & 0 \end{bmatrix}$,
$\ds \vecp=\begin{bmatrix} 2 \\ -3 \\ 0 \\ 1 \end{bmatrix}$.
$\ds A= \begin{bmatrix} 1 & 2 & 3 & -1 \\ 0 & -5 & 4 & 2 \\ 3 & 1 & 5 & 6  \end{bmatrix}$,
$\ds \vecb=\begin{bmatrix} 2 \\ 4 \\ 3 \end{bmatrix}$,
$\ds C= \begin{bmatrix} 1 & 1 & 1 & 3 \\ -1 & 3 & 1 & 0  \end{bmatrix}$ and
$\ds \vecd=\begin{bmatrix} 1 \\ 1 \end{bmatrix}$.
\ee

\item Verify formula (\ref{E:QPKKTPartionedMatrixInverse}). That is, 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}
where $\ds S=-AQ^{-1}A^t$.

\item An individual's blood type (A, B, AB, or O) is determined by a pair of inherited alleles, of which there are three possibilities: A, B, and O, where A and B are dominant over O.
    Table \ref{Ta:ExercisesQPBloodTyes} summarizes the blood types produced by each allele pair. Note that the allele pairs AO=OA and BO=OB result in blood types A and B, respectively, due to the dominate nature of A
    and B.

\begin{table}[h]
\caption{Blood types produced by different allele pairs}\label{Ta:ExercisesQPBloodTyes}
\begin{tabular}{|c|c|c|c|}
\hline
\multicolumn{4}{|c|}{First Allele}\\ \hline
Second & A & B & O  \\ \hline
A & AA=A & AB  &  AO=A  \\ \hline
B &  BA=AB & BB=B & BO=B   \\ \hline
O &  OA=A  & OB=B & OO=O    \\ \hline
\end{tabular}
\end{table}

\noi
Let $\ds \vecx=\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}$ be a vector whose entries represent the
frequencies of the alleles, A, B, and C, within a certain population. An individual is
heterozygous for blood type if he or she inherits different allele types. Since
\begin{equation*}
1=(x_1+x_2+x_3)^2= x_1^2+2x_1x_2+2x_1x_3+x_2^2+2x_2x_3+x_3^2,
\end{equation*}
the probability that an individual is heterozygous is then given by
$\ds 2x_1x_2+2x_1x_3+2x_2x_3$.

\newpar
Determine the values of $x_1$, $x_2$, and $x_3$ that maximize the preceding probability by constructing and then solving a quadratic programming problem of the form (\ref{E:QPGeneralForm}).

\item Consider the special case of the bimatrix game when Steve's payoff matrix, $B$, equals $-A$. Show that if we identify $z_1$ with $w$ and $z_2$ with $-z$, then the solution of
    (\ref{E:QPBimatrixGameQuadProgram}) coincides with that of the zero-sum matrix game
    as formulated in Section \ref{S:ZeroSumMatrixGameIntroduction}. (Hint: When $B=-A$, the objective
    in (\ref{E:QPBimatrixGameQuadProgram}) reduces to one of minimizing
    \begin{align*}
    f(\vecz,\vecx,\vecy )&= \vece^t \vecz - \vecx^t (A+B) \vecy \\
    &= \vece^t\vecz \\
    &= z_1 + z_2 \\
    &= w - z,
    \end{align*}

    \noi
    which is achieved by minimizing $w$ and maximizing $z$. Show the the constraints
    from (\ref{E:QPBimatrixGameQuadProgram}) then coincide with the feasibility of
    $\vecx$ for Ed's (primal) LP and $\vecy$ for Steve's (dual) LP as constructed in
    Section \ref{S:ZeroSumMatrixGameIntroduction}.)

\item In the game of ``chicken'' two individuals drive their cars toward one another at high
speeds. If Driver A swerves and the Driver B continues to along his or her straight-line path,
then Driver B receives recognition for his bravery and Driver A is deemed a ``chicken.'' To these outcomes we associate payoffs of 2 and 0 respectively. Similarly, if Driver B swerves and Driver A continues along his straight-line path, then Driver A is considered
``brave'' and Driver B a ``chicken.'' If both drivers continue straight-on, they crash into one another,
an outcome we associate with payoffs of -1 for each driver. Finally, if both drivers swerve, they
are each awarded payoffs of 1 for having the common sense to avoid a collision.

\newpar
Based upon the rules of the game, we can associate to the two drivers the following payoff
matrices, where row 1 and column 1 are associated with continuing straight and row 2 and column
2 to swerving:

\begin{equation*}
A=\begin{bmatrix} -1 & 0 \\ 2 & 1 \end{bmatrix} \mbox{  and  }
B=\begin{bmatrix} -1 & 2 \\ 0 & 1 \end{bmatrix}
\end{equation*}

\noi
Set up and solve a quadratic programming that determines the all Nash equilibria for the game. There are
three. Two are pure strategy equilibria, where one driver always continues driving
straight and the other swerves, and vice-versa. The third equilibrium is of mixed-strategy
 type in which each
driver elects to continue straight or to swerve with a non-zero probability.


\ee





