Linear Programming & Combinatorial Optimization (2022) Lecture-24

In today's lecture (04/03/2022), we covered one of the most important aspects of Duality (especially from the point of view of designing and analyzing Combinatorial Optimization Algorithms based on the Primal-Dual Method) --- the Complementary Slackness (abbreviated to CS) conditions.

Theorem 4.6 (GKT): [Complementary Slackness Theorem] For any primal-dual pair of LPs, say (P) and (D), and feasible solutions x* and y* (for the respective LPs): x* and y* are both optimal solutions (for the respective LPs) if and only if x* and y* satisfy the CS conditions (stated below):

CS1: For each primal constraint, either the constraint is TIGHT for x* or the corresponding dual variable (in y*) is ZERO.

CS2: For each dual constraint, either the constraint is TIGHT for y* or the corresponding primal variable (in x*) is ZERO.

We proved a special case of the Complementary Slackness Theorem. The general case just requires more bookkeeping, and does not use any novel mathematical ideas. (So, we will not be proving the general case.)

In the next lecture (07/03/2022), we shall return to Geometry and look at Optimality from a geometric point of view.