# CS261 Lecture 6: Duality in Linear Programming

In which we introduce the theory of duality in linear programming.

1. The Dual of Linear Program

Suppose that we have the following linear program in maximization standard form:

$\displaystyle \begin{array}{ll} {\rm maximize} & x_1 + 2x_2 + x_3 + x_4\\ {\rm subject\ to}\\ & x_1 +2 x_2 + x_3 \leq 2\\ & x_2 + x_4\leq 1\\ & x_1 + 2x_3\leq 1\\ & x_1 \geq 0\\ & x_2 \geq 0\\ &x_3 \geq 0 \end{array} \ \ \ \ \ (1)$

and that an LP-solver has found for us the solution ${x_1:=1}$, ${x_2:=\frac 12}$, ${x_3:=0}$, ${x_4:= \frac 12}$ of cost ${2.5}$. How can we convince ourselves, or another user, that the solution is indeed optimal, without having to trace the steps of the computation of the algorithm?

Observe that if we have two valid inequalities

$\displaystyle a\leq b \ {\rm and } \ c \leq d$

then we can deduce that the inequality

$\displaystyle a+c \leq b+d$

(derived by “summing the left hand sides and the right hand sides” of our original inequalities) is also true. In fact, we can also scale the inequalities by a positive multiplicative factor before adding them up, so for every non-negative values ${y_1,y_2 \geq 0}$ we also have

$\displaystyle y_1 a + y_2 c \leq y_1 b + y_2 d$

Going back to our linear program (1), we see that if we scale the first inequality by ${\frac 12}$, add the second inequality, and then add the third inequality scaled by ${\frac 12}$, we get that, for every ${(x_1,x_2,x_3,x_4)}$ that is feasible for (1),

$\displaystyle x_1 + 2x_2 + 1.5 x_3 + x_4 \leq 2.5$

And so, for every feasible ${(x_1,x_2,x_3,x_4)}$, its cost is

$\displaystyle x_1 + 2x_2 + x_3 + x_4 \leq x_1 + 2x_2 + 1.5 x_3 + x_4 \leq 2.5$

meaning that a solution of cost ${2.5}$ is indeed optimal.

In general, how do we find a good choice of scaling factors for the inequalities, and what kind of upper bounds can we prove to the optimum?

Suppose that we have a maximization linear program in standard form.

$\displaystyle \begin{array}{ll} {\rm maximize} & c_1 x_1 + \ldots c_n x_n \\ {\rm subject\ to}\\ & a_{1,1} x_1 + \ldots + a_{1,n} x_n \leq b_1\\ & \vdots\\ & a_{m,1} x_1 + \ldots + a_{m,n} x_n \leq b_m\\ & x_1 \geq 0\\ & \vdots\\ & x_n \geq 0 \end{array} \ \ \ \ \ (2)$

For every choice of non-negative scaling factors ${y_1,\ldots,y_m}$, we can derive the inequality

$\displaystyle y_1 \cdot ( a_{1,1} x_1 + \ldots + a_{1,n} x_n )$

$\displaystyle + \cdots$

$\displaystyle + y_n \cdot ( a_{m,1} x_1 + \ldots + a_{m,n} x_n )$

$\displaystyle \leq y_1 b_1 + \cdots y_m b_m$

which is true for every feasible solution ${(x_1,\ldots,x_n)}$ to the linear program (2). We can rewrite the inequality as

$\displaystyle ( a_{1,1} y_1 + \cdots a_{m,1} y_m )\cdot x_1$

$\displaystyle + \cdots$

$\displaystyle + (a_{1,n}y_1 \cdots a_{m,n} y_m ) \cdot x_n$

$\displaystyle \leq y_1 b_1 + \cdots y_m b_m$

So we get that a certain linear function of the ${x_i}$ is always at most a certain value, for every feasible ${(x_1,\ldots,x_n)}$. The trick is now to choose the ${y_i}$ so that the linear function of the ${x_i}$ for which we get an upper bound is, in turn, an upper bound to the cost function of ${(x_1,\ldots,x_n)}$. We can achieve this if we choose the ${y_i}$ such that

$\displaystyle \begin{array}{l} c_1 \leq a_{1,1} y_1 + \cdots a_{m,1} y_m\\ \vdots\\ c_n \leq a_{1,n}y_1 \cdots a_{m,n} y_m \end{array} \ \ \ \ \ (3)$

