The document discusses complementary slackness, a condition for optimality in linear programming. It presents three theorems:
1) If the primal problem is feasible and bounded, then the dual is feasible and bounded, and their optimal values coincide.
2) For feasible primal and dual solutions x0 and y0, if their objective values are equal, then both solutions are optimal.
3) For feasible primal x0 and dual y0 solutions, their objective values are equal if and only if for any constraint where the dual variable y0 is positive, the corresponding primal constraint is tight, and vice versa.
It proves the third theorem, called complementary slackness, and notes it provides a new criterion for
The document discusses complementary slackness, a condition for optimality in linear programming. It presents three theorems:
1) If the primal problem is feasible and bounded, then the dual is feasible and bounded, and their optimal values coincide.
2) For feasible primal and dual solutions x0 and y0, if their objective values are equal, then both solutions are optimal.
3) For feasible primal x0 and dual y0 solutions, their objective values are equal if and only if for any constraint where the dual variable y0 is positive, the corresponding primal constraint is tight, and vice versa.
It proves the third theorem, called complementary slackness, and notes it provides a new criterion for
The document discusses complementary slackness, a condition for optimality in linear programming. It presents three theorems:
1) If the primal problem is feasible and bounded, then the dual is feasible and bounded, and their optimal values coincide.
2) For feasible primal and dual solutions x0 and y0, if their objective values are equal, then both solutions are optimal.
3) For feasible primal x0 and dual y0 solutions, their objective values are equal if and only if for any constraint where the dual variable y0 is positive, the corresponding primal constraint is tight, and vice versa.
It proves the third theorem, called complementary slackness, and notes it provides a new criterion for
The document discusses complementary slackness, a condition for optimality in linear programming. It presents three theorems:
1) If the primal problem is feasible and bounded, then the dual is feasible and bounded, and their optimal values coincide.
2) For feasible primal and dual solutions x0 and y0, if their objective values are equal, then both solutions are optimal.
3) For feasible primal x0 and dual y0 solutions, their objective values are equal if and only if for any constraint where the dual variable y0 is positive, the corresponding primal constraint is tight, and vice versa.
It proves the third theorem, called complementary slackness, and notes it provides a new criterion for
Lecturer: Sundar Vishwanathan Computer Science & Engineering Indian Institute of Technology, Bombay
1 Complementary Slackness Primal Dual
max cT x min y T b Ax b AT y = c y0
We proved this in the last lecture.
Theorem 1 If the primal is feasible and the cost is bounded, then the dual is feasible and its cost is
also bounded. Moreover, their optimum values coincide.
The following theorem follows from the above theorem.
Theorem 2 Consider an x0 and y0 , feasible in the primal and dual respectively. Then both are optimum
i cT x0 = y0T b.
The proof is an exercise. One way is to use the hint given below. Note that cT xf = yfT Ax yfT b for any feasible xf and yf .
Theorem 3 (Complementary Slackness) Consider an x0 and y0 , feasible in the primal and dual
respectively. That is, Ax0 b and AT y0 = c; y0 0 . Then cT x0 = y0T b if and only if (y0 )i >0) Ai x0 = bi .
Note that this gives a new criterion for optimality. The second criterion is called Complementary Slackness. It says that if a dual variable is greater than zero (slack) then the corresponding primal constraint must be an equality (tight.) It also says that if the primal constraint is slack then the corresponding dual variable is tight (or zero.) Notice that if y0 were an extreme point in the dual, the complementary slackness condition relates a dual solution y0 to a point x0 in the set F in the primal. When we add to this, the fact that x0 is feasible, we may infer that both points should be optimal. We prove this formally below. Proof: First assume that the complementary slackness condition holds. We need to prove that the
1 2
costs of the points are equal.
X m y0T b = y0j bj j =1 Xm = y0j (Aj x0 ) (using complementary slackness) j =1 Xm X n ! = y0j Aji x0i j =1 i=1 0m 1 X n X = x0i @ Aji y0j A i=1 j =1 = T0 x c (using AT y0 = c ) = T c x0 Now assume that the costs are equal. cT x0 = xT0 c 0m 1 Xn X = x0i @ Aji y0j A i=1 j =1 Xm X n ! = y0j Aji x0i j =1 i=1 X m = y0j (Aj x0 ) j =1 Xm y0j bj (using y0j 0 and Aj x0 b ) j =1 = 0T y b But we know that cT x0 = y0T b. Hence, y0 > 0 ) Ai x0 = bi .
2 Infeasibility and Unboundedness
Every LP problem is either feasible or infeasible. Infeasibility means that there is no solution to fx : Ax bg. Exercise: Give an example of an infeasible LP. Feasible problems either have a solution or are unbounded. This will depend on the cost function. Exercise: Give an example of a feasible but unbounded LP. What happens to the dual in these cases? In particular can both the primal and dual be infeasible? The answer is yes. Exercise. Exhibit such a primal-dual pair. In the ensuing discussion we will assume that at least one of the primal and dual is feasible. We rst note that if an LP is unbounded then the dual will be infeasible. If the dual were feasible then the cost at any feasible point of the dual is an upper-bound on the cost of the optimal primal solution. Prove this. Exercise: If the LP is infeasible, and the dual is feasible prove that the dual will be unbounded. We will collect all this in the form of a theorem in the next lecture. 3
A Point on Degeneracy: In general, LPs need not be degenerate. Our description of Simplex, its proof of correctness and the subsequent proof of the Duality theorem uses this assumption. However all of this holds even when the LPs are not degenerate. The description of Simplex needs to be modi ed though. An additional problem that arises then is cycling. We will not bother about these points in this course however we will assume the theorems in general. The fact that at an optimum vertex the cost vector can be written as a non-negative linear combination of the normals is also true when the optimal point is degenerate. These are good exercises to try. Some hint will be given in the next lecture.
