Video 11-4: LP Duality

0:03 the real power of of LPS or approximation algorithms comes via the duality theory. And so um I'm going to try to uh convince you of that first in in the abstract and then we'll see examples tomorrow.

0:17 Uh what's this about? So let's again take a step back. Why did we use LPS for these optimization problems? Well, we wanted a lower bound. say it's a minimization problem just to fix the language. Uh we could from the relaxation get a lower bound on the optimal solution for our problem by taking the fractional solution. Now uh there's another technique to get that namely dual problems where you also get somehow a lower bound on the optimal objective uh function and it it has some uh benefits as you'll see later. Uh let's first see um what this works like and this I don't want to want to rush too much. Um because I think it's uh is if you've seen it once the right way you you never need to remember the the rules for dualization. So here's our um fictitious uh LP from before. The goal is to somehow bound its objective value. So it's a minimization problem. We'd like to have a lower bound for how good can this possibly be.

1:39 So we want a lower bound for this 7 x1 + x2 + 5x3. But of course subject to the constraints um otherwise it wouldn't be a solution. And so um one option is we can take this uh objective function and we can make uh because the x's are non- negative we can make some of the coefficients smaller that makes the overall value smaller. In particular we can take instead of seven we can take x1 instead of + one we can take minus one and instead of five we can take three and then I've essentially reproduced this first constraint. So because x is feasible, this got to be bigger than 10. Tada. I've proven a lower bound on the optimal objective value subject to the constraints of 10. Right? All I've done is uh I've rewritten the objective function uh using the constraints and what I've done here is I just lowered the coefficients for each of the variables from 7 to one, from one to minus one, from five to three. Now I could try let's try to make use of the second constraint, right? Um, if that works so well, maybe we get something better.

3:12 And I could try to get to this, but it doesn't work for X2. So, I can't really use that second constraint in the same way. Also, uh, the lower bound we would get here is even weaker. So, it's it's not interesting. But uh there's also kind of a a hurdle here in using this trick. Now what else could you do? Um these are inequalities and inequalities can be added up. So if you add up those two, you get 6 x1 plus x2 and 2 x3.

3:54 These are component wise smaller than our bound here. So I can I can take the sum of the two constraints. Let's call this a and b. I'm doing a + b. Then I get what did I say? 6 x1 x1 plus x2 2 x3. And the sum of the right hand sides is 16, which is better than my 10 from before. So I've made some progress. Aha. So how far can I push this? In general, I can multiply these uh entire constraints with some arbitrary numbers. I cannot just take the sum. I can take any linear combination. Right? So I can multiply the left and right hand side with some arbitrary value. Aha. But maybe not arbitrary because I have an inequality. So uh I certainly would want that my my y's are non- negative. Right.

5:13 Okay. also uh to have a useful uh statement I cannot produce this uh middle part where I'm making any of the uh coefficients larger or lower bound. So I need to make sure for example for x1 I want to make sure that y1 + 5 y 2 is below seven right otherwise I don't get this bound and I get the same for the other two uh variables. So - y1 + 2 y2 should be below 1 and 4 x3 I get this constraint with 3 y1 - y2 less or equal 5. And uh what's the lower bound I get from doing the linear combination?

6:24 y 2. And so I can pick any such y's and I might as well pick the highest lower bound. That's the best I get. Okay, is the process clear?

6:35 and see how this uh just by the numbers nicely corresponds to um uh working superficially on the LPS. The coefficients of the objective of the objective function here turn into the right hand sides of the inequalities. The uh right hand sides of the inequalities in the original problem turn into the coefficients of the objective function. If you've had inequality constraints here, that means that the multipliers you put to the inequalities have to be non- negative. Otherwise, you flip the sign. But had there been an equality here, you could have multiplied by a negative number. It would have been okay. And so you get uh constraints on the on the variables here come from the uh constraints in the in the original problem. And um in a way vice versa uh if you have greater equal here then you can allow the coefficients to drop. If say x1 would have been allowed to be negative then I I can only get a valid bound if uh the coefficients are equal to seven.

7:57 Okay. So you're you're playing a game where um you try to get a lower bound for the objective function and that game turns out to be another LP and that's exactly the dual LP.

8:15 Uh I know that most or all of you will have seen dual LPS in some sort but often times it's just here's the definition deal with it. uh whereas you can very very uh logically uh derive all the rules for dualizing LPS that way.

8:36 If you write them in standard form then it's also quick to memorize if you prefer. Um if that was your your original problem the primal LP then the dual will have this shape min turns into max. uh the coefficients here they just swap and a gets transposed and these are the generalization I uh I mentioned uh on the example already. Okay.

9:09 Now so far this was this was kind of by example shown what we're trying to do. Um this is just the definition of if you start here that's the dual problem. Uh whatever you prefer you can show or any feasible solution in the primal respectively dual the pair of those they always give you a bound for the optimal object for for the objective function values namely uh for the minimization problem you get a higher thing than for the maximization problem. If you imagine oh it's not bounded. So there's there's the the values for the cost function then uh you have the ctx and bty they somehow lie here and you always get that they're they're ordered this way. Uh that's called weak duality and it's a simple consequence of the definitions. You can prove it in general on this on this normal form as follows. Uh if you take the the dual constraint a transposed y less than c transpose the inequalities these are element wise inequalities on a vector. So you can you can transpose that and the inequalities couldn't care less I guess. So cranspose is greater or equal a transpose y the whole thing transpose and you know the rules for transposition means you flip uh the product inside around so it's yta and then you can just rewrite the objective value of the primal start from here you replace c with that ct here then you have uh you have this um associvity you change the order of the parenthesis. Then you use the primal constraint on ax and that gives you a bound on uh of b here and then that's a a scalar.

11:12 It's just a number. So if you take um yt b or bt y is the same. That's weak duality. Okay. So you can always uh get this bound and that's almost by definition. we've chosen the LPS so that this is the case. Uh the more exciting part is that you can or LPS show that the exactly uh optimal values are are the same. They coincide.

11:40 Um formally if you have the some optimal solutions xstar and yar for the primal and dual respectively then the objective values match. that's a a bit more more uh more linear algebra to prove. So I'm I'm not too keen on doing it. We're just going to use this as a fact. And uh there's another cool thing that's useful for designing algorithms sometimes. Uh this is a characterization of when a pair of solutions is optimal. um namely so some feasible solution x feasible for the primal y feasible for the dual are jointly optimal if and only if these these two conditions are are true. So uh for every index j either xj in the primal is is at zero so it's kind of tight on its non- negativity constraint or the uh corresponding inequality in the the cha constraint in the duel is tight. So here you have equality and that's not not helpful I guess. um you always have equality on one of those two constraints either in the primal or in the dual and you have this for all J and for all I they're playing uh opposite roles and they're called complimentary slackness conditions because you cannot have slack in both of the constraints and be optimal and in in particular this is an if and only if. All right.

13:27 Um, if you want to take the uh complexity angle, you can say for for LPS, not integer linear programs. All of this is just for for LPS, right? Not for the integer linear programs. Uh, for normal LPS, the fact that you have strong duality means that you have a yes and a no certificate. uh primal and dual variables. And so we know that the decision problem is in in NP and in co-enp. But we already know it's in P. So maybe that's not so surprising. Um for for the integer linear programs, much of what's on this current slide breaks down, but the weak duality you can still rescue. That stays stays valid. And you can you can dualize integer linear programs in just the same way. Um using the the idea of lower bounding the objective