[MUSIC] Let us now look at linear programming duality from a geometry perspective. We have seen that the minimum of the primal, 7x1 plus x2 plus 5x3 such that x is feasible, is at least equal to the maximum of the dual 10y1 + 6y2 such at y feasible. Actually, the linear programming duality theorem says much more than that. There's an equality is an equality. It's not just greater than or equal but it's exactly equal. The minimal of the primal, the optimal value of the primal, is equal to the optimal value of the duo. In general, it's a little bit more general than that. There are more cases because a linear program might have no solution. So if we state this in general, the primal will be same main of c dot x such that the vector x satisfies Ax is greater than or equal to b, and x is non-negative. The dual, as we constructed, max of b dot y such that a transpose y is less than or equal to c and y is not negative. The dual of the dual is the primal again. What does the theorem say about these two primal and dual linear programs, that this pair of linear programs that are dual to one another? It says that if both are non-empty both have finite values then those values are equal. This is the most interesting case for us the most relevant for the design of algorithms. However there are some other possibilities. The dual could be infinite, in that case the primal is empty. The primal could be infinite, minus infinity, in that case the dual is empty. Or it could be that both are empty, this is a pathological case that never comes up in practice in computer science as far as I know. So let's look at the geometry of duality. Let's do it by example. Here is an example of a linear program. We have two variables, x1, x2. So we can draw this in two dimensions. X1 and x2 are non-negative. X1 non-negative means we are in the east half plane, bounded by the line of equation x1 equal to 0. X2 non-negative means we're in the north half plane, bounded by the horizontal line x1 equal to 0. So we are in the northeast quadrant. And in this northeast quadrant, we have some additional constraints, x1 + 4x2 is a most 16. X1 + 4x2 is at most 16, means we're at half plain bounded by the narrowed equation, x1 + 4x2 = 16. 6x1 + 4x2 is less than 30 where in the half plane bounded by the line of equation 6x1 + 4x2 = 30. 2x1- 4x2 is more than 6 means we are in the half plane bounded by the line of equation 2x1- 5x2 = 6. If you intersect all those half planes, what do you get? You get the polytope that is in the shaded in yellow here. The intersection of all these half planes gives you this complex object bounded by these lines. Hyperplanes, in general. What about the objective? Maximize 6x1 + 5x2. Here are the level lines, 6x1 + 5x2 equals maybe 2, 3, 4, 5 and so on. And as you move in this direction you had increasing values of 6x1 + 5x2. You're trying to maximize this subject to being in this yellow shaded region. So you're moving this line, parallel lines, until you're barely touch this yellow region. And then you're outside. This point, this is the optimal value. So that is the interpretation of the primal LP. What about duality? Duality. We say that, we think complex combinations of constraints. Let's do it. Take a constraint, x1 + 4x2 less than or equal to 16, this line. Multiply by one quarter, 0.25x1 + x2 is at most 4, same line. Multiplying by one quarter does not change the equation. This does not change the geometry. Considered the other line 6x1 + 4x2 is at most 30. Here is the corresponding line when you have the qualities. Add these two equations. 6.25x1 + 5x2 is at most 34. Where do we see this geometrically? This is the equation if we put an equality. This is the equation of a line. What can I say about this line? This line goes through the point of intersection of x1 + 4x2 = 16 and 6x1 + 4x2 = 30. Because If x1, x2 satisfies both, 0.25 x1 + x2 equals 4 and 6x1 + 4x2 equals 30. If it satisfies both of these with equality, then it also satisfies that with equality. In other words, if a point belongs to both this line and that line. Then it belongs to the new line. So the new line will go through the point of intersection of those two constraints. It goes through and then we can rotate. And rotating means changing the coefficients to get some convex combination. But still, it's something which is implied by the other two. So it is something that still never enters the yellow region. So we have, by varying the coefficients, we can get any line going through here that is between here and there. These are the equations we may get. Okay, so that's the first step, getting this. Then from this we can deduce 6x1 + 5x2 with at most 34. How do we do this? How do we interpret this? Here we said since x1 is non negative, 6.25x1 is greater than or equal to 6 x1 therefore this inequality implies 6x1 plus 5x2 is at most 34. How do we interpret this geometrically? If we take the orange line, 6.25x1 plus 5x2 is at most 34, go up to the axis x1 equal to 0. We could rotate and that corresponds to diminishing the coefficient of X1. Rotates until we get the coefficient we wish. The line of the equation 6x1 + 5x2 = 34 is the line that goes through that intersection point, orange line intersect this vertical axis rotated a little bit. Rotated until when? Until we picked a line that has exactly the right slope. A slope parallel to our objective function. So with that, we can prove that the objective is, at most, 34. This corresponds to finding a feasible dual solution of value 34. So that's all the operations we did, taking complex combinations of constraints can be seen as taking points on the polytope doing convect combinations of things that go through them. And then rotating a little bit. So what does the linear programming duality theorem say? It says that these linear programs, this pair of linear programs, if they both have finite values then these values are equal. And what does this mean? It means that if you consider your polytope for P that is finite. Then there exists a way to get exactly the optimal value by doing what? By doing constraints. By taking a choice of constraints that go through this optimal point. Complex combinations so as to make the combination be exactly parallel to this hyper plane, the level line of the objective. And then the value of the objective will be exactly the optimal value. In other words, there always exists, if we have a finite polytope, not empty, there always exists a combination of constrains of the primal that imply exactly the correct upper bound. That's what the linear programming duality theorem tells you. So with this we are done with the geometric discussion of LP Duality.