%********MAPLE AND EXCEL****************************************************************************
\section{Quadratic Programming}\label{S:QP}	
\setcounter{progress_ck_counter}{0}

\noi Many real-world nonlinear programming problems are quadratic\index{quadratic programming} in nature. In this section we develop develop a framework for solving such problems.

\subsection{Problems with Equality-type Constraints Only}\index{quadratic programming!equality-type constraints}

\noi A quadratic
programming\index{quadratic programming!matrix form} problem is written in
matrix form as follows:

\begin{align}\label{E:QPGeneralForm}
 \mbox{ minimize }  f(\vecx)&= \frac{1}{2} \vecx^t Q \vecx +\vecp^t\vecx  \\
	\mbox{ subject to} & \notag\\
	A\vecx &= \vecb \notag\\
C\vecx &\leq \vecd, \notag
	\end{align}	

\noi where $\vecx$ belongs to $\R^n$, $Q$ is a symmetric $n$-by-$n$ matrix, $A$ is an $m$-by-$n$ matrix,
$C$ is a $p$-by-$n$ matrix, and $\vecb$ and $\vecd$ belong to $\R^m$ and $\R^p$, respectively.

\newpar
As a first step towards solving (\ref{E:QPGeneralForm}), we consider the special case when
it has only equality-type constraints. In other words, we seek to solve

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

\noi
We will assume that the system of equations $A \vecx =\vecb$ is consistent and that no single equation
comprising the system is a linear combination of the others. Therefore, the rows of $A$ must form
a linearly independent set of vectors, so that $m \leq n$ and any KKT point is regular.

\newpar The Lagrangian corresponding to (\ref{E:QPGeneralFormEQConstraints}) is given by
\begin{equation}\label{E:QPEqualityLagrangian}
L(\vecx,\muvec)= f(\vecx)+\muvec^t \left(A\vecx-\vecb\right) \mbox{ where } \muvec \in \R^p.
\end{equation}
By Theorem \ref{Th:KKTTheorem}, if $\vecx_0$ is a solution
of (\ref{E:QPGeneralFormEQConstraints}), then it must be feasible, i.e., $A\vecx_0=\vecb$, and
satisfy

\begin{align}\label{E:QPKKTConditions}
\zerovec &= \nabla L(\vecx_0) \\
&= \nabla f(\vecx) + A^t \muvec_0 \notag \\
 &= Q\vecx_0 +\vecp+A^t \muvec_0 \notag
\end{align}
for some $\muvec_0$ in $\R^p$.

\newpar
These conditions may be conveniently combined into the form of a partitioned
matrix equation,

\begin{equation}\label{E:QPKKTPartionedMatrix}
\begin{bmatrix}
0_{m\times m} & A \\
A^t & Q
\end{bmatrix} \begin{bmatrix} \muvec_0 \\ \vecx_0 \end{bmatrix}
= \begin{bmatrix} \vecb \\ -\vecp \end{bmatrix}.
\end{equation}

\newpar
In the ideal situation, the matrix $Q$ is positive definite. When this occurs
(\ref{E:QPGeneralFormEQConstraints}) is a convex NLP so that any solution
of (\ref{E:QPKKTPartionedMatrix}) yields a regular KKT point, $\vecx_0$, which is
a solution of (\ref{E:QPGeneralFormEQConstraints}) by Theorem \ref{Th:ConvexNLPsMainResult}.

\newpar
When $Q$ is positive definite, the coefficient matrix in (\ref{E:QPKKTPartionedMatrix}) is invertible. In particular, if we denote
$\ds S=-AQ^{-1}A^t$, the inverse is given
by
\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}

\noi
The matrix $S$ is called the \emph{Schur Complement}\index{Schur Complement} of $Q$ in
the coefficient matrix in (\ref{E:QPKKTPartionedMatrix}). That $S$ itself is invertible can
be proven using the Spectral Theorem.

\newpar
For example, suppose $\ds Q= \begin{bmatrix} 2 & 2 & 0 \\ 2 & 4 & 1 \\ 0 & 1 & 5 \end{bmatrix}$,
$\ds \vecp=\begin{bmatrix} 2 \\ -3 \\ 0 \end{bmatrix}$,
$\ds A= \begin{bmatrix} 1& 2 & 2 \\ 1 & 0 & 0 \end{bmatrix}$, and
$\ds \vecb=\begin{bmatrix} 1 \\ 2 \end{bmatrix}$. The eigenvalues of $Q$ are positive, so
$Q$ is positive definite. The solution of
(\ref{E:QPKKTPartionedMatrix}) is given by
\begin{equation*}
\begin{bmatrix} \muvec_0 \\ \vecx_0 \end{bmatrix} \approx
\begin{bmatrix} .3929 \\ -5.5357 \\ 2 \\ -.4286 \\ -.0714 \end{bmatrix}
\end{equation*}
with corresponding objective value $f(\vecx_0) \approx 7.9821$.

