Okay, so the last condition or the last theorem that we're going to talk about is called complementary slackness. So this is a very interesting property I would say. So let's take a look. So we know we have the primal and the dual linear programs. In the previous examples, your dual constraints is y transpose A should be greater than or equal to C transpose. All right? Now, that's going to introduce slack variables, lets call it v and put that into the dual linear program. So we are going to have y transpose A minus v transpose becomes c transpose. So the condition obviously has something to do with these slack variables. So what's that? Somehow it says, your dual slack variables and your primal solution are somewhat complementary. So that's the [inaudible] considered a primal LP defining one and your dual program defining two. So in this case, you're primal solution x bar and your dual solution now should be expressed as y bar, v bar. They will be primal and dual optimal if and only if the following thing. So first, they should be feasible of course and the second, your v bar transpose x bar goes to zero. Okay? So as long as you satisfy condition one and condition two, you know these two solutions are primal and dual optimal or the other way. If you know they are primal and dual optimal, of course they are feasible and they must satisfy the fact that the product would be zero. So let's see why that is true. We know that we have c transpose x bar should be equal to this one. So that's because your c transpose equals to y transpose A minus v transpose. So if it is true for all the solution, it is true for y bar, v bar. Then you take away the multiplication, you split the multiplication and then you get y bar transpose x bar and minus v bar transpose x bar. So we have these two parts. We know Ax bar is b, all right? Because x bar is feasible and then v bar transpose x bar is still here. So we're going to have the fact that c transpose x bar should equal to y bar transpose b minus v bar transpose x bar. So this obviously tells us that your v bar transpose x bar must be zero if and only if your c transpose x bar equals y bar transpose b. Okay? So if this one and this one are the same, then obviously this must be zero. But you also know that this equality implies x bar and y bar are optimal. Okay? So immediately this says that if this is true, then they are optimal. So in other words, if this guy v transpose x is zero, then this is true and then they are optimal. Or the other way. If you see that first they are optimal, then obviously strong duality says the two terms are equal, then your v transpose x would be zero. Okay? So that's how strong duality and the complementary slackness they imply each other. So now one thing to keep in mind is that if your v bar transpose times x bar is zero, that means each pair of primal variable and a dual slake, the product is zero. Why is that? Because everything is non-negative. So if your v bar transpose x bar is zero, then obviously you know, the bar I times x bar I, sum of I from one to n, or you call it j doesn't really matter. So if you do all of this, if this guy, the summation is zero, and then because for each pair you can be no less than zero, so it must be the case that all the pairs are zeros. Okay? So this means for any primal variable that corresponding duals slack, the product would be zero. Okay? So on the other hand, if you know your dual constraint is non-binding, that means your VI is not zero, all right? In that case, the corresponding primal variable must be zero. So if dual constraint is non-binding, that primal variable would be zero. If a primal constraint is non-binding, your dual variable must be zero. So let's take a look at again, an example. So this example is again the one that we just mentioned. So you have a primal, you have a dual, both of them at this moment they are inequalities. So let's add slack variables and the slack variables to these two programs to make both of them, I should say standard form, all right? So in this case, we're going to see that primal variables and the duals slacks, they should have some relationship. Your x1 multiplied by v1 would be zero if you are talking about a peer of optimal solution. Your x2 times v2 would be zero if you are talking about a pair of optimal solutions. Similarly, for s and y, it would be the same thing. Your s1 multiplied by y1 would be zero if you are talking about a pair of optimal solutions, and so on and so on. By knowing that x bar, y bar, v bar is bar construct pair of optimal solutions. You have five pairs of equalities. This would be useful if you want to construct a dual solution given a good primal feasible optimal solution. How to do that. Let's take a look at this solution. Let's say our x bar, s bar is primal optimal. Then we know x bar would be three and two, and s bar should be 0, 0, and 1. Let's try to find a dual optimal solution, which should be y bar v bar, without solving the dual linear program. Previously what we did is that CB transpose A B inverse, we used that formula to get a dual optimal solution. Now let's try the other way. Let's try to use complimentary slackness. The thing is the following. We know previously what we have is that we have three dual variables and we have those inequality constraints. We add v into our equations and make them equality constraints. We like equality constraints because we are able to solve linear systems and find a solution. But if a solution must satisfy two equations and we have five variables, then there's no way for us to really solve and get a solution. Too many solutions may satisfy this system. But luckily, what we know is that we know from the primal solution, they are three positive values, x_1, x_2, and s_3, they are all positive. That means in the corresponding part, v_1, v_2 and the y_3 must be equality. Why is that? Because x_1 and the v_1, the product must be 0, if you are talking about the optimal pair. X_2, v_2, their product must be 0, if they are optimal. Finally, s_3 and the y_3, they must be multiplied to 0 if they are optimal. In short, if a primal solution is positive, the dual slack must be zero and the other way. That allows us to eliminate v_1, v_2, and the y_3. We will only have a two-by-two linear system, which is here. Then once we solve that two-by-two linear system, we get this one. Your y bar 1 and y bar 2 must be one- fourth, one- fourth, which is exactly what you may obtain from CB transpose A B inverse. This again confirms the fact that this is optimal. We may again see that their objective values are identical. You may find that all the things somewhat point to the same result, and that's true because for primal and the dual pairs, all this strong duality, CB transpose AB inverse, and this is complimentary slackness. They all imply each other. Somehow this again conference the fact that primal and dual, they are equivalent. Lastly, maybe we want to give an idea about why we want to have duality. With duality now, we know one thing. We know for each primal program, there is corresponding to your program and somehow they are equivalent. The thing is that for primal, typically we want to find the primal optimal solution directly. Now instead, we may first get a dual, find dual optimal solution, and then use complementary slackness or the formula to get back to our primal solution. That's okay. But maybe you want to ask, what's the point of doing that? Well, there are actually many reasons, but here I'm going to give you one that makes sense to you at this moment. We know the computation time of the simplex method is roughly proportional to m cubed. Here, m is the number of functional constraints. When you have a lot of functional constraints, that's going to make simplex method slower, more things to consider it. Because each time when you have a matrix like this, you select one part to be AB, and then the part on it of computation is to calculate AB inverse. The AB inverse basically need the complexity is roughly m cubed, and that's something we mentioned in the past. On the other hand, the number of variables does not matter that much. If you have a program where m, the number of functional constraints is much larger than your number of variables, then solving this primal program directly may actually takes a lot of time. On the other hand, solving the dual may actually save a lot of time because in your dual program, the number of variables would be a lot and the number of functional constraints would be fewer. That may actually save you a lot of time. This may be just one reason to know duality and apply duality. There are actually many other reasons. We will see some more. Some will be talked about in the next videos in today's lectures, some will be discovered sooner or later. There are actually more and more. Hopefully, you will also see some of them. In general, knowing some properties of the optimal solution always helps.
