\section{Duality}\label{S:ExerciseSolutions_Duality}
\setcounter{progress_ck_counter}{0}

\be
%EXERCISE 1
\item At each stage of the simplex algorithm, the decision variables in the primal LP correspond
to a basic feasible solutions. Values of the decision variables in the dual LP are recorded
by the entries of the vector $\vecy$. Only at the final iteration of the algorithm, do the dual variables
satisfy both $\vecy A \geq \vecc$ and $\vecy \geq \zerovec$, i.e., only at the final iteration do
the entries of $\vecy$ constitute a basic feasible solution of the dual.

%EXERCISE 2
\item The given LP can be restated as
    \begin{align*}
		 \mbox{maximize } z &=3x_1+4x_2  \\
		\mbox{ subject to} \notag\\
		x_1 \x &\leq 4 \notag\\
		x_1+3x_2 &\leq 15  \notag\\
		-x_1+2x_2 &\geq 5 \notag \\
		x_1-x_2 &\geq 9 \notag \\
		x_1+x_2&\leq6 \notag \\
        -x_1-x_2 &\leq -6 \\
		x_1,x_2 &\geq 0.\notag
		\end{align*}

 \noi   In matrix inequality form, this becomes
    \begin{align*}
 \mbox{maximize } z &=\vecc \cdot \vecx   \\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec, \notag
	\end{align*}
where $\ds A= \begin{bmatrix} 1 & 0 \\ 1 & 3 \\ 1 & -1 \\ -1 & 1 \\ 1 & 1 \\ -1 & -1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} 3 & 4 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 4 \\ 15 \\ -5 \\ 9 \\ 6 \\ -6\end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\newpar
The corresponding dual is given by
\begin{align*}
   \mbox{minimize } w &=\vecy \cdot \vecb   \\
	\mbox{ subject to} \\
	\vecy A &\geq \vecc  \\
	\vecy &\geq \zerovec,
	\end{align*}
where $\vecy=\begin{bmatrix} y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \end{bmatrix}$. In expanded
form this is identical to
\begin{align*}
   \mbox{minimize } w &=4y_1+15y_2-5y_3+9y_4+6(y_5-y_6)   \\
	\mbox{ subject to} \\
	y_1+y_2+y_3-y_4+(y_5-y_6) \geq 3  \\
    3y_2-y_3+y_4+(y_5-y_6) \\
	y_1,y_2,y_3,y_4,y_5,y_6 &\geq 0.
	\end{align*}

\noi Now define the new decision variable $\widetilde{y}=y_5-y_6$, which
is unrestricted in sign due to the fact $y_5$ and $y_6$ are nonnegative. Since $y_5$ and $y_6$, together,
correspond to the equality constraint in the primal LP, we see that $\widetilde{y}$
is a dual variable unrestricted in sign that corresponds to an equality constraint in the primal.

%EXERCISE 3
\item The standard maximization LP can be written in matrix inequality form as
\begin{align*}
 \mbox{maximize } z &=\vecc^t  \vecx  \\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec,\notag
	\end{align*}

where $\vecx$ belongs to $\R^n$, $\vecc$ is a {\underbar{column}} vector in $\R^n$, $\vecb$ belongs to $\R^m$, and $A$ is an $m$-by-$n$ matrix.

\newpar
The dual LP is then expressed as
\begin{align*}
 \mbox{minimize } w &=\vecy^t  \vecb   \\
	\mbox{ subject to} \notag\\
	\vecy^t A &\geq \vecc^t \notag \\
	\vecy &\geq \zerovec,\notag
	\end{align*}

where we have assumed the dual variable vector, $\vecy$, is a column vector in $\R^m$. But, by
 transpose properties, this is equivalent to
\begin{align*}
 \mbox{maximize } \widetilde{w} &=-\vecb^t \vecy  \label{E:Duality_primal} \\
	\mbox{ subject to} \notag\\
	-A^t \vecy &\leq -\vecc \notag \\
	\vecy &\geq \zerovec.\notag
	\end{align*}

\newpar
The preceding LP is a maximization problem, whose dual is given by

