Duals of Linear Programs

Question

We are trying to find the dual of the following linear program.

$$ \max_x \ ax_1 \ + x_2 $$

such that:

$$ v_1x_1 - v_2x_2 \geq b_1 \\ v_1x_1 - v_2x_2 \geq b_2 \\ x_1 \geq 0 \\ x_2 \geq 0$$

How would one do this?

I am not sure but I get the following as the dual :

$$ \min_\gamma \ b_1\gamma_1 + b_2\gamma_2 $$

such that:
$$ v_1\gamma_1 - v_2\gamma_2 \geq a $$

$$ v_1\gamma_1 - v_2\gamma_2 \geq 1 \\ \gamma_1 \geq 0 \\ \gamma_2 \geq 0$$

Is this correct?

What can one say about the primal and dual feasibility and the optimal values of this problem?

Answer 1

I employ the method described by Sebastien Lahaie at

http://www.cs.columbia.edu/coms6998-3/lpprimer.pdf

Question: find the dual of the following linear program:

$$ \max_x \ ax_1 \ + x_2 $$

such that:

$$ v_1x_1 - v_2x_2 \geq b_1 \\ v_1x_1 - v_2x_2 \geq b_2 \\ x_1 \geq 0 \\ x_2 \geq 0$$

Solution:

Steps 1 and 2.

$$ \min_x -ax_1 - x_2$$

such that

$$ v_2x_2 - v_1x_1 +b_1 \le 0 \\ v_2x_2 - v_1x_1 + b_2 \le 0 \\ x_1 \geq 0 \\ x_2 \geq 0$$

Step 3

$$ \max_ \gamma \min_x -ax_1 - x_2$$

$$+ \gamma_1(v_2x_2 - v_1x_1 +b_1) \\ + \gamma_2(v_2x_2 - v_1x_1 + b_2)$$

$$x_1 \geq 0 \\ x_2 \geq 0 \\ \gamma_1 \geq 0 \\ \gamma_2 \geq 0$$

Step 4

$$ \max_ \gamma \min_x \gamma_1 b_1 + \gamma_2 b_2$$

$$ + x_1(-v_1 \gamma_1 -v_1 \gamma_2 -a)$$

$$ + x_2(v_2 \gamma_1 +v_2 \gamma_2 -1)$$

$$x_1 \geq 0 \\ x_2 \geq 0 \\ \gamma_1 \geq 0 \\ \gamma_2 \geq 0$$

Steps 5 and 6

$$ \max_ \gamma \gamma_1 b_1 + \gamma_2 b_2$$

$$-v_1 \gamma_1 -v_1 \gamma_2 -a \ge 0$$

$$v_2 \gamma_1 +v_2 \gamma_2 -1 \ge 0$$

$$ \gamma_1 \geq 0 \\ \gamma_2 \geq 0$$

Step 7

$$ \min_ \gamma - \gamma_1 b_1 - \gamma_2 b_2$$

$$-v_1 \gamma_1 -v_1 \gamma_2 \ge a$$

$$v_2 \gamma_1 +v_2 \gamma_2 \ge 1$$

$$ \gamma_1 \geq 0 \\ \gamma_2 \geq 0$$

Answer 2

Here is an informal perspective on the dual that may help with intuition. I use this to quickly derive the transcription when away from my books/notes:

To simplify notation, I am using $\alpha = (a,1)^T$, $V = \begin{bmatrix} v_1 & -v_2 \\ v_1 & -v_2 \end{bmatrix}$, $b= (b_1,b_2)^T$.

The primal problem is $\sup_{x \ge 0} \{ \alpha^Tx | V x \ge b \}$.

To incorporate the constraint into the cost, we penalize any violations as follows $\sup_{x \ge 0} \inf_{\gamma \ge 0} \alpha^Tx +\gamma^T(Vx-b) $.

Now we magically switch the $\inf$ and $\sup$ (justified by von Neumann minimax, or similar) to get $\inf_{\gamma \ge 0} \sup_{x \ge 0} \alpha^Tx +\gamma^T(Vx-b) = \inf_{\gamma \ge 0} \sup_{x \ge 0} (\alpha+V^T \gamma)^T x - b^T\gamma$.

If any component of $\alpha+V^T \gamma$ is positve, the cost will be infinite, so we write this as $\inf_{\gamma \ge 0} \{ -b^T \gamma | V^T \gamma \le -\alpha \}$.

So, your problem should be $\min \{ -(b_1 \gamma_1+b_2 \gamma_2) | \gamma_1 \ge 0, \gamma_2 \ge 0, v_1\gamma_1+v_1 \gamma_2 \le -a, -v_2\gamma_1+-v_2 \gamma_2 \le -1 \}$.

To avoid confusion, I would write the primal in a standard form and then just compute the dual in a rote fashion. This avoids many errors.