Hello everybody. Welcome back to our Linear Programming Unit. Today we're going to talk about an interesting phenomenon in linear programs called duality. So let's recall the first example that we looked at here. We wanted to maximize 200M + 100W subject to this bunch of equations. Now it turns out we had a very clever way of proving that optimum was correct once we found it. So the best you could do is 60000, and there was a great way of proving it. We took one constraint, we multiplied by a hundred, we took another constraint and we multiplied it by half. We added those together and we got a new constraint that, if we satisfied our original constraints, it had to be the case. That 200M plus 100W, the thing we were trying to optimize, was at most 60,000. And this is a very interesting and general technique that if you want to bound your objective. You can try and do this by combining the constraints that you have together to prove a bound. So let's see what happens in general. You have a linear program, you say you want to minimize v1x1 plus v2x2 plus. all the way up to vnxn. Subject to a bunch of these linear inequality constraints A11x1 plus a12x2 plus dot dot dot is at least b1 and thenetc etc. So how can we try and do this? Well if you give me any constant ci bigger than 0, you can take the first constraint and multiply it by c1 and the second constraint multiplied by c2 and so on and so forth, and add those all up. And what you'll get is a new linear inequality, w1x1 plus w2x2 plus dot dot dot is at least T. Here the w i are some combination of the Cs, w i is the sum of c j a j i and t is the sum of c j b j and this is a new inequality. Now, if it's the case that w i is equal to Vi for all i, we have is that V1X1 plus V2X2 plus dot, dot, dot that thing we were trying to minimize is at least t. And so, if we can arrange for Wi to the Vi for all i, we've proven a lower bound on the thing that we're trying to minimize. So, we'd like to find there's a bunch of Ci's that are all non-negative such that vi is the sum of j = 1 to m of cj aji for all i. And so that subject to this constraints t the sum of cjbj is as large as possible. So we like the biggest lower bound we can. Now the very interesting thing about this, is that this system we just wrote down is actually just another linear program. We want to find the c in Rm such that cjbj the sum of that is as large as possible subject to a bunch of linear inequalities. CI bigger than or equal to 0 and a few linear equalities. vi is the sum of cj times aji. And so, to put this formally, given any linear program we can call the primal very often.. Say minimize v.x subject to Ax at least b. There's a dual linear problem, which is the linear problem that we want to maximize. Y.b subject to y transpose A equals v and that's just another way of rewriting our inequality constraints. And y at least 0. And it should be noted that even if your linear program wasn't exactly in this form, you can still write a dual program, it's with a linear program of trying to find a combination of the constraints. To bound the thing that you're trying to optimize. And so it's not hard to show that a solution to the dual program bounds the optimum for the primal. Suppose that you have a solution for the dual, you've got a y bigger than or equal to 0, such that y transpose A is equal to v. Then for any x where ax is at least b, well, x dot v is equal to y transpose ax. That's at least y transpose b, which is y dot b. And so y dot b, the solution to the dual, it's a lower bound to the solution to the prime. Now the surprising thing is that not just is this a way that you can get lower bounds, that these two linear programs they actually have the same solution. If you find the best solution for the dual program, it actually always gives you a tight lower bound for the primal. And the theorem here is a linear programming duality that says a linear program and its dual have the same numerical answer. And this is incredibly useful. On the one hand it says if you have a linear program and want to prove that your answer is optimal you could try and solve the dual to provide a matching upper band or lower band. It also means that if all you care about is the numerical answer you can try to solve with dual program rather than the primal. And often, dual program is easier to solve, and so this makes things more convenient. And even if the dual program isn't easier, often looking at the dual gives you some insight into the solution to the primal. Ok so that's the new programming duality. Let's look at some examples. For example, let's look at the max flow problem. The size of your flow is the total flow going out of a source minus total flow going into a source. Now, we have a bunch of these conservation of flow equations, and we can add any multiples of those that we like. And the objective stays the same. So when we do that, the thing we're trying to maximize is the same as the sum over all vertices V of some constant C sub V times the total flow out of vertex V minus the total flow into vertex V. Here C sub s needs to be 1 if s is a source and C sub t needs to be zero if t is a sign but for any other vertex V we can take C sub v to be anything we like. [COUGH] Okay, so we have this expression, what do we get when we write this down? And this is sum over edges from V to W of the flow along the edge times C sub V minus C sub W. We can now try to bound this above using our capacity constraints. And so the best we can do here, it's not hard to show is the sum over edges v to w of the capacity of the edge e times the maximum of either C sub v minus C sub w or zero. Okay so this gives us an upper bound and we want this upper bound to be a small as possible. It's not hard to show that we should pick our C sub v to always be either zero or one. Now if we do that, let C, be the set of vertices where C sub v equals one. The bound that we prove then reduces to the sum over edges V w, where V is in script C and w isn’t of the capacity h. But you'll note, C is just cut and this bound that we proved is just the size of the cut. And so, this dual program in some sense is just trying to find the minimum cut. Hence, linear programming in duality, in this special case, just gives us the max flow equals min cut. Okay, let's look at this other problem for example. The diet problem. Here we want to minimize the total cost of foods you need to buy, subject to constraints. It needs to meet your various daily requirements for various nutrients, and you need to get a non-negative amount of each type of food. So you've got this system, what's the dual program? Well okay, so for each nutrients N we have some multiple C sub N of the equation for that nutrient. And then we can add on positive multiples of the constraints even in non-negative amount of each type of food. Okay, so when we combine all of those together we're suppose to get A lower bound on the cost of our diet. And so, if you compare coefficients well, the coefficient we need to end up with for a food f is the cost of that food. And this should be equal to the sum of our nutrients N of C sub of N times the amount of that nutrients in the food f. Plus some positive amount that we got by adding whatever multiple we had on the constraint that we got a non-negative amount of that food. So what this says is for each food f, the cost of food f, should be at least the sum over nutrients N, times the amount of that nutrient showing up in this food. But there’s a nice way now of interpreting this C sub N. We can interpret it as a cost in order to buy a unit of nutrients N. And so if there was a market where you could just buy calories at the cost of Cn and you could buy protein at the cost of whatever. What the above equations are saying. Is that for each food you can't cheat the system by buying out food. You can't get nutrients more cheaply than you could by buying the nutrients individually. And the cheapest way to get nutrients is buying them individually it's pretty clear the total cost of a balanced diet is at least just the sum over nutrients at the cost of that nutrient times the amount of nutrient that you're required to have in your diet. And so, what this linear program tries to do, is it tries to find non-negative costs for the various nutrients that satisfy this, no food allows you to cheat inequalities. Such that the total cost of your diet is large as possible. Now, there's one interesting observation about the solution, supposed that we're actually trying to exactly achieved this lower bound. That would mean that you could never afford to buy overpriced food. You can never afford to buy foods where the cost of that food was strictly bigger than the total cost of all the nutrients that make up that food. You could only buy foods where the cost of the foods is exactly the cost of the nutrients in that food. And this gives us as an example of a general phenomena called complementary slackness where basically what this says Is that if you look at the solutions the dual, you should look at which equations you needed to use in the dual program. That tells you about which equations in the primal program need to be so in particular, complementary slackness is the following theorem. If you give me a primal in your program, minimize v. x subject to Ax at least b. And it's dual. Then if you take solutions to these two, if you use a positive multiple of an equation in the dual, if yi is strictly bigger than 0, in the dual. This happens only if the ith equation in the solution to the primal is actually tight. The ith inequality is actually an equality in the optimal solution. So let's reveal what this means. Let's suppose that we have a linear program to find by these five linear inequalities labelled 1, 2, 3, 4, 5 and the diagram below. We have allowed what regions this gray region and the red point located is the optimal. Now, suppose that we're looking for solutions of the dual program. Which of these five equations might actually be used as sort of positive multiple of those equations, in the solutions to the dual program? Well, it turns out the only equations that you could actually use are two and four because complementary slackness says that the only equations that get used in the solution to the dual are ones with that equation is tight in the primal. And in this case, two and four are the only lines of this solution to the primal actually lies on. And its those are the only equations that could actually be used in the solution. So in summary everything in your program has a dual in your program. The solution to dual actually bounds to the solutions to the primal. And surprisingly the LP na dit's dual has the same answer. And this means that the solution do dual actually is tight bound to the solution to the primal An. In addition, we have this complementary slackness where knowing the solutions to the dual tells you a lot about where the solutions to the primal lies. In fact, it tells you which equations in the solutions the primal needs to be tied. So that's basically everything we have for this lecture. Next lecture we're going to talk about proofs for these things so that material is not necessarily required, but if you'd like to see it, it's informative.