[MUSIC] Duality, let us continue our conversation about linear programming duality. The Strong Duality Theorem in general, there are several possible cases depending on whether the primal or the dual are empty or have infinite value. But in a typical case, in the case that usually comes up for algorithmic applications and computer science, the primal has a value that is finite. The dual has a value that is also finite, and the values of the primal and of the dual are equal. So, now we're going to see the proof of the easy side of this inequality, the Weak Duality Theorem. If you look at the maximum value of cx, given Ax is less than b and x is non negative, this is less than or equal to the minimum value of b y, such that A transpose y is at least c and y is non negative. That is the weak duality theorem. How do we prove this? So, there are two ways to present this, one is the compact form with the matrix and the vectors, and the other one is the extended form where you write out every little coefficient and only the dot, dot, dots express a summary. So, these are two forms of the same linear program. How do we prove that the maximum of the linear program on the left side is less than the minimum of the linear program on the right side? We must prove that every value here is less than every value there. So let us proceed with this proof. The primal, the dual. We're going to take a vector x that is feasible for the primal, it satisfies all the constraints, and a vector y that is feasible for the dual, it satisfies all the constraints. What must we prove? We must prove that the objective value 4x for the primal, c1x1 + c2x2 + cnxn ,is less than or equal to b1y1 + b2y2+ bmym. Let us start with this proof. So first we use the constraints of the dual. So, we want to upper bound c1x1 + c2x2 + cnxn. What do we know? We know something about ci. We know that c1 is less than or equal to this expression, a11y1 + a21y2 + + am1ym. c2 Is less than, equal to that expression and so on, all the way to cn. So what do we do? In our objective, c1x1 + + cnxn, we upper bound c1 by this expression, c2 by the corresponding expression, and cn by that expression here. Okay, first we use the constraints of the dual to upper bound the cis. Next, we now have a double summation. Sum over i of xi times sum over j of sum aijs times yjs. So what do we do? We invert summations. We have a double summation, where xi has some complicated factor. We rewrite it with yj in factor of various things. In particular, what is a factor of y1? a11 times x1, + dot dot dot, + n factor of y1, a1n times xn. So a11x1 + dot, dot, dot + a1nxn in factor of y1. We continue in the same way, (am1x1 + + + amnxn)ym. Okay. We have inverted summations. Next, what do we do? Next, we use the constraints again. But this time, they are the constraints of the primal. What do we know? We know that a11x1 + + a1nxn, this is the left-hand side of one of the constraints of the primal. So we know that it's less than or equal to b1. We can upper bound it by b1. The next term can be, the next coefficient can be upper bounded by b2. And the last one can be bounded by bm. And so what we have is the expression we just wrote is less than or equal to b1y1 + b2y2 + + bmym. Okay, so three steps. Constraints of the dual, invert summations, constraints on the primal. And what do we get? In summary, we started from x feasible for the primal, y feasible for the dual, and we proved that the c1x1 + + cnxn, the objective function for the primal, is less than b1y1 + + bmym, the objective function for the dual. And so if we take the maximum over every x feasible for the primal, we get something which is less than or equal to the minimum for over every y feasible for the dual. And that is exactly the Weak Duality Theorem. So with this, we have proved the Weak Duality Theorem in general. Why did I bother going through this calculation? Because this proof is good to memorize, it can be useful to understand the analysis of primal dual algorithms. And so, we have made a little progress here in understanding LP duality.