\newpar
When $Q$ is not positive definite, the situation becomes somewhat more complicated. In this case,
equation (\ref{E:QPKKTPartionedMatrix}) still remains valid. However, the coefficient
matrix need not be invertible and, even if it is, (\ref{E:QPGeneralFormEQConstraints})
is no longer a convex NLP, so a solution of (\ref{E:QPKKTPartionedMatrix}) need not
yield a solution of the original problem.

\newpar
Fortunately, a tool exists for circumventing this problem, one that applies to many situations. To understand the rationale behind it, we first consider a simple example. Suppose, in
(\ref{E:QPGeneralFormEQConstraints}), that
$\ds Q=\begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}$,
$\vecp = \zerovec$,
$\ds A=\begin{bmatrix} 1 & -1 \end{bmatrix}$, and $\vecb=1$.
(For the sake of consistent notation throughout the discussion, we
express $\vecb$ using vector notation even though it is a scalar for this particular problem.)
The feasible region for this NLP consists of the line $x_1-x_2=1$ in $\R^2$. However, the eigenvalues of $Q$ are mixed-sign, so the NLP is not convex.

\newpar
Figure (\ref{Fi:QP_ParabolaOnSaddle}) depicts the graph of the objective function, $f$, a saddle-shaped
surface, along with the image under $f$ of the line $x_1-x_2=1$, which constitutes a parabola
embedded in the surface.
\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\includegraphics[width=.8\linewidth]{images/f09x04x01.eps}
\caption{Quadratic form, $f$, together with the image under $f$ of the line $x_1-x_2=1$. }
\label{Fi:QP_ParabolaOnSaddle}
\end{figure}

\noi Observe that while the graph
of $f$ is saddle-shaped, the restriction of $f$ to the line $x_1-x_2=1$ is an upward-opening parabola. In fact, if we substitute $x_2=x_1-1$ into $\ds f(\vecx)=\vecx^t Q \vecx$, we obtain
\begin{align*}
\ds f(\vecx)&=f(x_1,x_1-1) \\
&= \begin{bmatrix} x_1 \\ x_1-1 \end{bmatrix}^t Q  \begin{bmatrix} x_1 \\ x_1-1 \end{bmatrix} \\
&= \frac{1}{2}x_1^2+2x_1x_2-\frac{1}{2}x_2^2 \\
&= 2x_1^2-x1-\frac{1}{2},
\end{align*}
which is a convex function of $x_1$ and has
a minimum at $\ds x_1=\frac{1}{4}$. This value corresponds to $x_2=-\frac{3}{4}$ so
that $\ds \vecx_0 =\begin{bmatrix} 1/4 \\ -3/4 \end{bmatrix}$ is the solution
of (\ref{E:QPGeneralFormEQConstraints}). Observe this result can also be
obtained by solving (\ref{E:QPKKTPartionedMatrix}), in which case
\begin{equation*}
\begin{bmatrix} \muvec_0 \\ \vecx_0 \end{bmatrix} =
\begin{bmatrix} -1 \\ 1/4 \\ -3/4  \end{bmatrix}.
\end{equation*}

\newpar
Although the calculations are somewhat tedious, we can replicate the previous steps to show that if $\ds Q=\begin{bmatrix} q_1 & q \\ q & q_2 \end{bmatrix}$,
$\vecp = \zerovec$,
$\ds A=\begin{bmatrix} a_1 & a_2 \end{bmatrix}$, and $\vecb \in \R$,
then the restriction of $\ds f(\vecx)= \frac{1}{2} \vecx^t Q \vecx$ to the
set of
vectors $\ds \vecx=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ satisfying
$A\vecx=\vecb$ is a quadratic expression in $x_1$, whose leading coefficient is given by
$\ds \frac{q_1 a_2^2-2q a_2 a_1 + q_2 a_1^2}{2a_2^2}$. Thus, as a function of $x_1$ alone,
this restriction of $f$ is convex provided
$\ds q_1^2 a_2^2-2q a_2 a_1 + q_2 a_1^2>0$. This was the case in our preceding example,
where $q_1=1$, $q_2=-1$, $q=2$, $a_1=1$, and $a_2=-1$.

