What is the dual for the following LP

67 Views Asked by At

Minimize $c^Tx$

subject to, $b_l \leq Ax \leq b_u \\ l\leq x \leq u$

where $A$ is an $m \times n$ matrix.

My approach was to separate each inequality into two. So,

$b_l \leq Ax\\ Ax\leq b_u\\ l\leq x\\ x\leq u$

And the dual objective would then be, Maximize $b_l^Ty+b_u^Ty+l^Ty+u^Ty$. I was not able to figure out the constraints

1

There are 1 best solutions below

0
On BEST ANSWER

Let $I$ be the identity matrix. Define $$ B=\begin{bmatrix}A\\-A\\I\\-I\end{bmatrix},\qquad d=\begin{bmatrix}b_l\\-b_u\\l\\-u\end{bmatrix} $$ then all the constraints can be written as $Bx\ge d$.

Calculate the dual problem to $$ \min c^Tx\quad\text{subject to }Bx\ge d. $$ There are different ways to do it in optimization courses that covers LP, but let's do it via Lagrange duality. The Lagrange function is $$ L(x,y)=c^Tx+y^T(d-Bx)=d^Ty+(c-B^Ty)^Tx,\quad y\ge 0. $$ The dual problem is $$ \max_{y\ge 0}\min_x L(x,y). $$ The inner minimum is easily calculated as $$ \min_x L(x,y)= \begin{cases} d^Ty & \text{ if }c-B^Ty=0,\\ -\infty & \text{ otherwise}. \end{cases} $$ Now for maximization the part with $-\infty$ is not relevant, so we have the dual problem $$ \max d^Ty\quad\text{subject to }B^Ty=c,\ y\ge 0. $$