1
$\begingroup$

$$\min x +y + z$$

so that

$$ x + y =2$$

and

$$y + z = 3$$

where, $x,y,z >0$. How to create the dual?

[Something like this?]

$$ \max 2s + 3t$$

so that

$$ ...+... =1$$

and

$$ ...+...=1$$

2 Answers 2

2

The underlying idea of duality is very simple: there are no non-trivial linear consequences of linear inequalities and identities. The trivial consequence is just a linear combination of the given conditions with some coefficients, which are the unknowns for the dual problem.

So, you have 5 conditions: $x\ge0$, $y\ge 0$, $z\ge 0$, $x+y=2$ and $y+z=3$. You want to use them to estimate $x+y+z$ from below. You can add them up with coefficients $a,b,c,d,e$ to get $ax+by+cz+d(x+y)+e(y+z)\ge 2d+3e$ where $a,b,c$ must be $\ge 0$ not to revert the signs of the inequalities but $d,e$ can be arbitrary because the identities survive multiplication by any constants. Now, if you want to draw the conclusion about $x+y+z$ from here, you should have exactly it on the left, so we must have $a+d=1$, $b+d+e=1$, $c+e=1$. This, together with the already mentioned $a,b,c\ge 0$ gives you $6$ restrictions. Now, you want to get as large lower bound as possible and you get $2d+3e$, so the objective is $2d+3e\to\max$. That's all there is to it.

  • 1
    +1: This not only gives you the dual, but it also explains where the dual comes from. (Side comment: There's more than one way to form the dual. In fedja's formulation here, the $a,b,c$ variables are what would be the slack variables in the other standard formulation.)2012-01-12
  • 0
    Can you clarify `"not to revert the signs of the inequalities but d,e can be arbitrary because the identities survive multiplication by any constants."`? I dropped here.2012-04-13
  • 0
    @MikeSpivey: could you previem my follow-up clarification q?2012-04-13
0

Primal $$\min c'\bar{x}$$ $$A\bar{x} \leq \bar{b}$$ $$\bar{x}\geq0$$

Dual

$$\max \bar{b}' \bar{y}$$ $$A^{T} \bar{y} \leq \bar{c}$$ $$\bar{y}\geq0$$

Now work out the things.

  • 0
    ...is there something wrong with this?2012-02-26