\newpar
The condition $\ds \frac{q_1^2 a_2^2-2q a_2 a_1 + q_2 a_1^2}{2a_2^2}>0$
can be restated in terms of a determinant identity. Namely, it holds provided
\begin{align*}
-\det \left(\begin{bmatrix}
0 & A \\
A^t & Q
\end{bmatrix}\right)
&=-\det \left( \begin{bmatrix} 0 & a_1 & a_2 \\ a_1 & q_1 & q \\ a_2 & q & q_2 \end{bmatrix} \right) \\
&= q_1^2 a_2^2-2q a_2 a_1 + q_2 a_1^2 \\
&>0.
\end{align*}

\newpar
The matrix $\ds B=\begin{bmatrix} 0 & A \\ A^t & Q \end{bmatrix}$, which is identical to the
 coefficient matrix in (\ref{E:QPKKTPartionedMatrix}), is known as a
 \emph{bordered Hessian}\index{bordered Hessian}.
It consists of the Hessian of $f$, $Q$ in this case, bordered above by $A$ and to the left by $A^t$. In the absence of constraints, $B$ is simply
$Q$. Thus, the bordered Hessian can be viewed as a generalization of the normal Hessian
to the constrained setting,
one that incorporates useful information regarding the constraints themselves. It is
an extremely useful tool for solving the quadratic programming problem (\ref{E:QPGeneralFormEQConstraints}).
However, before stating a general result that spells out how this is so, we introduce some new terminology.

\begin{definition}\label{Th:PrincipalMinor}
Suppose $M$ is an $n$-by-$n$ matrix. Then the \emph{leading principal minor
of order}\index{leading principal minor} $k$, where $0 \leq k \leq n$, is the determinant of the matrix
formed by deleting the last $n-k$ rows and the last $n-k$ columns of $M$.
\end{definition}

\newpar
Note that when $k=0$, the leading principal minor is just $M$ itself. With this terminology, we now
state a classic result, known as the
\emph{bordered Hessian test}\index{bordered Hessian!test}.

\begin{theorem}\label{Th:QPBorderedHessian}
Assume the quadratic programming problem (\ref{E:QPGeneralFormEQConstraints})
has a KKT point at $\vecx_0$ with corresponding multiplier vector, $\muvec_0$.
Let $B=\ds \begin{bmatrix} 0 & A \\ A^t & Q \end{bmatrix}$
denote the corresponding $(n+m)$-by-$(n+m)$ bordered Hessian formed using $Q$ and $A$.
Then $\vecx_0$ is a solution of (\ref{E:QPGeneralFormEQConstraints}) if the determinant of $B$ and the last $n-m$ leading principal minors of $B$ all have the same sign as $(-1)^m$.
\end{theorem}

\noi The proof of this result can be found in a variety of sources \cite{Marsden}. Instead of proving
it here, we examine its significance in the context of investigating a particular example.

\newpar
For example, suppose in (\ref{E:QPGeneralFormEQConstraints}) that
$\ds Q=\begin{bmatrix} 3 & -1 & 0 \\ -1 & 2 & 1 \\ 0 & 1 & -1 \end{bmatrix}$,
$\ds \vecp= \begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix}$,
\newline $\ds A= \begin{bmatrix} 1 & -1 & 2 \end{bmatrix}$, and $\vecb=1$.


\newpar
In this situation, $Q$ is indefinite and the solution to (\ref{E:QPGeneralFormEQConstraints})
is given by
\begin{align*}
\begin{bmatrix} \muvec_0 \\ \vecx_0 \end{bmatrix}
&= \begin{bmatrix} 5/6 \\ -31/24 \\ -25/24 \\ 5/8 \end{bmatrix} \\
&\approx \begin{bmatrix} .8333 \\ -1.2917 \\ -1.0417 \\ .625 \end{bmatrix}.
\end{align*}
The bordered Hessian, $B$, is the 4-by-4 matrix,
\begin{equation*}
B= \begin{bmatrix} 0 & 1 & -1 & 2 \\ 1 & 3 & -1 & 0 \\ -1 & -1 & 2 & 1 \\ 2 & 0 & 1 & -1
\end{bmatrix}.
\end{equation*}

\newpar
Since $n=3$ and $m=1$, we must compute the determinant of $B$ along with its last two leading principal minors. The determinant of $B$ is -24. The leading principal minor corresponding to deletion of the last row and column of $B$
equals -3, and that corresponding to deletion of the last two rows and columns equals -1. Since all three determinants have the same sign as $(-1)^m=-1$,
we conclude for this example that the solution of (\ref{E:QPGeneralFormEQConstraints}) is
\begin{align*}
\vecx_0
&= \begin{bmatrix} -31/24 \\ -25/24 \\ 5/8 \end{bmatrix} \\
&\approx \begin{bmatrix} -1.2917 \\ -1.0417 \\ .625 \end{bmatrix},
\end{align*}
with corresponding multiplier $\ds \muvec_0= \frac{5}{6} \approx .8333$.