Now we see that for every non-negative ${(y_1,\ldots,y_m)}$ that satisfies (3), and for every ${(x_1,\ldots,x_n)}$ that is feasible for (2),

$\displaystyle c_1 x_1 + \ldots c_n x_n$

$\displaystyle \leq ( a_{1,1} y_1 + \cdots a_{m,1} y_m )\cdot x_1$

$\displaystyle + \cdots$

$\displaystyle + (a_{1,n}y_1 \cdots a_{m,n} y_m ) \cdot x_n$

$\displaystyle \leq y_1 b_1 + \cdots y_m b_m$

Clearly, we want to find the non-negative values ${y_1,\ldots,y_m}$ such that the above upper bound is as strong as possible, that is we want to

$\displaystyle \begin{array}{ll} {\rm minimize} & b_1 y_1 + \cdots b_m y_m \\ {\rm subject\ to}\\ & a_{1,1} y_1 + \ldots + a_{m,1} y_m \geq c_1\\ & \vdots\\ & a_{n,1} y_1 + \ldots + a_{m,n} y_m \geq c_n\\ & y_1 \geq 0\\ & \vdots\\ & y_m \geq 0 \end{array} \ \ \ \ \ (4)$

So we find out that if we want to find the scaling factors that give us the best possible upper bound to the optimum of a linear program in standard maximization form, we end up with a new linear program, in standard minimization form.

Definition 1 If

$\displaystyle \begin{array}{ll} {\rm maximize} & \mbox{} {\bf c}^T {\bf x}\\ {\rm subject\ to}\\ & A{\bf x} \leq {\bf b} \\ & \mbox{} {\bf x} \geq {\bf {0}} \end{array} \ \ \ \ \ (5)$

is a linear program in maximization standard form, then its dual is the minimization linear program

$\displaystyle \begin{array}{ll} {\rm minimize} & \mbox{} {\bf b}^T {\bf y}\\ {\rm subject\ to}\\ & A^T{\bf y} \geq {\bf c} \\ & \mbox{} {\bf y} \geq {\bf {0}} \end{array} \ \ \ \ \ (6)$

So if we have a linear program in maximization linear form, which we are going to call the primal linear program, its dual is formed by having one variable for each constraint of the primal (not counting the non-negativity constraints of the primal variables), and having one constraint for each variable of the primal (plus the non-negative constraints of the dual variables); we change maximization to minimization, we switch the roles of the coefficients of the objective function and of the right-hand sides of the inequalities, and we take the transpose of the matrix of coefficients of the left-hand side of the inequalities.

The optimum of the dual is now an upper bound to the optimum of the primal.

How do we do the same thing but starting from a minimization linear program?

We can rewrite

$\displaystyle \begin{array}{ll} {\rm minimize} & \mbox{} {\bf c}^T {\bf y}\\ {\rm subject\ to}\\ & A{\bf y} \geq {\bf b} \\ & \mbox{} {\bf y} \geq {\bf {0}} \end{array}$

in an equivalent way as

$\displaystyle \begin{array}{ll} {\rm maximize} & \mbox{} - {\bf c}^T {\bf y}\\ {\rm subject\ to}\\ & - A{\bf y} \leq - {\bf b} \\ & \mbox{} {\bf y} \geq {\bf {0}} \end{array}$

If we compute the dual of the above program we get

$\displaystyle \begin{array}{ll} {\rm minimize} & \mbox{} - {\bf b}^T {\bf z}\\ {\rm subject\ to}\\ & - A^T{\bf z} \geq - {\bf c} \\ & \mbox{} {\bf z} \geq {\bf {0}} \end{array}$

that is,

$\displaystyle \begin{array}{ll} {\rm maximize} & \mbox{} {\bf b}^T {\bf z}\\ {\rm subject\ to}\\ & A^T{\bf z} \leq {\bf c} \\ & \mbox{} {\bf y} \geq {\bf {0}} \end{array}$

So we can form the dual of a linear program in minimization normal form in the same way in which we formed the dual in the maximization case:

