0:00

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.

Â