\subsection{Inequality Constraints}\label{SS:QPInequalityConstraints}\index{quadratic programming!inequality-type constraints}

\noi We now consider the case when inequality constraints are present in (\ref{E:QPGeneralForm}). Assume that $\vecx_0$ is a KKT point for this problem. Each row of the $p$-by-$n$ matrix $C$ corresponds to a constraint. Assume $k$ of these constraints are binding. Let $\tilde{C}$ be the
submatrix of $C$ consisting of these $k$ rows, and let $\tilde{\vecd}$ denote the vector
formed using the corresponding $k$ entries of $\vecd$. Note that
\begin{equation*}
\begin{bmatrix} A \\ \tilde{C} \end{bmatrix} \vecx_0= \begin{bmatrix} \vecb \\ \tilde{\vecd} \end{bmatrix}.
\end{equation*}

\noi
We assume that the rows of $\ds \begin{bmatrix} A \\ \tilde{C} \end{bmatrix}$
form a linear independent set of vectors,
implying, as in the previous section, that $\vecx_0$ is regular and $m+k \leq n$.

\newpar
An extension of Theorem \ref{Th:QPBorderedHessian}, whose proof we also omit, uses
 the matrix $Q$ ``bordered'' by $\ds \begin{bmatrix} A \\ \tilde{C} \end{bmatrix}$ and its transpose. Specifically,
we form the $(m+k+n)$-by-$(m+k+n)$ bordered Hessian
\begin{equation*}
B=\begin{bmatrix} 0_{m \times m} & 0_{m \times k} & A \\
0_{k \times m} & 0_{k \times k} & \tilde{C} \\
A^t & \tilde{C}^t & Q \end{bmatrix}.
\end{equation*}
If the last $n-(m+k)$ leading principal minors of $B$ have the same sign as $(-1)^{m+k}$,
then $\vecx_0$ is a solution of (\ref{E:QPGeneralForm}).

\newpar
To illustrate this solution process, we solve
\begin{align}\label{E:QPMixedInequalityExample}
 \mbox{ minimize }  f(\vecx)&= \frac{1}{2} \vecx^t Q \vecx +\vecp^t\vecx  \\
	\mbox{ subject to} & \notag\\
	A\vecx &= \vecb \notag\\
C\vecx &\leq \vecd, \notag
	\end{align}	
where
$\ds Q=\begin{bmatrix} 1 & 2 & 0 \\ 2 & 4 & 1 \\ 0 & 1 & 3 \end{bmatrix}$,
$\ds \vecp= \begin{bmatrix} 2 \\ -3 \\ 0 \end{bmatrix}$,
$\ds A= \begin{bmatrix} 1 & 0 & 1 \end{bmatrix}$, $\vecb=2$,
$\ds C= \begin{bmatrix} 1 & 2 & 2 \\ 4 & 1 & 0 \end{bmatrix}$, and
$\ds \vecd=\begin{bmatrix} 2 \\ 5 \end{bmatrix}$.

\newpar
Elementary calculations using methods discussed in Section \ref{SS:SolvingConvexNLPs},
establish (\ref{E:QPMixedInequalityExample}) has a KKT point given by
$\ds \vecx_0 =\begin{bmatrix} 5/4 \\ -3/8 \\ 3/4 \end{bmatrix}$, with corresponding multipliers
$\ds \lambdavec_0=\begin{bmatrix} 5/8 \\ 0 \end{bmatrix}$ and
$\ds \muvec_0=-\frac{25}{8}$. Using $\vecx_0$, we see that only the first
 of the two constraints of the matrix inequality $\ds C\vecx \leq \vecd$ is binding, so we set
$\ds \tilde{C}=\begin{bmatrix} 1 & 2 & 2 \end{bmatrix}$. The two rows
forming $\ds \begin{bmatrix} A \\ \tilde{C} \end{bmatrix}$ are linearly independent,
so $\vecx_0$ is regular. The bordered
Hessian is given by
\begin{equation}\label{E:QPMixedInequalityBorderedHessian}
B=\begin{bmatrix}
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 2 & 2 \\
1 & 1 & 1 & 2 & 0 \\
0 & 2 & 2 & 4 & 1 \\
1 & 2 & 0 & 1 & 3
\end{bmatrix}.
\end{equation}

\noi
Since $n=3$, $m=k=1$, $n-(m+k)=1$ so that we must check that the determinant of $B$ and the leading principal minor corresponding to deletion of the last row and column of $B$ have the same sign as $(-1)^{m+k}=1$. The values of the two determinants are
given by 24 and 4, respectively, so we conclude that $\ds \vecx_0 =\begin{bmatrix} 5/4 \\ -3/8 \\ 3/4 \end{bmatrix}$ is the solution of (\ref{E:QPMixedInequalityExample}).