\begin{align*}
 \mbox{minimize } \widetilde{z} &=\vecx^t (-\vecc)  \\
	\mbox{ subject to} \notag\\
	\vecx^t (-A^t) &\geq -\vecb^t \notag \\
	\vecx &\geq \zerovec.\notag
	\end{align*}

Using transpose properties again, we may rewrite this final LP as
\begin{align*}
 \mbox{maximize } z &=\vecc^t  \vecx  \\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec,\notag
	\end{align*}
which is the original LP.

%EXERCISE 4
\item
\be
\item The original LP has four decision variables and three constraints. Thus,
the dual LP has three decision variables and four constraints.
\item The current primal solution is not optimal, as the nonbasic variable, $s_1$,
has a negative coefficient in the top row of the tableau. By the ratio test,
we conclude that $s_1$ will replace $x_1$ as a basic variable and that $s_1=4$
in the updated basic feasible solution. Since the coefficient of $s_1$ in the top row
is $-2$, the objective value in the primal will increase to 28. By weak duality, we can conclude
that the objective value in the solution of the dual LP is no less than 28.
\ee

%EXERCISE 5
\item The dual of the given LP is
\begin{align*}
 \mbox{minimize } w &=y_1-2y_2 \\
	\mbox{ subject to} \\
	y_1-y_2 &\geq 2 \\
    -y_1+y_2 &\geq 1 \\
    y_1, y_2 &\geq 0,
\end{align*}
which is infeasible.

%EXERCISE 6
\item
\be
\item The current tableau can also be expressed in partitioned matrix form as

\begin{equation*}
\begin{bmatrix}
z & \vecx & \vecy & \vecy \vecb \\
1 & [\bs,\bs] & [1,0,0] & \bs \\
\zerovec & MA & M & M\vecb
\end{bmatrix}
\end{equation*}

\noi Comparing this matrix to that given in the problem, we see
that $\ds M=\begin{bmatrix} 1/3 & 0 & 0 \\ -1/2 & 1 ^ 0 \\ -1/3 & 0 & 1 \end{bmatrix}$.
Thus,
\begin{align*}
\vecb &= M^{-1} (M\vecb) \\
&= \begin{bmatrix} 3 & 0 & 0 \\ 3/2 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 6 \\ 3 \\ 10 \end{bmatrix}
&= \begin{bmatrix} 18 \\ 12 \\ 16 \end{bmatrix},
\end{align*}

and

\begin{align*}
A &= M^{-1} (M A) \\
&= \begin{bmatrix} 3 & 0 & 0 \\ 3/2 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}
\begin{bmatrix} -2/3 & 1 \\ 3 & 0 \\ 14/3 & 0  \end{bmatrix}
&= \begin{bmatrix} -2 & 3 \\ 2 & 3/2 \\ 4 & 1  \end{bmatrix}.
\end{align*}

\noi Using $A$ and $b$, we obtain the original LP:

\begin{align*}
 \mbox{maximize } z &=2x_1+3x_2 \\
	\mbox{ subject to} \notag\\
	-2x_1+3x_2 &\leq 18 \notag\\
	2x_1+\frac{3}{2}x_2 &\leq 12  \notag\\
	4x_1+x_2 &\leq 16 \notag \\
	x_1,x_2 &\geq 0.\notag
	\end{align*}

\item The coefficients of $x_1$ and $x_2$ in the top row of the tableau are given by
\begin{align*}
-\vecc+\vecy A &= -[2,3]+[1,0,0]A  \\
&=[-4,0]
\end{align*}

\noi
The unknown objective value is
\begin{align*}
z &=\vecy \vecb \\
&=[1,0,0]\begin{bmatrix} 18 \\ 12 \\ 16 \end{bmatrix} \\
&=18.
\end{align*}

\item The coefficient of $x_1$ in the top row of the tableau is -4, so an additional iteration
of the simplex algorithm is required. Performing the ratio test, we see that $x_1$
replaces $s_2$ as a nonbasic variable. The updated decision variables become
$x_1=1$ and $\ds x_2=\frac{20}{3}$, with a corresponding objective value of $z=22$. The
slack variable coefficients in the top row of the tableau are
$s_1=\frac{1}{3}$, $s_2=\frac{4}{3}$, and $s_3=0$, which indicates that the current
solution is optimal. Therefore the dual solution is given by
$\ds \vecy=\begin{bmatrix} 1/3 \\ 4/3 \\ 0 \end{bmatrix}$ with objective value $w=22$.
\ee

