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.