\subsection{Maple's \mf{QPSolve} Command}\label{S:QPMapleQPSolveCommand}\index{Maple!\mf{QPSolve}}

\noi
Maple's \mf{QPSolve} command, located within the \mf{Optimization} package, provides a convenient
means for solving quadratic programming problems. The command accepts arguments in the same format
as does \mf{NLPSolve}. However, an error message results if the function to be minimized is not quadratic or if any constraint is neither a linear equation nor a linear inequality. The most convenient way to use this command is to enter constraints in matrix form, in a manner similar to that done for the \mf{LPSolve} command from
Section \ref{S:LP_Prototype_Standard_Form_Matrix_Form}. To solve the quadratic programming
problem (\ref{E:QPGeneralForm}) having both equality and inequality constraints, we enter
the matrices $Q$, $A$, and $C$ along with the vectors $\vecp$, $\vecb$, and $\vecd$ and solve
the resulting problem with the command \mf{QPSolve([p,Q],[C,d,A,b])}. Note that the matrix
and vector constraints within the brackets are entered in the order of inequality constraints first.
To solve (\ref{E:QPGeneralForm}) where only inequality-type constraints are present, we enter \mf{QPSolve([p,Q],[C,d])}
and for the corresponding case of equality-type constraints, we use
\mf{QPSolve([p,Q],[NoUserValue,NoUserValue,A,b])}. As an example, consider problem
(\ref{E:QPMixedInequalityExample}),	where
$\ds Q=\begin{bmatrix} 1 & 2 & 0 \\ 2 & 4 & 1 \\ 0 & 1 & 3 \end{bmatrix}$,
$\ds \vecp= \begin{bmatrix} 2 \\ -3 \\ 0 \end{bmatrix}$,
$\ds A= \begin{bmatrix} 1 & 0 & 1 \end{bmatrix}$, $b=2$,
$\ds C= \begin{bmatrix} 1 & 2 & 2 \\ 4 & 1 & 0 \end{bmatrix}$, and
$\ds \vecd=\begin{bmatrix} 2 \\ 5 \end{bmatrix}$.

A Maple worksheet for solving this problem is as follows:
\begin{maplelist}
\item \mf{restart:with(LinearAlgebra):with(Optimization):}
\item \mf{Q:=Matrix(3,3,[1,2,0,2,4,1,0,1,3]):}
\item \mf{p:=<2,-3,0>:}
\item \mf{A:=Matrix(1,3,[1,0,1]):}
\item \mf{b:=<2>:}
\item \mf{C:=Matrix(2,3,[1,2,2,4,1,0]):}
\item \mf{d:=<2,5>:}
\item \mf{QPSolve([p,Q],[C,d,A,b]);}
\mo{\left[ 4.3125,\begin{bmatrix} 1.25 \\ -.375 \\ .75 \end{bmatrix} \right]}
\end{maplelist}

\noi
Note that \mf{p}, \mf{b}, and \mf{d} must be entered as vectors using either the $<,>$ notation or
the \mf{Vector} command. They may not be entered as matrices or as scalars.

\newpar
One drawback of the \mf{QPSolve} command is its inability to return the corresponding Lagrange
multipliers. To obtain these values, we must use tools introduced in the context of solving the \CM problem at the end of Section \ref{SS:SolvingConvexNLPs} and formulate the Lagrangian function.
Here is syntax that demonstrates an efficient means for constructing the Lagrangian corresponding
to a quadratic programming problem, such as (\ref{E:QPMixedInequalityExample}):

\begin{maplelist}
\item \mf{with(VectorCalculus):with(LinearAlgebra):}
\item \mf{Q:=Matrix(3,3,[1,2,0,2,4,1,0,1,3]):}
\item \mf{p:=Matrix(3,1,[2,-3,0]):}
\item \mf{x:=Matrix(3,1,[x1,x2,x3]):}
\item \mf{f:=unapply(1/2*(Transpose(x).Q.x)[1,1]+\newline (Transpose(p).x)[1,1],[x1,x2,x3]):}
\item \mf{A:=Matrix(1,3,[1,0,1]):}
\item \mf{b:=Matrix(1,1,[2]):}
\item \mf{h:=unapply(convert(A.x-b,Vector),[x1,x2,x3]):}
\item \mf{C:=Matrix(2,3,[1,2,2,4,1,0]):}
\item \mf{d:=Matrix(2,1,[2,5]):}
\item \mf{g:=unapply(convert(C.x-d,Vector),[x1,x2,x3]):}
\item \mf{lambda:=<lambda1,lambda2>:}
\item \mf{mu:=<mu1>:}
\item \mf{L:=unapply(f(x1,x2,x3)+(Transpose(lambda).g(x1,x2,x3)) \newline
+(Transpose(mu).h(x1,x2,x3),[x1,x2,x3,lambda1,lambda2,mu1]):}
\end{maplelist}

\noi
Observe the index, \mf{[1,1]}, added to \mf{(Transpose(x).Q.x)} in the fifth line
of the worksheet. It is required to convert \mf{(Transpose(x).Q.x)}, which
Maple views as a 1-by-1 matrix, to a scalar-valued
function. In essence, the added index, ``removes the brackets'' so to speak,
from the matrix \mf{(Transpose(x).Q.x)}. For identical reasons, we add brackets, \mf{[1,1]},
immediately after \mf{(Transpose(p).x)}.

\newpar
Once the Lagrangian, \mf{L}, has been created, KKT points and corresponding multipliers can be computed as was done in the \CM worksheet at the end of Section \ref{SS:SolvingConvexNLPs}.

\subsection{The Bimatrix Game}\label{S:QPBimatrixGame}\index{bimatrix game}

\noi
In Sections \ref{S:ZeroSumMatrixGameIntroduction} and \ref{S:SufficientSecondOrderConditions} we
investigated the topic of zero-sum matrix games from the perspectives of duality and
saddle points of functions, respectively. A \emph{bimatrix}\index{matrix game!bimatrix} game is a generalization of
the zero-sum game, one in which each player has his or her own payoff matrix.

\newpar
In this example we assume that Ed's payoff matrix is given by
\begin{equation}\label{E:duality_payoff_matrix}
A=\begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix}
\end{equation}
and Steve's by
\begin{equation}\label{E:duality_payoff_matrix}
B=\begin{bmatrix} 4 & 3 \\ 3 & 4 \end{bmatrix}.
\end{equation}

\noi
As in the zero-sum game, Ed picks a column, say column $j$. Simultaneously, Steve picks a row, call it row $i$. Then Steve receives an amount equal to the entry in row $i$ column $j$ of $B$, and Ed receives an amount equal to the corresponding entry in $A$. For example, if Steve picks row 1 and Ed chooses column 2, then Ed receives \$2 and Steve receives \$3. (Whether each player receives the money from the other or from some third party is inconsequential.)

\newpar
A pure strategy Nash equilbrium\index{matrix game!pure strategy Nash equilibrium} for the bimatrix
game is defined in a manner analogous to that done for the zero-sum case. To determine such equilibria,
we consider the four possible ordered pairs formed by the two column choices for Ed and the two row choices for Steve. For example, the combination consisting of Ed choosing column one and Steve choosing row one is not a pure strategy equilibrium. If Ed recognizes that Steve always chooses row one, then Ed can increase his earnings by choosing column two provided Steve continues to follow his own strategy. Similar reasoning applied to other cases establishes that no pure strategy Nash equilibrium exists.

\newpar
However, as proven by John Nash\index{Nash, J.} in 1951, any bimatrix game is guaranteed to possess at least one mixed strategy equilbrium\index{matrix game!mixed strategy Nash equilibrium} \cite{Nash}. We now determine such equilibria for Ed and Steve's contest.

\newpar
As was the case in Section \ref{S:Duality}, matrix-vector products provide a convenient means for expressing each game move. To Ed's choice
of column 2 we associate the vector $\ds \begin{bmatrix} 0 \\ 1 \end{bmatrix}$ and to Steve's
choice of row 1 we associate $\ds \begin{bmatrix} 1 \\ 0 \end{bmatrix}$. Then Ed and Steve have respective earnings given by
\begin{equation*}
\begin{bmatrix} 1 \\ 0 \end{bmatrix}^t A \begin{bmatrix} 0 \\ 1 \end{bmatrix}=2
\mbox{  and  }
\begin{bmatrix} 1 \\ 0 \end{bmatrix}^t B \begin{bmatrix} 0 \\ 1 \end{bmatrix}=3.
\end{equation*}

\newpar
If Steve's equilibrium mixed strategy\index{matrix game!equilibrium mixed strategy} is represented by the vector $\vecy_0$ in $\R^2$, whose entries sum to 1, then Ed seeks to determine the value $\vecx$, call it $\vecx_0$, whose entries sum to 1 and which maximizes
$\ds \vecy_0^t A \vecx$. Likewise, Steve wants $\vecy_0$ to be the value of $\vecy$ that
maximizes $\ds \vecy^t B \vecx_0$. If $\ds \vecz_0= \begin{bmatrix} z_{0,1} \\ z_{0,2} \end{bmatrix}$ is the vector recording Ed and Steve's corresponding earnings, respectively, then
the equilibrium mixed strategies must satisfy the following conditions:
\begin{align}\label{E:QPBimatrixGameConditions}
z_{0,1}&= \max_{\vecx} \left\{ \vecy_0^t A \vecx \mid  \vece^t \vecx =1 \mbox{ and } \vecx \geq \zerovec \right\}
\intertext{and}
z_{0,2}&= \max_{\vecy} \left\{ \vecy^t B \vecx_0 \mid  \vece^t \vecy =1 \mbox{ and } \vecy \geq \zerovec \right\}.\notag
\end{align}

\noi
Observe that due to the manner in which equilibrium strategies, $\vecx_0$ and $\vecy_0$, are defined, if
one player deviates from his equilibrium strategy while the second player continues to follow his own, then the first sees no improvement in
his earnings.

\newpar
Finding the vector quantities, $\vecx_0$, $\vecy_0$, $\vecz_0$, that satisfy the conditions in (\ref{E:QPBimatrixGameConditions}) can be restated in terms of solving a certain quadratic programming
problem. Namely, the triple, $\ds \begin{bmatrix} \vecz_0 \\ \vecx_0 \\ \vecy_0 \end{bmatrix}$,
constitutes a solution of (\ref{E:QPBimatrixGameConditions}) if and only if it is also a solution
of the following\index{bimatrix game!quadratic programming formulation}:
\begin{align}\label{E:QPBimatrixGameQuadProgram}
 \min_{\vecz,\vecx,\vecy}  f(\vecz,\vecx,\vecy )&= \vece^t \vecz - \vecx^t (A+B) \vecy  \\
	\mbox{ subject to} & \notag\\
	A^t \vecy &\leq z_1 \vece \notag \\
    B \vecx &\leq z_2 \vece \notag \\
    \vece^t \vecx &=1 \notag \\
    \vece^t \vecy &=1 \notag \\
    \vecx, \vecy &\geq \zerovec \notag,
    \end{align}
where $\ds \vecz=\begin{bmatrix} z_1 \\ z_2 \end{bmatrix}$. The proof that the solution of (\ref{E:QPBimatrixGameQuadProgram}) coincides with that of (\ref{E:QPBimatrixGameConditions}) is beyond the scope of this text and can be found in other sources \cite{Mangasarian_game_theory_quad_programming}. We will focus on the connection between
this problem and that of the general quadratic programming model and apply these tools to Ed and Steve's game. We will also leave it as an exercise to show that when $B=-A$, the solutions of
(\ref{E:QPBimatrixGameConditions}) and (\ref{E:QPBimatrixGameQuadProgram}) are not only identical but also coincide with the solution of the zero-sum matrix game.

\newpar
We first express (\ref{E:QPBimatrixGameQuadProgram}) in the standard form from
(\ref{E:QPGeneralForm}). For the sake of compact notation, we let $\vecw$
be the vector in $\R^6$, whose first two entries we associate to $\vecz$, the next two
to $\vecx$, and the last two to $\vecy$. In other words,
$\ds \vecw = \begin{bmatrix} \vecz \\ \vecx \\ \vecy \end{bmatrix}$.

\newpar
Now define $\ds \vecp= \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$
and
\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*}
Straightforward calculations show that the objective function, $f$, from
(\ref{E:QPBimatrixGameQuadProgram}) is none other than the quadratic function $f:\R^6 \to \R$
given by
\begin{equation}\label{E:QPBiMatrixGameObjective}
f(\vecw)= \frac{1}{2} \vecw^t Q \vecw +\vecp^t\vecw.
\end{equation}