%EXERCISE 7
\item Since the given LP has two decision variables and four constraints, the corresponding
dual has four decision variables, $y_1$, $y_2$, $y_3$, and $y_4$ along with two constraints.
In expanded form, it is given by

\begin{align*}
 \mbox{minimize } z &=4y_1+6y_2+33y_3+24y_4 \\
	\mbox{ subject to} \\
	-y1+2y_3+2y_4 &\geq 1 \\
	y_1+y_2+3y_3+y_4 &\geq 5  \\
	y_1,y_2,y_3,y_4 &\geq 0.
	\end{align*}

\noi To solve the dual LP using the simplex algorithm, we subtract excess variables, $e_1$
and $e_2$, from the first and second constraints, respectively, and add artificial variables, $a_1$ and $a_2$. The Big M method with $M=1000$ yields an initial tableau given by

\begin{table}[h]
\caption{Initial tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
$w$ & $y_1$ & $y_2$ & $y_3$ & $y_4$ & $e_1$ & $a_1$ & $e_2$ & $a_2$ & RHS  \\
\hline
1 & -4 & -6 & -33 & -24 & 0 &-1000 & 0 &-1000 & 0 \\ \hline
0 & -1 & 0 & 2 & 2 & -1 & 1 & 0 & 0 & 1 \\ \hline
0 & 1 & 1 & 3 & 1 & 0 & 0 & -1 & 1 & 5 \\ \hline
\end{tabular}.
\end{table}

\noi The final tableau is

\begin{table}[h]
\caption{Final tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c}
\hline
$w$ & $y_1$ & $y_2$ & $y_3$ & $y_4$ & $e_1$ & $a_1$ & $e_2$ & $a_2$ & RHS \\
\hline
1 & -11/2 & 0 & 0 & -3 & -15/2 & -1985/2 & -6 & -994 & 75/2 \\ \hline
0 & -1/2 & 0 & 1 & 1 & -1/2 & 1/2 & 0 & 0 & 1/2 \\ \hline
0 & 5/2 & 1 & 0 & -2 & 3/2 & -3/2 & -1 & 1 & 7/2 \\
\hline
\end{tabular}.
\end{table}

\noi The excess variable coefficients in the top row of this tableau are the additive inverses of
the decision variable values in the solution of the primal. Hence, the optimal solution
of the primal is given by $\ds x_1=\frac{15}{2}$ and $x_2=6$, with corresponding objective
value $\ds z=\frac{75}{2}$.


%EXERCISE 8
\item By the complementary slackness property, $\vecx_0$ is the optimal solution of the LP
provided we can find $\ds \vecy_0=\begin{bmatrix} y_1 \\ y_2 \\ y_2 \\y_4 \end{bmatrix}$ in $\R^4$ such that

\[ \left[\vecy_0 A -\vecc \right]_i[\vecx_0]_i=0 \quad  1 \leq i \leq 6\]
and
	\[ [\vecy_0]_j \left[\vecb-A \vecx_0\right]_j=0 \quad 1 \leq j \leq 4.\]


\noi We have
\begin{equation*}
\vecb - A\vecx_0 = \begin{bmatrix} 0 \\ 0 \\ 61/7 \\ 0 \end{bmatrix},
\end{equation*}
so that in a dual solution it must be the case that $y_3=0$. Furthermore,
when $y_3=0$,
\begin{equation*}
\vecy_0 A-\vecc= \begin{bmatrix}
y_1+7y_2+7y_4-5 \\
2y_1-5y_2+8y_4 -1 \\
4y_1+2y_2-3y_4-1 \\
3y_1+y_2+5y_4-4 \\
4y_1+2y_2+2y_4-1 \\
6y_1+3y_2+4y_4-2
\end{bmatrix}.
\end{equation*}

\noi By complementary slackness again, the first, third and fourth components of this vector
must equal zero, whence we have a system of 3 linear equations, whose solution is
given by $y_1=\frac{103}{204}$, $y_2=\frac{37}{204}$, and $y_3=\frac{47}{102}$.
If we define $\ds \vecy_0 = \begin{bmatrix} 103/204 \\ 37/204 \\ 0 \\ 47/102 \end{bmatrix}$,
then
\begin{align*} w &=\vecy_0 \vecb \\
&= \frac{53}{17} \\
&= \vecc \vecx_0
\end{align*}
so that $\vecx_0$ is the optimal solution of the LP by Strong Duality.



%EXERCISE 9
\item Player 1's optimal mixed strategy is given by the solution of the LP

\begin{align*}
 \mbox{maximize } z &\mbox{ subject to} \\
	A \vecx &\geq z\vece \notag \\
	\vece^t\cdot\vecx&=1 \notag  \\
	\vecx &\geq \zerovec, \notag
	\end{align*}

and Player 2's by the solution of the corresponding dual LP,

\begin{align*}
 \mbox{minimize } w &\mbox{ subject to} \\
	\vecy A&\leq w\vece^t \notag \\
	\vecy \cdot \vece&=1 \notag  \\
	\vecy &\geq \zerovec. \notag
\end{align*}

\noi Here $\ds \vece=\begin{bmatrix} 1 \\ 1 \end{bmatrix}$. The solution of the first
LP is given by $\ds \vecx_0 = \begin{bmatrix} .7  \\ .3 \end{bmatrix}$ and
the solution of the second by $\ds \vecx_0 = \begin{bmatrix} .5  \\ .5 \end{bmatrix}$.
The corresponding objective value for each LP is $z=w=.5$, thereby indicating
that the game is biased in Player 1's favor.


%EXERCISE 10
\item
\be
\item Since $A$ is an $m$-by-$n$ matrix, $\vecb$ belongs to $\R^m$, and $\vecc$ is a row
vector in $\R^n$, the matrix $M$ has $m+n-1$ rows and $m+n-1$ columns. Furthermore, the
transpose of a partitioned matrix, $\ds \begin{bmatrix} A & B \\ C & D \end{bmatrix}$,
is given by $\ds \begin{bmatrix} A^t & C^t \\ B^t & D^t \end{bmatrix}$, which can be used
to show $M^t=-M$.
\item Define $\ds vecw_0 = \begin{bmatrix} \vecy_0^t \\ \vecx_0 \\ 1 \end{bmatrix}$. Then
$\vecw_0$ belongs to $\R^{m+n+1}$ and has nonnegative components since $\vecx_0$ and $\vecy_0$ are
primal feasible and dual feasible vectors belonging to $\R^n$ and $\R^m$, respectively. Furthermore, $[\vecw_0]_{m+n+1}=1 >0$. We have
\begin{align*}
M\vecw_0 &= \begin{bmatrix} 0_{m \times m} & -A & \vecb \\
   A^t & 0_{m \times n} & -\vecc^t \\
   -\vecb^t & \vecc & 0
   \end{bmatrix} \begin{bmatrix} \vecy_0^t \\ \vecx_0 \\ 1 \end{bmatrix} \\
   &= \begin{bmatrix} -A \vecx_0 + \vecb \\
   A^t \vecy_0^t - \vecc_t \\
   -\vecb^t\vecy_0^t + \vecc \vecx_0
   \end{bmatrix} \\
   &\geq \zerovec
\end{align*}
since the primal feasibility of $\vecx_0$ dictates $A \vecx_0 \leq \vecb$,
the dual feasibility of $\vecy_0$ and transpose properties
imply $A^t \vecy_0^t \geq \vecc_t$, and strong duality forces
$\vecb^t\vecy_0^t = \vecc \vecx_0$.

\item Letting $\kappa$, $\vecx_0$, and $\vecy_0$ be defined as in the hint, we have
\begin{align*}
\zerovec &\leq M \vecw_0 \\
&= \begin{bmatrix} 0_{m \times m} & -A & \vecb \\
   A^t & 0_{m \times n} & -\vecc^t \\
   -\vecb^t & \vecc & 0
   \end{bmatrix} \begin{bmatrix} \kappa \vecy_0^t \\ \kappa \vecx_0 \\ \kappa \end{bmatrix} \\
&= \kappa \begin{bmatrix} 0_{m \times m} & -A & \vecb \\
   A^t & 0_{m \times n} & -\vecc^t \\
   -\vecb^t & \vecc & 0
   \end{bmatrix} \begin{bmatrix} \vecy_0^t \\ \vecx_0 \\ \end{bmatrix} \\
&= \kappa \begin{bmatrix} -A \vecx_0 + \vecb \\
   A^t \vecy_0^t - \vecc_t \\
   -\vecb^t\vecy_0^t + \vecc \vecx_0
   \end{bmatrix}
\end{align*}

\noi Since $\kappa > 0$, we conclude that
$ A \vecx_0 \leq \vecb$, $A^t \vecy_0^t \geq \vecc^t$, and $\vecc \vecx_0 \geq \vecb^t \vecy_0^t$.
Transpose properties permit us to rewrite the second of these matrix inequalities
as $\vecy_0 A \geq \vecc$. Thus $\vecx_0$
and $\vecy_0$ are primal feasible and dual feasible, respectively. Moreover,
the third inequality is identical to $\vecc \vecx_0 \geq \vecy_0 \vecb$
if we combine the facts $\vecb^t \vecy_0^t = \vecy_0 \vecb$, each of
these two quantities is a scalar, and the transpose of a scalar is itself.
But the Weak Duality Theorem also dictates $\vecc \vecx_0 \leq \vecy_0 \vecb$, which
implies $\vecc \vecx_0 = \vecy_0 \vecb$. From this result, we conclude
$\vecx_0$
and $\vecy_0$ constitute the optimal solutions of the (4.1) and (4.3), respectively.
\ee

\ee

\newpar
\textbf{Solutions to Waypoints}

\begin{waypoint}
In matrix inequality form, the given LP can be written as
\begin{align*}
 \mbox{maximize } z &=\vecc \cdot \vecx  \\
	\mbox{ subject to} \\
	A \vecx &\leq \vecb \\
	\vecx &\geq \zerovec,
	\end{align*}
where $\ds vecx=\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}$, $\vecc=[3,5,2]$,
$\ds A=\begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 3 & 1 & 5 \\ -1 & 1 & 1 \end{bmatrix}$,
and $\ds \vecb=\begin{bmatrix}= 2 \\ 2 \\ 4 \\ 3 \end{bmatrix}$. The dual LP is given
by

