I review LP duality by reading Lecture 7:
The LP Duality Theorem.
I get the idea how to find the dual LP from primal LP, but my basic knowledge is not enough for finding dual LP for the LP in chapter "Duality and the Minimax
Theorem" from the same scribe.
Given:
max $v$
s.t. $v-(x^TA)_j\leq0$, for $j=1,..,m_2$
$x_1+…+x_{m_1}=1$
$x_i\geq 0$, for $j=1,…,m_1$
Problem: Show that the dual LP of a given LP is
min $u$
s.t. $u-(Ay)_i\geq 0$, for $i=1,…,m_1$
$y_1+…+y_{m_2}=1$
$y_j\geq 0$, for $j=1,…,m_2$
Ideas for solution:
Primal LP has equality $x_1+…+x_{m_1}=1$ then dual should have unrestricted variable but it doesn't, therefore inequity should be rewritten as
$x_1+…+x_{m_1}\leq 1$ and $-x_1-…-x_{m_1}\leq -1$.
Let rewrite inequality as $-(x^TA)_j\leq -v$, which is a standard form.
However, it doesn't help, I still don't know how to get the final result. In addition how at the end we get equality with $y_i$.
In short, it's not trivial case, I would appreciate any help.
Best Answer
I assume that $A \in \mathbb{M}_{m_1,m_2}(\mathbb{R})$
The variables of the problem are : $X= (x_1,...x_{m_1},v)$ ($v$ is a variable not a constant which is what you needed in your answer) $$ \begin{aligned} &\max v = C^TX\\ &\text{s.t. } v-(A^Tx)_j = (DX)_j&\leq0&\text{, for }j=1,..,m_2\\ &(DX)_{m_2+1}=x_1+...+x_{m_1}&=1&\text{, for }j=m_2+1\\ &x_i&\geq 0&\text{, for }j=1,...,m_1\\ \end{aligned} $$ In the standard form, the problem is as follow : $$ \begin{aligned} &\max C^TX\\ &\text{subject to }\\ &(DX)_j&\leq0&\text{, for }j=1,..,m_2\\ &(DX)_{m_2+1}&=1&\text{, for }j=m_2+1\\ &x_i&\geq 0&\text{, for }j=1,...,m_1\\ \end{aligned} $$ Where : $X = (x_1,...,x_{m_1},v)$ is the variable of the problem
$$D = \begin{pmatrix} -a_{1,1} & .. & -a_{1,m_1}&1\\ : & & &:\\ -a_{m_2,1} & .. &-a_{m_2,m_1} &1\\ 1&..&1&0 \end{pmatrix} = \begin{pmatrix} -A^T&1\\ 1&0 \end{pmatrix} $$ $B = (b_1,...,b_{m_2},b_{m_2+1})=(0,..,0,1)$ same as $ b_1 = 0$, $b_2 = 0$,...,$b_{m_2}=0$, $b_{m_2+1}=1$ as required in the standard form
$C = (c_1,...,c_{m_1},c_{m_1+1})=(0,..,0,1)$ which means that ($c_1 = 0$, $c_2 = 0$,..., $c_{m_1} = 0$, $c_{m_1+1}=1$)
You can then use the general recipe for LP duals (page 7 in your lecture) :
The dual variable has the same length as $B$. I will call it : $Y = (y_1,...,y_{m_2},u)$ $$ \begin{aligned} &\max B^TY = u\\ &\text{s.t. }(D^TY)_i = u-(Ay)_i&\geq0&\text{, for }i=1,..,m_1\\ &(D^TY)_{m_1+1}=y_1+...+y_{m_2}&=1\\ &y_i&\geq 0&\text{, for }i=1,...,m_2\\ \end{aligned} $$ because :
$$ D^T = \begin{pmatrix} -A&1\\ 1&0 \end{pmatrix} $$