\newpar
We now seek to express the constraints from (\ref{E:QPBimatrixGameQuadProgram}) in the form
of a matrix inequality, $C\vecw \leq \vecd$, along with a matrix equation
$E\vecw =\vecb$. (We use $E$ instead of $A$ since $A$ already denotes Ed's payoff
matrix.)

\newpar
Equality constraints from (\ref{E:QPBimatrixGameQuadProgram}) dictate
$\vece^t \vecx=1$ and $\vece^t \vecy =1$, so we set $\vecb = \vece$ and
$\ds E=\begin{bmatrix} 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$.
The matrix $C$ has 8 rows and 6 columns. Four of the rows correspond to the sign restrictions
$-\vecx \leq \zerovec$ and $-\vecy \leq \zerovec$. The remaining four arise from the inequalities,
$\ds A^t \vecy \leq z_1 \vece$ and $\ds B \vecx \leq z_2 \vece$, which can be rewritten
as $\ds -z_1\vece+A^t \vecy \leq \zerovec$ and $\ds -z_2 \vece + B \vecx \leq \zerovec$.
Set $\ds \vecd= \zerovec_{8 \times 1}$, $\ds M_1= \begin{bmatrix} -1 & 0 \\ -1 & 0 \end{bmatrix}$,
and $\ds M_2= \begin{bmatrix} 0 & -1 \\ 0 & -1 \end{bmatrix}$. Then inequality constraints are summarized through the inequality $C\vecx \leq \vecd$,
where
\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*}