\begin{align*}
 \mbox{minimize } w &=\vecy \cdot \vecb   \\
	\mbox{ subject to} \\
	\vecy A &\geq \vecc \\
	\vecy &\geq \zerovec,
	\end{align*}
where $\vecy=\begin{bmatrix} y_1 & y_2 & y_3 & y_4 \end{bmatrix}$. In expanded form,
this is equivalent to

\begin{align*}
		 \mbox{minimize } w &=2y_1+2y_2+4y_3+3y_4 \\
		\mbox{ subject to} \notag\\
		2y_1+ y_2+3y_3-y_4 \geq 3\notag\\
		y_1+ 2y_2+y_3+y_4 &\geq 5 \notag\\
		y_1+ y_2+5y_3+y_4 &\geq 2 \notag\\
		y_1,y_2,y_3,y_4 &\geq 0.\notag
		\end{align*}

The original LP has its solution given by $\ds \vecx_0=\begin{bmatrix} 2/3 \\ 2/3 \\ 0 \end{bmatrix}$ with $\ds z_0=\frac{16}{3}$. The solution of the dual LP is
$\vecy_0=\begin{bmatrix} 1/3 & 7/3 & 0 & 0 \end{bmatrix}$ with $\ds w_0=\frac{16}{3}$.
\end{waypoint}