• switch the type of optimization,
• introduce as many dual variables as the number of primal constraints (not counting the non-negativity constraints),
• define as many dual constraints (not counting the non-negativity constraints) as the number of primal variables.
• take the transpose of the matrix of coefficients of the left-hand side of the inequality,
• switch the roles of the vector of coefficients in the objective function and the vector of right-hand sides in the inequalities.

Note that:

Fact 2 The dual of the dual of a linear program is the linear program itself.

We have already proved the following:

Fact 3 If the primal (in maximization standard form) and the dual (in minimization standard form) are both feasible, then

$\displaystyle opt({\rm primal}) \leq opt({\rm dual})$

Which we can generalize a little

Theorem 4 (Weak Duality Theorem) If ${LP_1}$ is a linear program in maximization standard form, ${LP_2}$ is a linear program in minimization standard form, and ${LP_1}$ and ${LP_2}$ are duals of each other then:

• If ${LP_1}$ is unbounded, then ${LP_2}$ is infeasible;
• If ${LP_2}$ is unbounded, then ${LP_1}$ is infeasible;
• If ${LP_1}$ and ${LP_2}$ are both feasible and bounded, then

$\displaystyle opt(LP_1) \leq opt(LP_2)$

Proof: We have proved the third statement already. Now observe that the third statement is also saying that if ${LP_1}$ and ${LP_2}$ are both feasible, then they have to both be bounded, because every feasible solution to ${LP_2}$ gives a finite upper bound to the optimum of ${LP_1}$ (which then cannot be ${+\infty}$) and every feasible solution to ${LP_1}$ gives a finite lower bound to the optimum of ${LP_2}$ (which then cannot be ${-\infty}$). $\Box$

What is surprising is that, for bounded and feasible linear programs, there is always a dual solution that certifies the exact value of the optimum.

Theorem 5 (Strong Duality) If either ${LP_1}$ or ${LP_2}$ is feasible and bounded, then so is the other, and

$\displaystyle opt(LP_1) = opt(LP_2)$

To summarize, the following cases can arise:

• If one of ${LP_1}$ or ${LP_2}$ is feasible and bounded, then so is the other;
• If one of ${LP_1}$ or ${LP_2}$ is unbounded, then the other is infeasible;
• If one of ${LP_1}$ or ${LP_2}$ is infeasible, then the other cannot be feasible and bounded, that is, the other is going to be either infeasible or unbounded. Either case can happen.

We will return to the Strong Duality Theorem, and discuss its proof, later in the course.

## 14 thoughts on “CS261 Lecture 6: Duality in Linear Programming”

1. Seriously… You’ve summarized the concept painstakingly and a big thanks for it because I am referring to these notes for my exam… But just a thought… Instead of doing a lot of manual calculation, can’t we feed this problem to a computer and let it churn out the result?! Why should we strain our brain with these manual calculations when computer can immediately give us the result with steps…

2. Please expond a little more ou duality especially using examples to find the duals of given primals.

3. Excellent!! Pretty much clarifying and rigorous!! I’m looking for the promised strong theorem’s proof, though. I wonder if you could refer to a good exposition of the (weak and strong) theorems of complementarity in LP.
Thandks a lot.

4. awesome tutorials ,,, thanks thanks and thanks 🙂 🙂

5. The nice thing is that instead of Introducing duality just by definition, he guides the thought of the student gradually towards the duality.
@subramanian: there is a saying that with computer ‘garbage in garbage out’ . Now you have to know the process in order to be able to control the validity of some tones of printouts as is the norm for a medium size LP real life problem.
Regards

George Kakarelidis
Lecturer LP & Statistics
T.E.I. of West Greece

6. Great article! Just one little thing, I think there’s a type-o in the equation right after:

“For every choice of non-negative scaling factors {y_1,\ldots,y_m}, we can derive the inequality”

The last y multiplying (a_m …) should be y_m instead of y_n, correct me if I’m wrong I might be missing something!

7. Thanks for u are presentation in some way but add more notes to encouragement his/her lecture

8. This is the clearest explanation of LP duality I could find. Awesome work and thank you so much!

9. Thanks,,,for clarification of a relatively concept theorem…for beginner like me.

10. The first six sentences of this blog taught me more about duality theory than an entire course and three textbooks! Thank you very much!

11. Seriously, Thank you. Brilliant write up. I learned a lot from this post. Hope you keep writing about different topics.