\newpar Knowing  $Q$, $E$, $\vecb$, and $\vecd$, we now restate (\ref{E:QPBimatrixGameQuadProgram}) in the standard quadratic program
form\index{bimatrix game!matrix form}:

\begin{align}\label{E:QPBimatrixGameStandardForm}
 \mbox{ minimize }  f(\vecw)&= \frac{1}{2} \vecw^t Q \vecw +\vecp^t\vecw  \\
	\mbox{ subject to} & \notag\\
	E\vecw &= \vecb \notag\\
C\vecw &\leq \vecd. \notag
	\end{align}	


\begin{progress_ck}
Use Maple's \mf{QPSolve} command to verify that the solution of (\ref{E:QPBimatrixGameStandardForm})
is given by $\ds \vecw_0= \begin{bmatrix} 5/3 \\ 7/2 \\ 1/2 \\ 1/2 \\ 2/3 \\ 1/3 \end{bmatrix}$.
Thus Ed's equilibrium strategy consists of $\vecx_0=\begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}$, implying he chooses each column with equal probability. His earnings are given by $\ds z_{0,1} = 5/3$. Steve,
on the other hand, has an equilibrium strategy of $\vecy_0=\begin{bmatrix} 2/3 \\ 1/3 \end{bmatrix}$, meaning he chooses the first row $2/3$ of the time and has earnings of $\ds z_{0,2} = 7/2$. That Steve's earnings
are much larger than Ed's is intuitively obvious if we compare the relative sizes of the entries
in $A$ and $B$.
\end{progress_ck}

