C&O 355 Lecture 9 N. Harvey http://www.math.uwaterloo.ca/~harvey/ Outline Complementary Slackness Crash Course in Computational Complexity Review of Geometry & Linear Algebra Ellipsoids Duality: Geometric View We can generate a new constraint aligned with c by

taking a conic combination (non-negative linear combination) of constraints tight at x. What if we use constraints not tight at x? x2 -x1+x2 1 x x1 + 6x2 15 Objective Function c x1 Duality: Geometric View We can generate a new constraint aligned with c by taking a conic combination (non-negative linear combination) of constraints tight at x. What if we use constraints not tight at x?

x2 -x1+x2 1 x Doesnt prove x is optimal! x1 + 6x2 15 Objective Function c x1 Duality: Geometric View What if we use constraints not tight at x? This linear combination is a feasible dual solution, but not an optimal dual solution Complementary Slackness: To get an optimal dual solution, must only use constraints tight at x.

x2 -x1+x2 1 x Doesnt prove x is optimal! x1 + 6x2 15 Objective Function c x1 Primal LP Weak Duality Dual LP

Theorem: Weak Duality Theorem If x feasible for Primal and y feasible for Dual then cTx bTy. Proof: cT x = (AT y)T x = yT A x yT b. Since y0 and Axb Primal LP Weak Duality Dual LP Theorem: Weak Duality Theorem If x feasible for Primal and y feasible for Dual then cTxbTy. Proof: When does equality hold here? Corollary: If x and y both feasible and cTx=bTy then x and y are both optimal.

Primal LP Weak Duality Dual LP Theorem: Weak Duality Theorem If x feasible for Primal and y feasible for Dual then cTxbTy. Proof: When does equality hold here? Equality holds for ith term if either yi=0 or Primal LP Weak Duality

Dual LP Theorem: Weak Duality Theorem If x feasible for Primal and y feasible for Dual then cTxbTy. Proof: Theorem: Complementary Slackness Suppose x feasible for Primal, y feasible for dual, and for every i, either yi=0 or . Then x and y are both optimal. Proof: Equality holds here. General Complementary Slackness Conditions Let x be feasible for primal and y be feasible for dual. Primal

Dual Objective Variables max cTx x1, , xn min bTy y1,, ym Constraint matrix Right-hand vector Constraints versus Variables

A b AT c ith constraint: ith constraint: ith constraint: = yi 0 yi 0 yi unrestricted xj 0 xj 0 xj unrestricted

jth constraint: jth constraint: jth constraint: = for all i, equality holds either for primal or dual and for all j, equality holds either for primal or dual , x and y are both optimal Example

Primal LP Challenge: What is the dual? What are CS conditions? Claim: Optimal primal solution is (3,0,5/3). Can you prove it? Primal LP Example Dual LP CS conditions:

Either x1+2x2+3x3=8 Either 4x2+5x3=2 Either y1+2y+2+4y3=6 Either 3y2+5y3=-1 or y2=0 or y3=0 or x2=0 or x3=0 x=(3,0,5/3) ) y must satisfy: y1+y2=5 ) y = (16/3, -1/3, 0) y3=0 y2+5y3=-1

Complementary Slackness Summary Gives optimality conditions that must be satisfied by optimal primal and dual solutions (Sometimes) gives useful way to compute optimum dual from optimum primal More about this in Assignment 3 Extremely useful in primal-dual algorithms. Much more of this in C&O 351: Network Flows C&O 450/650: Combinatorial Optimization C&O 754: Approximation Algorithms Weve now finished C&O 350! Actually, they will cover 2 topics that we wont Revised Simplex Method: A faster implementation

of the algorithm we described Sensitivity Analysis: If we change c or b, how does optimum solution change? Computational Complexity Field that seeks to understand how efficiently computational problems can be solved See CS 360, 365, 466, 764 What does efficiently mean? If problem input has size n, how much time to compute solution? (as a function of n) Problem can be solved efficiently if it can be solved in time nc, for some constant c. P = class of problems that can be solved efficiently. Computational Complexity P = class of problems that can be solved efficiently

i.e., solved in time nc, for some constant c, where n=input size. Related topic: certificates Instead of studying efficiency, study how easily can you certify the answer? NP = class of problems for which you can efficiently certify that answer is yes coNP = class of problems for which you can efficiently certify that answer is no Linear Programs Can certify that optimal value is large (by giving primal solution x) Can certify that optimal value is small (by giving dual solution y) Computational Complexity NP Can graph be colored with k colors?

Many interesting problems coNP NPcoNP Is LP value k? Is m a prime number? P Does every coloring of graph use k colors? Many interesting problems

Sorting, string matching, breadth-first search, Open Problem: Is P=NP? Probably not One of the 7 most important problems in mathematics You win $1,000,000 if you solve it. Computational Complexity NP Can graph be colored with k colors? Many interesting problems coNP NPcoNP

Is LP value k? Is m a prime number? P Does every coloring of graph use k colors? Many interesting problems Sorting, string matching, breadth-first search, Open Problem: Is P=NPcoNP? Leonid Khachiyan

Maybe for most problems in NPcoNP, they are also in P. Is m a prime number?. Proven in P in 2002. Primes in P Is LP value k?. Proven in P in 1979. Ellipsoid method Review Basics of Euclidean geometry Euclidean norm, unit ball, affine maps, volume Positive Semi-Definite Matrices Square roots Ellipsoids Rank-1 Updates Covering Hemispheres by Ellipsoids 2D Example

3 2 1 Dene T (x) = Ax + b where A = and b= . 0 1 1 Ellipsoid T(B) Unit ball B