\begin{waypoint}
\be
\item If Steve always chooses row one and Ed chooses columns one, two, and three with respective probabilities, $x_1$, $x_2$, and $x_3$, then Ed's expected winnings are given by
\begin{align*}
f_1(x_1,x_2,x_3)&=\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}\cdot A \cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \\
&= x_1-x_2+2x_3,
\end{align*}
which coincides with the first entry of the matrix-vector product, $A\vecx$. By similar
reasoning,
\begin{align*}
f_2(x_1,x_2,x_3)&=\begin{bmatrix} 0 & 1 & 0 \end{bmatrix}\cdot A \cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \\
&= 2x_1+4x_2-x_3 \\
\intertext{and}
f_3(x_1,x_2,x_3)&=\begin{bmatrix} 0 & 0 & 1 \end{bmatrix}\cdot A \cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \\
&= -2x_1+2x_3,
\end{align*}
which equal the second and third entries of $A\vecx$, respectively.

\item If Ed always chooses column one and Steve chooses rows one, two, and three with respective probabilities, $y_1$, $y_2$, and $y_3$, then Steve's expected winnings are given by
\begin{align*}
g_1(y_1,y_2,y_3)&=\begin{bmatrix} y_1 & y_2 & y_3 \end{bmatrix} \cdot A \cdot 
\begin{bmatrix} 1 \\  0 \\ 0 \end{bmatrix}
&= y_1+2y_2-2y_3,
\end{align*}
which coincides with the first entry of the product, $\vecy A$.
By similar
reasoning,
\begin{align*}
g_2(y_1,y_2,y_3)&=\begin{bmatrix} y_1 & y_2 & y_3 \end{bmatrix}\cdot A \cdot 
\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \\
&= -y_1+4y_2\\
\intertext{and}
g_3(y_1,y_2,y_3)&=\begin{bmatrix} y_1 & y_2 & y_3 \end{bmatrix}\cdot A \cdot 
\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \\
&= 2y_1-y_2+2y_3,
\end{align*}
which equal the second and third entries of $\vecy A$, respectively.
\ee
\end{waypoint}