\newpar
We can verify these results by applying our newly developed tools for quadratic programming problems. Using tools for calculating KKT points, as
discussed in Section \ref{S:ConvexNLPs}, we can verify $\vecw_0$ is the only KKT point of (\ref{E:QPBimatrixGameStandardForm}). The multiplier
vector, $\lambdavec_0$, corresponding to the eight inequality constraints is given by
$\ds \lambdavec_0= \begin{bmatrix} 1/6 \\ 5/6 \\ 1/6 \\ 5/6 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, and
that the multiplier vector corresponding to the two equality constraints is $\ds \muvec_0= \begin{bmatrix} 11/6 \\ 11/3 \end{bmatrix}$. Only the first four constraints of
to $C \vecw \leq \vecd$ are binding. Thus, to apply the bordered Hessian
\index{bimatrix game!application of bordered Hessian test} test, we form a submatrix of $C$ using its top four rows:

\begin{equation*}
\tilde{C}=\begin{bmatrix} M_1 &  0_{2 \times 2} & A^t \\
M_2 & B &  0_{2 \times 2}
  \end{bmatrix}.
\end{equation*}

\noi
It is easy to check that the rows
forming $\ds \begin{bmatrix} E \\ \tilde{C} \end{bmatrix}$ are linearly independent,
so $\vecx_0$ is regular.

\newpar
The bordered Hessian is the 12-by-12 matrix given by
\begin{equation*}
B_h= \begin{bmatrix} 0_{2\times 2} & 0_{2 \times 4} & E \\
0_{4 \times 2 } & 0_{4 \times 4} & \tilde{C} \\
E^t & \tilde{C}^t & Q
\end{bmatrix}.
\end{equation*}

\noi
In this case $n=6$ (the number of decision variables), $m=2$ (the number of equality constraints),
and $k=4$ (the number of binding inequality constraints). Since $n-(m+k)=0$, we need only to check that
$\det(B_h)$ has the same sign as $(-1)^{m+k}=1$. A quick calculation verifies
that $\det(B_h)=36$ so that the KKT point $\vecw_0$ is a solution of (\ref{E:QPBimatrixGameStandardForm}).

\newpar
We end this section by noting that the mixed strategy Nash
equilibrium solution of a bimatrix game  need not be unique in general. It can be the case that (\ref{E:QPBimatrixGameQuadProgram}) has multiple solutions. While the value of the objective function, $f$, in (\ref{E:QPBimatrixGameQuadProgram}) must be the same for all of these, the players' equilibrium mixed strategies and corresponding payoffs, as determined by entries of $\vecx_0$, $\vecy_0$, and $\vecz_0$, may vary.

\section*{Exercises Section \protect\ref{S:QP}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_QuadraticProgramming}	
\endinput








