Okay, so this is Discrete Optimization, Linear Programming, Part V. So, what we are going to today is some really, really beautiful thing. Okay, so we're going to see duality. Okay? And at a higher level, okay, so you can think of, we are looking at the same thing but from two different angles. And we can see some very, very different things. So, most of you have probably seen this picture where you can see this beautiful young lady and this old ugly woman. Right? And so, this is duality. Right? So, this is going to be looking at the same thing, but from different angle. And to motivate you to this lecture, I want to tell you the story of, of, of [UNKNOWN] and [UNKNOWN]. So, so, so when [UNKNOWN] invented linear programming, he went to see John von Neumann. So, this genius mathematician and computer scientist with this encyclopedic knowledge of everything, right? So, he went to see him and start explaining the, the, the linear programming to von Neumann. And von Neumann, typically being a patient, you know, man, was kind of, you know, impatient that day. And said, you know, get to the point, get to the point. And so then, [UNKNOWN] say, oh, he wants me to get to the point. And so, he started going fast. And then, von Neumann stopped him, and started there he's writing all the results. And the things I'm going to show you today. Okay? And [UNKNOWN] was like, what's happening? You know, yeah. It's just deriving all this guy is just deriving all this on the fly. But von Neumann was also a very kind person. And he said at the end, I just don't want you to think that I'm deriving this on the fly, right. So, this is very, very similar to something I'm doing in game theory, okay. And therefore, you know, I'm postulating that these two things are the same, okay. And they were, they were, they are essentially the same, okay. And so, that's what duality, that's what I'm going to show you today. I'm going to show you these results on duality theory which are basically looking at linear programming in two different ways. Okay? So, so what I'm going to show you today is basically two linear programs. The primal which is essentially what we have been seeing all along. Okay? Which is minimizing this objective function c x subject to inequality. Ax greater or equal to b with all the variables being non-negative, okay. And then, I'm going to talk about another linear program, which we're going to call the dual. And that dual is going to maximize, okay, an objective function y b, y are the variables here, okay. So, y are going to be called the dual variables. The x, I called the primal variables. So, okay. Primal, dual, okay. And then, we have also a set of linear inequality, okay? y A is smaller or equal to c, instead of being greater or equal, it's going to be smaller or equal. Same matrix, okay? Different variables, okay? Primal variables, dual variables. And then, the y's are also going to be, you know, non-negative. Okay? So, let me show you an example here, so that you can see this on the, on the read example. This is the primal, this is the dual, right? The variable here, the primal variable, x1, x2, x3, okay? You see you see the coefficient, 3, 2, 4, okay? Then, you see these two constraints, okay? And then, you see the right hand side. Okay? in this particular case, 2 and 5. Okay? 2 and 5. Okay? This is a dual. Okay? Instead of minimizing, we are maximizing. We have two variables, the dual variables. Okay? And then, we have three inequalities here. Okay? I'm, I'm remove, you know, I'm not showing the non-negative constraints here. Okay? So, they are implicit. Okay? So, primal dual, you see these things. Okay? No, these two guys have a very strong relationship. So, I'm going to show you how we obtain the dual. Right? So, the first thing we do, is that we introduce these dual variables, y1 and y2. Okay? So, in a sense, with every constraints now, we are associating a dual variable. Okay? So, this is y1 and y2. And of course, in the dual is only expressed in terms of y1 and y2. The key point here is to remember these 2 variables are associated. There is as many dual variables as there are constraints in the primal. Okay, now, how do we obtain the objective? Right to we transform the min into a max, but the coefficients of the variables, where do they come from? Well, they come from the right end side of the inequalities in the primal, okay? So, you saw 2 and 5 here, okay? You see 2 and 5 here, okay. And you see now that the objective function is maximizing 2y1 plus 5y2, okay? So, in a sense you take this, you flip it, and you get the objective functions of the dual, okay? One thing stopped, okay? Now, how do we get the right hand side of the dual? Well, you take the objective function, right? So, the objective function of the primal is what? 3, 2, 4, is in term of the coefficient. And now, you see 3, 2, and 4 as the right end side of the dual, right? So, in a sense, the right hand side of the primal become the objective function of the dual. The objective, you know the objective coefficients of the primer become the right end side of the dual. Okay? And now, the trick is almost played, right? So, the only thing that we need to do is to look at the, the matrix that you see over there, okay? For the constraints, okay? So, so we look at the coefficients of, of the first column here, do you know? So, we see y1, y2. We take a column here, the coefficients for x1, okay? They are 2 and 2, and what you get here is essentially constraints. Okay? It's going to be 2y1 plus 2y2, okay. Smaller or equal to the value that we had already computed, which is 3. Okay. How do we obtain the second constraint? Well, you take the, you take the column associating, associated with x2 over there. Okay. The coefficient for x2 are what? 1 and minus 1. And therefore, these are the coefficients of the dual variable in the second constraint. 1, for x, y y1, and minus 1 for y2, and you get the third constraint. the second constraint. The third constraint is easy right? There is only one coefficient, and that is the coefficient for the dual, for the dual variable y2. And so, what you see here is, that the last constraint is simply y2 is smaller or equal to 4. Okay? So, in a sense, it's beautiful, right, the objective function becomes the right end side. The right end side of the primal become the, the objective functions of the dual. And then, this matrix, the column here becomes the row, and the, the column, you know, of the primal, become the row of the dual. Okay? And that's how you express this dual. Okay. So, this, once again, this is involving the annotation, but you see primal variable you see the dual variable. Obviously, if you have two constraints here, you have two dual variables. Okay. If you have three variables over there, you have three constraints. Okay. So, it's going to these nice matching. It's like you take it your head. You flip it and you get the dual. Okay, so that's what you get. So, this is even more explicit when you take matrix notation, okay. Remember the last lecture I told you, we can view all these things in terms of matrices. This is what you see here as well, okay. So this is the primal. You see the primal variable there, y, you know, x1, x2, x3, okay. So, you'll see the dual variable there, y1 y2. These are the coefficient of the objective function for the primal. Where do you find these guys? Well, these guys will be here, right? So, they will be the right end side of the constraints in the dual, okay? Now, you see, basically, the matrix here, okay? The matrix, the inequality is basically the big matrix A, okay? You see the primal, you see the primal variable over there, you see the, the the, sorry, yeah the primal variables here. And what you see here is the right end site, okay? So, these right end side, no is of usely going to the objective function here, okay? And you see this matrix here is going to be essen, is going to be here, okay? So, the only, you know, here, the column and the row comes from the fact that here we are multiplying this matrix by these variables. And here, we are multiplying the, the you we are multiplying, we are multiplying, you are taking the dual variables and multiplying the matrix. We just switch the side, okay? So, this is, once again, in matrix from primal dual, the objective function become the right end sign, okay. The right end sign becomes the objective coefficients, and then you have the the matrix that you basically switch around, okay. So, that's duality. Now, why is this interesting in any sense, okay? This is the beautiful property, right? You see the primal, you see the dual. And the basic result that you have is that if the primal is a feasible solution and for an optimal solution. Okay. Then the dual also have a feasible solution and it has an optimal solution with the same cost. Okay. So, in a sense, these two problem have the, have optimal solution which have the same cost. Okay. Now, you see, you, you don't know really why this is useful, but I will show you next time. Right? So, but, but this is, this is the basic result. Okay, the basic result is that the opt, the optimal value for this one is going to be the optimal value for the other one. And I'm just going to prove it to you. Okay. I'm going to say, this x and y so the first thing that I'm going to show you is that the cost of the primal, okay? Is always higher than the cost of the dual. Okay? So, think about it. The primal we are minimizing. So, we start very, very high and then we go down, down, down, down, down. Okay? The dual is maximizing. We start, we're going to start at the bottom and go up, up, up, up, up. And what I'm basically show is, the, the first thing that I'm going to show you is that the primal is going down. The dual is going up, but the dual is always lower than the primal, okay? So, they do this, okay? They kind of crossover, okay? So, and this is, this is the proof which is very simple. It's very simple algebraic manipulation of these things, okay? So, let x and pi okay, be solution. and there is a reason why I am using pi, you'll see later on, right? So, but, but x and pi are feasible solution to the primal and the dual, respectively. Okay? Now, I look at the costs, cx, do you see this? Okay? So, this is the cost of the primal. Okay? And now, I'm going to use the fact that, you know, these guys have to satisfy some conditions, right? So, essentially what I know. Look at this thing here. So, I know that c has to be greater than A, no, y times A. Okay? And y is the feasible solution to the, to the dual. Right? So, here I have pi which is a solution to the, to the dual, okay? So, I know that c has to be greater than what? Than pi times A. And that's what you see there, okay? So, you see that cx has to be greater than pi Ax, okay? So, and I'm just using the fact that this has to be true for a feasible solution to the dual, right? And so, the last thing I need to do is use this fact here which is the feasible solution to the primal, I know that any solution x which is visible to the primal, you know is to satisfy Ax is greater than b. Okay? Now, I have this beautiful Ax over there. I can replace it by b and what do I get? I get pi b. Okay? Now, pi b is the objective functions of what? Of the dual. Right? So, that's the value of that, that's the value of that objective value of pi, of, of feasible solution pi. I have c x over there. Okay? Which you see here, which is the value of the solution of the primal. And then, I have all of these relationship that, you know, the objective value of the primal is always greater, okay, than the solution of the dual. So, they do this. Okay? So, that's the first result. The primal objective function is always greater than the dual objective function. Okay? So, obviously know, obviously, since the primal is a feasible solution, the dual cannot be unbonded. Once again, you know, we're going down with the primal. The dual cannot just go like this, right? So, it has to be bonded, okay? So, that's the second fact that I have, okay? And then, the third fact, okay. While the, while the, there will be two more facts. The third fact is going to be that all the optimality of the primal, I have a feasible solution to the dual. Okay? And this is this pi, of course, right. This simplex multipliers. Okay, why? Because I know that optimality in the primal, okay. This linear program, I have to satisfy that all these costs, you know, in the basic feasible solution has to be non-negative. Okay. These costs are basically re-expressed in this particular fashion. I've shown you that last time, okay. So, I know that c minus pi A has to be greater than 0, okay, which basically means that c has to be greater than pi A, okay? So, which is essentially the condition that we shown, that we have seen, that we have seen here. Right? So, this is the condition on the dual. That's a feasible solution to the dual. So, what do I know? I know that the simplex multiplier pi have to be a feasible solution to the dual. So, if I solve the primal, I have already a feasible solution to the dual, okay? So, now, I can actually show you, with these two facts, I can actually show you that the primal and the dual optimality have the same cost, right? So, I take an optimal solution to the primal x star, okay? And then, obviously yielding all of the things that we have seen in the previous lectures. I know that, you know, the value of that particular that particular optimal solution has to be given in terms of a basis, and associating this value to the basic variables, all the non-basic variables being 0. So, I know that x star has to be A B to, you know, the, the, the matrix for the basis, minus 1, I have to invert it, times b, which is the right-hand side. When I state the system. Okay? Now, I told you that the dual, has a feasible solution which is obtained by the simplex multiplier, that this is what, that this is expressing. And the simplex multipliers are simply expressed as cB times AB minus 1. Okay. And therefore, I know can come to this interesting derivation. So the, the objective value of the dual is this value there that you see, right? So, y star b, okay? Now, y star, I just gave you the formula there. It's cB AB minus 1. So, I have cB AB minus 1 stein b, but AB minus 1 times b is, what is the value of the, you know, the, the basic variables in the primal? So, I get here cBx star. So, what I get here is that this feasible solution of the dual is exactly the same cost as the optimal solution to the, to the primal. So, I have one feasible solution to the dual, same solution as the primal. I know that there are no solution of the dual that can be better, so I fit, what you see here is that these two, the primal is going down. The dual is going up, and then the meet at this optimal point. Okay. So, that's, that's basically the result. So, you will have the primal, you have the dual. These two programs are closely related right. To derive one from the other. And then, you know they have the same objective value of optimality, okay. So, I've shown you the primary and dual, dual relationship in, in the general in the, in the, in the restricted cases. So, this is the general formula on how to obtain the dual from the primal, in full generality, okay? So, in full generality, I'm doing two things. I'm allowing to have equations not only inequalities. And I'm allowing some variables to be not, you know, non-negative. They can take any arbitrary real value. Okay? And once you do that, okay, so you can derive the dual in essentially the same way. There will be some constraints which are equalities, some variables which are constrained to be non-negative, and some which are not. How do we get them? Well, look at this thing. You know. Every equality will have a dual variable which is associated with it. And that dual variable here is not going to be constrained. It's non, it's, it doesn't have to be non-negative. Okay? If you have an inequality that's these types of constraints, they will obviously have a dual variable, and that dual variable is to be non-negative, that's what I've shown you before. Right? And, the same thing happens for, you know, the, the primal variables. If a primal variable is non-negative, you know that the constraint we are deriving, like I've shown you before, has to be an inequality. And we know that if the variable is non-constraints, we will get an equality. Okay? So, very simple, equalities, no constraints. Inequalities, non-negativity constraints. Okay? So, that's the general form of the dual. Okay? Now, there are some very interesting properties for this dual and primal. Okay? So, you know, this is basically telling you that the friend of my friend is my friend. Okay? So, the dual, the dual of the dual is the primal. Okay. So, if you take the dual, and then reapply the dual of that dual, you get back to the primal. You know, that's a good property to have, otherwise it would be crazy. Right? But this is essentially saying that if you take the dual of the dual of the primal, you get the primal back. Okay? Now, the other thing that you have to understand is, you know what is the relationship if these things are feasible, unfeasible, unbounded and so on, okay. So, we already know that if the primal is feasible, okay, the primal is feasible then the dual has to be feasible. If we have a solution, the other guy can get back to that part of the solution. Okay? Now, what if the primer is unbounded, okay? So, what, you know, this is a picture which I've been, you know, telling you, okay? So, when they are both feasible, when, you know, they are both bounded and feasible, okay? So, you have the primer going down, you have the dual going up, and they meet. You know, it's like in Pac-Man when they go to the next level. Oh, they meet. Okay. So, this is what you have here. Okay. Now, if, if the primal is unbounded, what is happening? This guy's going down, down, down, down, down, down forever. Right. And we know that the cost of this guy has to be always greater. The cost of the primal is always to be greater than the cost of the dual. Okay. Therefore, the dual cannot go up. You know, it can go up, it, it, it cannot, you cannot have a fixed cost for this dual because, otherwise, the other one is, is, you know, going through it. And therefore, the only possibility for the dual is where it, it has to be infeasible, right? So, we know that this guy is, is, this guy is in, is, is the primal is unbounded, the dual has to be feasible, okay. Now, we have the last column that we need to consider, which is what about if the primal is infeasible? Okay? If the primal is infeasible, can the dual be infeasible? And can the, can the dual be unbounded? Okay? So, by analogy to the, you know, to the previous you can already, you know, reach one of the conclusions. Okay? But this is, this is a very simple example with, with, which expresses the possibility. This is the primal, I minimize, okay x1. Can I, cannot be simpler than that, okay? And two constraints okay? These two constraints are very interesting, because, you know, you look at the left-hand side here. And the other left-hand side that shows the negation of each other. And they both have to be greater than 1. So, this is clearing infeasible. Right? So, this is the dual, okay? And what do you see in the dual? You see, you know, this variables here are not, the variables x1 and x2 are not constraint. So, you get equations inside a dual. and therefore, you, you see some very nice equations with the right-hand side. Okay? It's the same for this, the left hand side for these two things are the same, but the constant, the constant here, is different. Okay? So, once again, it's feas, it's infeasible. So, if the primal is infeasible, we know that the dual can be infeasible. Okay? And then, there is the other case. It can also be the case that the primal is infeasible, but the dual is unbounded. And the only thing that I did here, I kept essentially the same constraints on the top, so it's still infeasible. But I added more constraints saying that the variables have to be non-negative. When the variables are non-negative, remember the impact of that is changing equations into inequalities. And that's what you see there. So now, essentially you have these two guys here, which have the same left hand side, okay. But now they are smaller or equal to 1 and 0, so you don't force them to be feasible anymore. Okay. So, these constraint are easy to satisfy, right. So, you make y a little bigger than, than, than y2, a little bit bigger than y1, okay. And these constraints are always going to satisfied. And therefore, what I can do now is take this objective function and drive it up, as much as I can. Right? I'm, I'm basically getting a value for y1, getting an even greater value for y2, and these values can go up, up, up, up, up, up, up. And so, it's unbounded. Okay. So, once the primal is feasible, okay. It's infeasible. The dual can be infeasible or the dual can be unbounded. So, you know, the relationship which is primal and dual now. Okay. Now, there is another thing which is very nice. Right? So, one of the things about the theory of NP completeness is I told you, okay. These problems are hard, we have to push the exponential, okay. That's what we have been doing all along, okay. But the nice thing about this problems is that we can actually show that if you give me a solution, I can check if it's feasible or not. Okay. Very easy, you know, typically low polynomial type, okay. But, but proving that something is optimal is kind of tough, right. So, I don't have that, okay. Now, in linear programming, can you actually provide me with a certificate of optimality? And the answer is yes. This is nice. In, in linear programming, I could show something is feasible. But if I give you, if I give you a solution, you can check quickly if it's satisfy, you know, if it's feasible or not. But here, you can also convince me that you can act, that you actually have found an optimal solution. How would you do that? Think about it. How would you actually convince me that you have an optimal solution? Well, this is what you would do, right. So, you would say, oh, but you know, we have primal and you have a dual you know, okay. So, von Neumann and [UNKNOWN] and some people at Princeton, Ken Tucker and Dale, if i remember correctly, actually proved this beautiful relation between these guys. These, these primal and the dual. So now, and so you believe these guys. So now, you can give me an x star which satisfy, you know, the constraints, the constraints of the primal. You can give me a y star which satisfies the constraints of the dual, and you can show me that the cost of these two things are the same. If this is the case, you know, I know, then, that, you know, x star is an optimal solution to the primal. And of course, that y star is an optimal solution to the dual. So, you can actually give me something that I can check very quickly, if this is actually an optimal solution. And this is one of the beauty of linear programming. That's the gap between NP completeness and polynomial time. Okay? So. We have seen the, you know, we have seen the basic introduction to the dual here, which is beautiful right? You have this primal and the dual, right? And they have the same objective value at optimality, assuming that there is a feasible solution for both. For, for, you know, for one of them because then they are solutions for both of them. They have this beautiful relationship, okay? And what I'm going to do next time is to show you, you know, how we act, what this actually means in practice, and what does it actually, what is, how do we actually get to these things, and why does it make any sense, okay? Thank you very much.