\begin{waypoint}
To assist in the formulation of the dual, we view the primal objective, $z$, as the difference
of two nonnegative decision variables, $z_1$ and $z_2$. Thus the primal LP can be expressed
in matrix inequality form as
\begin{align*}
		 \mbox{maximize } \begin{bmatrix} 1 & -1 & \zerovec_{1 \times 3} \end{bmatrix}
\cdot & \begin{bmatrix} z_1 \\ z_2 \\ \vecx \end{bmatrix} \\
		\mbox{ subject to}& \\
	\begin{bmatrix}	\vece & -\vece & -A \\
0 & 0 & \vece^t \\
0 & 0 & -\vece^t \end{bmatrix} \cdot \begin{bmatrix} z_1 \\ z_2 \\ \vecx \end{bmatrix}
&\leq \begin{bmatrix} \zerovec_{3 \times 1} \\ 1 \\ -1 \end{bmatrix} \\
\vecx \geq \zerovec \mbox{ and } z_1,z_2 &\geq 0.
\end{align*}

\newpar
If the dual LP has its vector of decision variables denoted
by $\ds \begin{bmatrix} \vecy & w_1 & w_2 \end{bmatrix}$,
where $\vecy$ is a row vector in $\R^3$ with nonnegative components, and
both $w_1$ and $w_2$ are nonnegative as well, then the dual is given by

\begin{align*}
		 \mbox{minimize } \begin{bmatrix} \vecy & w_1 & w_2 \end{bmatrix}
\cdot & \begin{bmatrix} \zerovec_{3 \times 1} \\ 1 \\ -1 \end{bmatrix} \\
		\mbox{ subject to}& \\
	\begin{bmatrix}	\vecy & w_1 & w_2 \end{bmatrix} 
\cdot \begin{bmatrix} \vece & -\vece & -A \\
0 & 0 & \vece^t \\
0 & 0 * -\vece^t \end{bmatrix}
&\geq \begin{bmatrix} 1 & -1 & \zerovec_{1 \times 3} \end{bmatrix} \\
\vecy \geq \zerovec_{1 \times 3} \mbox{ and } w_1,w_2 &\geq 0.
\end{align*}

\noi If we write $w=w_1-w_2$, then this formulation to the dual simplifies to
be
\begin{align*}
 \mbox{minimize } w &\mbox{ subject to} \\
	\vecy A&\leq w\vece^t  \\
	\vecy \cdot \vece&=1  \\
	\vecy &\geq \zerovec.
\end{align*}


\end{waypoint}

\endinput 