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.