Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

What would be a good informal/intuitive proof for 'hitting the point home' about LP duality? How best to show that the minimized objective function is indeed the minimum with an intuitive way of understanding the bound?

The way I was taught Duality only led to one understanding which I am sure is shared by a LOT of people I know: For every corresponding minimization problem there is an equivalent maximization problem that can be derived by inverting the inequality constraints. Period. This "conclusion" of duality is what seems to stick but not "why is this so" (i.e. how/why is there a bound on the optimal solution).

Is there a way of playing with the inequalities just to 'show' the lower/upper bound on the optimum which could be a motivation for the proof?

I've gone through Chvatal's book as well as a few others but found nothing that could be understood by absolute noobs to LP. The closest that I got was from Vazirani's book on algorithms, where he talks about 'multiplying the inequalities with some magic numbers that show the bound' - I'm not sure how to reproduce the effect for an arbitrary LP.

share|improve this question
4  
In this math.SE answer I go through a step-by-step example of where the dual comes from -- and why -- for a problem that has most of the different possibilities that can arise with an LP. Perhaps that may help? –  Mike Spivey Jan 24 '13 at 3:51
2  
Not sure why you think Vazirani's argument doesn't work for a general LP. Personally, I like that explanation the best of all. –  Suresh Venkat Jan 24 '13 at 5:55
1  
Are you asking about the weak duality or the strong duality? –  Tsuyoshi Ito Jan 24 '13 at 7:40
4  
You can get geometric intuition by visualizing (in 2d, say) what it means to take a linear combination of constraints. For example, draw the constraints $x \le 1$ and $y \le 1$ in the plane. Linear combinations of these constraints give you $ax + by \le a + b$ for any $a,b \ge 0$. Draw this out to see it. Generally, linear combination of constraints give you the supporting half-spaces of the polyhedra. Now ask, why is it that one of these supporting half-spaces is always enough, by itself, to give a bound on the cost? If you see it, that's strong duality. –  Neal Young Jan 25 '13 at 4:57
    
@MikeSpivey - I wish your comment was an answer :) –  PhD Jan 25 '13 at 20:49
show 2 more comments

2 Answers 2

up vote 10 down vote accepted

Per OP's wish, here's the math.SE answer I link to in my comment above.


Maybe it's worthwhile to talk through where the dual comes from on an example problem. This will take a while, but hopefully the dual won't seem so mysterious when we're done.

Suppose with have a primal problem as follows.

$$ Primal =\begin{Bmatrix} \max \ \ \ \ 5x_1 - 6x_2 \\ \ \ \ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ \ \ \ \ x_1 \geq 0\\ \end{Bmatrix} $$


Now, suppose we want to use the primal's constraints as a way to find an upper bound on the optimal value of the primal. If we multiply the first constraint by $9$, the second constraint by $1$, and add them together, we get $9(2x_1 - x_2) + 1(x_1 +3 x_2)$ for the left-hand side and $9(1) + 1(9)$ for the right-hand side. Since the first constraint is an equality and the second is an inequality, this implies $$19x_1 - 6x_2 \leq 18.$$ But since $x_1 \geq 0$, it's also true that $5x_1 \leq 19x_1$, and so $$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$$ Therefore, $18$ is an upper-bound on the optimal value of the primal problem.

Surely we can do better than that, though. Instead of just guessing $9$ and $1$ as the multipliers, let's let them be variables. Thus we're looking for multipliers $y_1$ and $y_2$ to force $$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$$

Now, in order for this pair of inequalities to hold, what has to be true about $y_1$ and $y_2$? Let's take the two inequalities one at a time.


The first inequality: $5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

We have to track the coefficients of the $x_1$ and $x_2$ variables separately. First, we need the total $x_1$ coefficient on the right-hand side to be at least $5$. Getting exactly $5$ would be great, but since $x_1 \geq 0$, anything larger than $5$ would also satisfy the inequality for $x_1$. Mathematically speaking, this means that we need $2y_1 + y_2 \geq 5$.

On the other hand, to ensure the inequality for the $x_2$ variable we need the total $x_2$ coefficient on the right-hand side to be exactly $-6$. Since $x_2$ could be positive, we can't go lower than $-6$, and since $x_2$ could be negative, we can't go higher than $-6$ (as the negative value for $x_2$ would flip the direction of the inequality). So for the first inequality to work for the $x_2$ variable, we've got to have $-y_1 + 3y_2 = -6$.


The second inequality: $y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

Here we have to track the $y_1$ and $y_2$ variables separately. The $y_1$ variables come from the first constraint, which is an equality constraint. It doesn't matter if $y_1$ is positive or negative, the equality constraint still holds. Thus $y_1$ is unrestricted in sign. However, the $y_2$ variable comes from the second constraint, which is a less-than-or-equal to constraint. If we were to multiply the second constraint by a negative number that would flip its direction and change it to a greater-than-or-equal constraint. To keep with our goal of upper-bounding the primal objective, we can't let that happen. So the $y_2$ variable can't be negative. Thus we must have $y_2 \geq 0$.

Finally, we want to make the right-hand side of the second inequality as small as possible, as we want the tightest upper-bound possible on the primal objective. So we want to minimize $y_1 + 9y_2$.


Putting all of these restrictions on $y_1$ and $y_2$ together we find that the problem of using the primal's constraints to find the best upper-bound on the optimal primal objective entails solving the following linear program:

$$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$$

And that's the dual.


It's probably worth summarizing the implications of this argument for all possible forms of the primal and dual. The following table is taken from p. 214 of Introduction to Operations Research, 8th edition, by Hillier and Lieberman. They refer to this as the SOB method, where SOB stands for Sensible, Odd, or Bizarre, depending on how likely one would find that particular constraint or variable restriction in a maximization or minimization problem.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint
share|improve this answer
add comment

Elaborating on Mike's answer and Vazirani's comment, you get the dual by considering the general form of an optimality proof for the solution to the original problem. Suppose you have a maximization problem given some linear inequalities, and without loss of generality, suppose you're trying to maximize the variable $x$. Given a solution in which $x = B$, how do we know that it's optimal? One way is to try to get a bound on $x$ by taking linear combinations of the linear inequalities. Some linear combinations give you a bounds of the form $x \leq C$, and you're trying to get the best (minimal) $C$ possible. Weak duality states that $B \leq \min C$, which is obvious by definition. Strong duality states that when $B$ is finite, then $B = \min C$. This means that if the maximum is $B$ then there is a "reason" that you can't get beyond $B$, which doubles as a proof of optimality.

This point of view is actually helpful sometimes. Let $f$ be a set function ($f$ takes a set and outputs a real number), and $S,O$ be two sets. Suppose you're trying to derive an inequality $f(S) \geq (1-1/e) f(O)$ from a bunch of inequalities regarding the function $f$ (that's a real-life example). You write a linear program in which the values of $f$ are the variables, $f(O) = 1$ is a constraint, and the objective is to minimize $f(S)$. The solution to this program is $\min f(S) = 1-1/e$ (let's assume $1-1/e$ is best-possible), and the solution to the dual gives you a proof of $f(S) \geq 1-1/e$.

This leaves open the question of why strong duality actually holds. There are two proofs of this fact for linear programming, one involving the simplex algorithm, the other Farkas's lemma. Farkas's lemma is probably the "correct" way to understand the situation, reducing everything to some intuitive geometric fact. However, I confess that this intuition goes over my head.

In more general situations (let's say semidefinite programming), you need to use the more general Karush-Kuhn-Tucker conditions (a form of Lagrange multipliers) to get the dual and conditions for strong duality. This is treated in texts on non-linear or convex optimization.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.