1
00:00:00,210 --> 00:00:03,660
Okay, so this is Discrete Optimization, 
Linear Programming, Part V. 

2
00:00:03,660 --> 00:00:07,180
So, what we are going to today is some 
really, really beautiful thing. 

3
00:00:07,180 --> 00:00:09,210
Okay, so we're going to see duality. 
Okay? 

4
00:00:09,210 --> 00:00:13,980
And at a higher level, okay, so you can 
think of, we are looking at the same 

5
00:00:13,980 --> 00:00:17,010
thing but from two different angles. 
And we can see some very, very different 

6
00:00:17,010 --> 00:00:18,890
things. 
So, most of you have probably seen this 

7
00:00:18,890 --> 00:00:23,280
picture where you can see this beautiful 
young lady and this old ugly woman. 

8
00:00:23,280 --> 00:00:25,350
Right? 
And so, this is duality. 

9
00:00:25,350 --> 00:00:27,110
Right? 
So, this is going to be looking at the 

10
00:00:27,110 --> 00:00:32,060
same thing, but from different angle. 
And to motivate you to this lecture, I 

11
00:00:32,060 --> 00:00:34,975
want to tell you the story of, of, of 
[UNKNOWN] and [UNKNOWN]. 

12
00:00:34,975 --> 00:00:40,221
So, so, so when [UNKNOWN] invented linear 
programming, he went to see John von 

13
00:00:40,221 --> 00:00:42,910
Neumann. 
So, this genius mathematician and 

14
00:00:42,910 --> 00:00:46,780
computer scientist with this encyclopedic 
knowledge of everything, right? 

15
00:00:46,780 --> 00:00:51,250
So, he went to see him and start 
explaining the, the, the linear 

16
00:00:51,250 --> 00:00:53,458
programming to von Neumann. 
And von Neumann, typically being a 

17
00:00:53,458 --> 00:00:58,390
patient, you know, man, was kind of, you 
know, impatient that day. 

18
00:00:58,390 --> 00:01:00,470
And said, you know, get to the point, get 
to the point. 

19
00:01:00,470 --> 00:01:03,370
And so then, [UNKNOWN] say, oh, he wants 
me to get to the point. 

20
00:01:03,370 --> 00:01:06,660
And so, he started going fast. 
And then, von Neumann stopped him, and 

21
00:01:06,660 --> 00:01:09,230
started there he's writing all the 
results. 

22
00:01:09,230 --> 00:01:11,140
And the things I'm going to show you 
today. 

23
00:01:11,140 --> 00:01:14,900
Okay? 
And [UNKNOWN] was like, what's happening? 

24
00:01:14,900 --> 00:01:16,090
You know, yeah. 
It's just deriving all this guy is just 

25
00:01:16,090 --> 00:01:19,750
deriving all this on the fly. 
But von Neumann was also a very kind 

26
00:01:19,750 --> 00:01:22,310
person. 
And he said at the end, I just don't want 

27
00:01:22,310 --> 00:01:24,640
you to think that I'm deriving this on 
the fly, right. 

28
00:01:24,640 --> 00:01:29,080
So, this is very, very similar to 
something I'm doing in game theory, okay. 

29
00:01:29,080 --> 00:01:33,070
And therefore, you know, I'm postulating 
that these two things are the same, okay. 

30
00:01:33,070 --> 00:01:36,030
And they were, they were, they are 
essentially the same, okay. 

31
00:01:36,030 --> 00:01:38,850
And so, that's what duality, that's what 
I'm going to show you today. 

32
00:01:38,850 --> 00:01:42,160
I'm going to show you these results on 
duality theory which are basically 

33
00:01:42,160 --> 00:01:44,550
looking at linear programming in two 
different ways. 

34
00:01:44,550 --> 00:01:47,670
Okay? 
So, so what I'm going to show you today 

35
00:01:47,670 --> 00:01:51,640
is basically two linear programs. 
The primal which is essentially what we 

36
00:01:51,640 --> 00:01:53,320
have been seeing all along. 
Okay? 

37
00:01:53,320 --> 00:01:58,325
Which is minimizing this objective 
function c x subject to inequality. 

38
00:01:58,325 --> 00:02:02,220
Ax greater or equal to b with all the 
variables being non-negative, okay. 

39
00:02:02,220 --> 00:02:06,990
And then, I'm going to talk about another 
linear program, which we're going to call 

40
00:02:06,990 --> 00:02:10,580
the dual. 
And that dual is going to maximize, okay, 

41
00:02:10,580 --> 00:02:14,150
an objective function y b, y are the 
variables here, okay. 

42
00:02:14,150 --> 00:02:16,360
So, y are going to be called the dual 
variables. 

43
00:02:16,360 --> 00:02:18,400
The x, I called the primal variables. 
So, okay. 

44
00:02:18,400 --> 00:02:22,080
Primal, dual, okay. 
And then, we have also a set of linear 

45
00:02:22,080 --> 00:02:25,800
inequality, okay? 
y A is smaller or equal to c, instead of 

46
00:02:25,800 --> 00:02:27,590
being greater or equal, it's going to be 
smaller or equal. 

47
00:02:27,590 --> 00:02:29,610
Same matrix, okay? 
Different variables, okay? 

48
00:02:29,610 --> 00:02:33,210
Primal variables, dual variables. 
And then, the y's are also going to be, 

49
00:02:33,210 --> 00:02:35,240
you know, non-negative. 
Okay? 

50
00:02:35,240 --> 00:02:38,560
So, let me show you an example here, so 
that you can see this on the, on the read 

51
00:02:38,560 --> 00:02:41,250
example. 
This is the primal, this is the dual, 

52
00:02:41,250 --> 00:02:44,082
right? 
The variable here, the primal variable, 

53
00:02:44,082 --> 00:02:47,356
x1, x2, x3, okay? 
You see you see the coefficient, 3, 2, 4, 

54
00:02:47,356 --> 00:02:49,560
okay? 
Then, you see these two constraints, 

55
00:02:49,560 --> 00:02:52,175
okay? 
And then, you see the right hand side. 

56
00:02:52,175 --> 00:02:55,003
Okay? 
in this particular case, 2 and 5. 

57
00:02:55,003 --> 00:02:55,930
Okay? 
2 and 5. 

58
00:02:55,930 --> 00:02:57,720
Okay? 
This is a dual. 

59
00:02:57,720 --> 00:03:00,400
Okay? 
Instead of minimizing, we are maximizing. 

60
00:03:00,400 --> 00:03:02,400
We have two variables, the dual 
variables. 

61
00:03:02,400 --> 00:03:04,440
Okay? 
And then, we have three inequalities 

62
00:03:04,440 --> 00:03:05,010
here. 
Okay? 

63
00:03:05,010 --> 00:03:08,794
I'm, I'm remove, you know, I'm not 
showing the non-negative constraints 

64
00:03:08,794 --> 00:03:09,340
here. 
Okay? 

65
00:03:09,340 --> 00:03:10,650
So, they are implicit. 
Okay? 

66
00:03:10,650 --> 00:03:13,160
So, primal dual, you see these things. 
Okay? 

67
00:03:13,160 --> 00:03:15,800
No, these two guys have a very strong 
relationship. 

68
00:03:15,800 --> 00:03:18,310
So, I'm going to show you how we obtain 
the dual. 

69
00:03:18,310 --> 00:03:20,950
Right? 
So, the first thing we do, is that we 

70
00:03:20,950 --> 00:03:24,670
introduce these dual variables, y1 and 
y2. 

71
00:03:24,670 --> 00:03:27,504
Okay? 
So, in a sense, with every constraints 

72
00:03:27,504 --> 00:03:30,760
now, we are associating a dual variable. 
Okay? 

73
00:03:30,760 --> 00:03:33,780
So, this is y1 and y2. 
And of course, in the dual is only 

74
00:03:33,780 --> 00:03:37,709
expressed in terms of y1 and y2. 
The key point here is to remember these 2 

75
00:03:37,709 --> 00:03:41,090
variables are associated. 
There is as many dual variables as there 

76
00:03:41,090 --> 00:03:45,210
are constraints in the primal. 
Okay, now, how do we obtain the 

77
00:03:45,210 --> 00:03:47,990
objective? 
Right to we transform the min into a max, 

78
00:03:47,990 --> 00:03:51,230
but the coefficients of the variables, 
where do they come from? 

79
00:03:51,230 --> 00:03:56,490
Well, they come from the right end side 
of the inequalities in the primal, okay? 

80
00:03:56,490 --> 00:04:00,980
So, you saw 2 and 5 here, okay? 
You see 2 and 5 here, okay. 

81
00:04:00,980 --> 00:04:07,150
And you see now that the objective 
function is maximizing 2y1 plus 5y2, 

82
00:04:07,150 --> 00:04:09,360
okay? 
So, in a sense you take this, you flip 

83
00:04:09,360 --> 00:04:13,340
it, and you get the objective functions 
of the dual, okay? 

84
00:04:13,340 --> 00:04:16,730
One thing stopped, okay? 
Now, how do we get the right hand side of 

85
00:04:16,730 --> 00:04:18,840
the dual? 
Well, you take the objective function, 

86
00:04:18,840 --> 00:04:21,240
right? 
So, the objective function of the primal 

87
00:04:21,240 --> 00:04:24,080
is what? 
3, 2, 4, is in term of the coefficient. 

88
00:04:24,080 --> 00:04:29,490
And now, you see 3, 2, and 4 as the right 
end side of the dual, right? 

89
00:04:29,490 --> 00:04:33,380
So, in a sense, the right hand side of 
the primal become the objective function 

90
00:04:33,380 --> 00:04:37,100
of the dual. 
The objective, you know the objective 

91
00:04:37,100 --> 00:04:42,475
coefficients of the primer become the 
right end side of the dual. 

92
00:04:42,475 --> 00:04:45,115
Okay? 
And now, the trick is almost played, 

93
00:04:45,115 --> 00:04:47,460
right? 
So, the only thing that we need to do is 

94
00:04:47,460 --> 00:04:51,260
to look at the, the matrix that you see 
over there, okay? 

95
00:04:51,260 --> 00:04:55,870
For the constraints, okay? 
So, so we look at the coefficients of, of 

96
00:04:55,870 --> 00:04:59,470
the first column here, do you know? 
So, we see y1, y2. 

97
00:04:59,470 --> 00:05:03,139
We take a column here, the coefficients 
for x1, okay? 

98
00:05:03,139 --> 00:05:07,230
They are 2 and 2, and what you get here 
is essentially constraints. 

99
00:05:07,230 --> 00:05:11,560
Okay? 
It's going to be 2y1 plus 2y2, okay. 

100
00:05:11,560 --> 00:05:15,080
Smaller or equal to the value that we had 
already computed, which is 3. 

101
00:05:15,080 --> 00:05:17,100
Okay. 
How do we obtain the second constraint? 

102
00:05:17,100 --> 00:05:22,490
Well, you take the, you take the column 
associating, associated with x2 over 

103
00:05:22,490 --> 00:05:22,890
there. 
Okay. 

104
00:05:22,890 --> 00:05:26,690
The coefficient for x2 are what? 
1 and minus 1. 

105
00:05:26,690 --> 00:05:30,620
And therefore, these are the coefficients 
of the dual variable in the second 

106
00:05:30,620 --> 00:05:35,860
constraint. 
1, for x, y y1, and minus 1 for y2, and 

107
00:05:35,860 --> 00:05:38,720
you get the third constraint. 
the second constraint. 

108
00:05:38,720 --> 00:05:41,620
The third constraint is easy right? 
There is only one coefficient, and that 

109
00:05:41,620 --> 00:05:45,090
is the coefficient for the dual, for the 
dual variable y2. 

110
00:05:45,090 --> 00:05:49,130
And so, what you see here is, that the 
last constraint is simply y2 is smaller 

111
00:05:49,130 --> 00:05:51,070
or equal to 4. 
Okay? 

112
00:05:51,070 --> 00:05:54,458
So, in a sense, it's beautiful, right, 
the objective function becomes the right 

113
00:05:54,458 --> 00:05:57,001
end side. 
The right end side of the primal become 

114
00:05:57,001 --> 00:06:02,030
the, the objective functions of the dual. 
And then, this matrix, the column here 

115
00:06:02,030 --> 00:06:07,370
becomes the row, and the, the column, you 
know, of the primal, become the row of 

116
00:06:07,370 --> 00:06:08,250
the dual. 
Okay? 

117
00:06:08,250 --> 00:06:12,060
And that's how you express this dual. 
Okay. 

118
00:06:12,060 --> 00:06:16,060
So, this, once again, this is involving 
the annotation, but you see primal 

119
00:06:16,060 --> 00:06:19,520
variable you see the dual variable. 
Obviously, if you have two constraints 

120
00:06:19,520 --> 00:06:21,630
here, you have two dual variables. 
Okay. 

121
00:06:21,630 --> 00:06:25,210
If you have three variables over there, 
you have three constraints. 

122
00:06:25,210 --> 00:06:27,460
Okay. 
So, it's going to these nice matching. 

123
00:06:27,460 --> 00:06:31,215
It's like you take it your head. 
You flip it and you get the dual. 

124
00:06:31,215 --> 00:06:35,430
Okay, so that's what you get. 
So, this is even more explicit when you 

125
00:06:35,430 --> 00:06:39,060
take matrix notation, okay. 
Remember the last lecture I told you, we 

126
00:06:39,060 --> 00:06:41,580
can view all these things in terms of 
matrices. 

127
00:06:41,580 --> 00:06:44,620
This is what you see here as well, okay. 
So this is the primal. 

128
00:06:44,620 --> 00:06:48,250
You see the primal variable there, y, you 
know, x1, x2, x3, okay. 

129
00:06:48,250 --> 00:06:51,180
So, you'll see the dual variable there, 
y1 y2. 

130
00:06:51,180 --> 00:06:55,510
These are the coefficient of the 
objective function for the primal. 

131
00:06:55,510 --> 00:06:58,960
Where do you find these guys? 
Well, these guys will be here, right? 

132
00:06:58,960 --> 00:07:03,570
So, they will be the right end side of 
the constraints in the dual, okay? 

133
00:07:03,570 --> 00:07:05,940
Now, you see, basically, the matrix here, 
okay? 

134
00:07:05,940 --> 00:07:09,550
The matrix, the inequality is basically 
the big matrix A, okay? 

135
00:07:09,550 --> 00:07:13,410
You see the primal, you see the primal 
variable over there, you see the, the 

136
00:07:13,410 --> 00:07:15,290
the, sorry, yeah the primal variables 
here. 

137
00:07:15,290 --> 00:07:17,860
And what you see here is the right end 
site, okay? 

138
00:07:17,860 --> 00:07:22,760
So, these right end side, no is of usely 
going to the objective function here, 

139
00:07:22,760 --> 00:07:25,620
okay? 
And you see this matrix here is going to 

140
00:07:25,620 --> 00:07:29,210
be essen, is going to be here, okay? 
So, the only, you know, here, the column 

141
00:07:29,210 --> 00:07:32,540
and the row comes from the fact that here 
we are multiplying this matrix by these 

142
00:07:32,540 --> 00:07:34,920
variables. 
And here, we are multiplying the, the you 

143
00:07:34,920 --> 00:07:38,150
we are multiplying, we are multiplying, 
you are taking the dual variables and 

144
00:07:38,150 --> 00:07:41,130
multiplying the matrix. 
We just switch the side, okay? 

145
00:07:41,130 --> 00:07:45,702
So, this is, once again, in matrix from 
primal dual, the objective function 

146
00:07:45,702 --> 00:07:49,870
become the right end sign, okay. 
The right end sign becomes the objective 

147
00:07:49,870 --> 00:07:53,516
coefficients, and then you have the the 
matrix that you basically switch around, 

148
00:07:53,516 --> 00:07:55,092
okay. 
So, that's duality. 

149
00:07:55,092 --> 00:07:58,280
Now, why is this interesting in any 
sense, okay? 

150
00:07:58,280 --> 00:08:02,550
This is the beautiful property, right? 
You see the primal, you see the dual. 

151
00:08:02,550 --> 00:08:07,350
And the basic result that you have is 
that if the primal is a feasible solution 

152
00:08:07,350 --> 00:08:09,120
and for an optimal solution. 
Okay. 

153
00:08:09,120 --> 00:08:13,630
Then the dual also have a feasible 
solution and it has an optimal solution 

154
00:08:13,630 --> 00:08:15,620
with the same cost. 
Okay. 

155
00:08:15,620 --> 00:08:20,430
So, in a sense, these two problem have 
the, have optimal solution which have the 

156
00:08:20,430 --> 00:08:21,602
same cost. 
Okay. 

157
00:08:21,602 --> 00:08:25,310
Now, you see, you, you don't know really 
why this is useful, but I will show you 

158
00:08:25,310 --> 00:08:25,950
next time. 
Right? 

159
00:08:25,950 --> 00:08:28,320
So, but, but this is, this is the basic 
result. 

160
00:08:28,320 --> 00:08:31,950
Okay, the basic result is that the opt, 
the optimal value for this one is 

161
00:08:31,950 --> 00:08:33,520
going to be the optimal value for the 
other one. 

162
00:08:33,520 --> 00:08:35,170
And I'm just going to prove it to you. 
Okay. 

163
00:08:35,170 --> 00:08:39,870
I'm going to say, this x and y so the 
first thing that I'm going to show you is 

164
00:08:39,870 --> 00:08:45,270
that the cost of the primal, okay? 
Is always higher than the cost of the 

165
00:08:45,270 --> 00:08:46,100
dual. 
Okay? 

166
00:08:46,100 --> 00:08:48,260
So, think about it. 
The primal we are minimizing. 

167
00:08:48,260 --> 00:08:51,260
So, we start very, very high and then we 
go down, down, down, down, down. 

168
00:08:51,260 --> 00:08:53,410
Okay? 
The dual is maximizing. 

169
00:08:53,410 --> 00:08:56,640
We start, we're going to start at the 
bottom and go up, up, up, up, up. 

170
00:08:56,640 --> 00:08:59,870
And what I'm basically show is, the, the 
first thing that I'm going to show you is 

171
00:08:59,870 --> 00:09:03,820
that the primal is going down. 
The dual is going up, but the dual is 

172
00:09:03,820 --> 00:09:08,590
always lower than the primal, okay? 
So, they do this, okay? 

173
00:09:08,590 --> 00:09:11,470
They kind of crossover, okay? 
So, and this is, this is the proof which 

174
00:09:11,470 --> 00:09:14,270
is very simple. 
It's very simple algebraic manipulation 

175
00:09:14,270 --> 00:09:18,865
of these things, okay? 
So, let x and pi okay, be solution. 

176
00:09:18,865 --> 00:09:22,450
and there is a reason why I am using pi, 
you'll see later on, right? 

177
00:09:22,450 --> 00:09:27,059
So, but, but x and pi are feasible 
solution to the primal and the dual, 

178
00:09:27,059 --> 00:09:28,580
respectively. 
Okay? 

179
00:09:28,580 --> 00:09:31,524
Now, I look at the costs, cx, do you see 
this? 

180
00:09:31,524 --> 00:09:33,630
Okay? 
So, this is the cost of the primal. 

181
00:09:33,630 --> 00:09:36,130
Okay? 
And now, I'm going to use the fact that, 

182
00:09:36,130 --> 00:09:39,180
you know, these guys have to satisfy some 
conditions, right? 

183
00:09:39,180 --> 00:09:41,780
So, essentially what I know. 
Look at this thing here. 

184
00:09:41,780 --> 00:09:47,280
So, I know that c has to be greater than 
A, no, y times A. 

185
00:09:47,280 --> 00:09:49,400
Okay? 
And y is the feasible solution to the, to 

186
00:09:49,400 --> 00:09:50,410
the dual. 
Right? 

187
00:09:50,410 --> 00:09:53,930
So, here I have pi which is a solution to 
the, to the dual, okay? 

188
00:09:53,930 --> 00:09:56,980
So, I know that c has to be greater than 
what? 

189
00:09:56,980 --> 00:09:59,850
Than pi times A. 
And that's what you see there, okay? 

190
00:09:59,850 --> 00:10:04,890
So, you see that cx has to be greater 
than pi Ax, okay? 

191
00:10:04,890 --> 00:10:10,106
So, and I'm just using the fact that this 
has to be true for a feasible solution to 

192
00:10:10,106 --> 00:10:12,620
the dual, right? 
And so, the last thing I need to do is 

193
00:10:12,620 --> 00:10:16,500
use this fact here which is the feasible 
solution to the primal, I know that any 

194
00:10:16,500 --> 00:10:20,380
solution x which is visible to the 
primal, you know is to satisfy Ax is 

195
00:10:20,380 --> 00:10:21,710
greater than b. 
Okay? 

196
00:10:21,710 --> 00:10:26,220
Now, I have this beautiful Ax over there. 
I can replace it by b and what do I get? 

197
00:10:26,220 --> 00:10:27,829
I get pi b. 
Okay? 

198
00:10:27,829 --> 00:10:30,870
Now, pi b is the objective functions of 
what? 

199
00:10:30,870 --> 00:10:32,250
Of the dual. 
Right? 

200
00:10:32,250 --> 00:10:36,880
So, that's the value of that, that's the 
value of that objective value of pi, of, 

201
00:10:36,880 --> 00:10:39,534
of feasible solution pi. 
I have c x over there. 

202
00:10:39,534 --> 00:10:42,930
Okay? 
Which you see here, which is the value of 

203
00:10:42,930 --> 00:10:45,751
the solution of the primal. 
And then, I have all of these 

204
00:10:45,751 --> 00:10:49,460
relationship that, you know, the 
objective value of the primal is always 

205
00:10:49,460 --> 00:10:51,530
greater, okay, than the solution of the 
dual. 

206
00:10:51,530 --> 00:10:53,310
So, they do this. 
Okay? 

207
00:10:53,310 --> 00:10:56,420
So, that's the first result. 
The primal objective function is always 

208
00:10:56,420 --> 00:10:59,040
greater than the dual objective function. 
Okay? 

209
00:10:59,040 --> 00:11:03,640
So, obviously know, obviously, since the 
primal is a feasible solution, the dual 

210
00:11:03,640 --> 00:11:06,630
cannot be unbonded. 
Once again, you know, we're going down 

211
00:11:06,630 --> 00:11:09,430
with the primal. 
The dual cannot just go like this, right? 

212
00:11:09,430 --> 00:11:12,900
So, it has to be bonded, okay? 
So, that's the second fact that I have, 

213
00:11:12,900 --> 00:11:15,540
okay? 
And then, the third fact, okay. 

214
00:11:15,540 --> 00:11:17,710
While the, while the, there will be two 
more facts. 

215
00:11:17,710 --> 00:11:23,240
The third fact is going to be that all 
the optimality of the primal, I have a 

216
00:11:23,240 --> 00:11:25,430
feasible solution to the dual. 
Okay? 

217
00:11:25,430 --> 00:11:28,460
And this is this pi, of course, right. 
This simplex multipliers. 

218
00:11:28,460 --> 00:11:31,739
Okay, why? 
Because I know that optimality in the 

219
00:11:31,739 --> 00:11:35,250
primal, okay. 
This linear program, I have to satisfy 

220
00:11:35,250 --> 00:11:38,475
that all these costs, you know, in the 
basic feasible solution has to be 

221
00:11:38,475 --> 00:11:39,340
non-negative. 
Okay. 

222
00:11:39,340 --> 00:11:42,160
These costs are basically re-expressed in 
this particular fashion. 

223
00:11:42,160 --> 00:11:47,590
I've shown you that last time, okay. 
So, I know that c minus pi A has to be 

224
00:11:47,590 --> 00:11:53,005
greater than 0, okay, which basically 
means that c has to be greater than pi A, 

225
00:11:53,005 --> 00:11:55,350
okay? 
So, which is essentially the condition 

226
00:11:55,350 --> 00:11:58,500
that we shown, that we have seen, that we 
have seen here. 

227
00:11:58,500 --> 00:12:00,760
Right? 
So, this is the condition on the dual. 

228
00:12:00,760 --> 00:12:03,650
That's a feasible solution to the dual. 
So, what do I know? 

229
00:12:03,650 --> 00:12:09,560
I know that the simplex multiplier pi 
have to be a feasible solution to the 

230
00:12:09,560 --> 00:12:12,520
dual. 
So, if I solve the primal, I have already 

231
00:12:12,520 --> 00:12:17,220
a feasible solution to the dual, okay? 
So, now, I can actually show you, with 

232
00:12:17,220 --> 00:12:22,210
these two facts, I can actually show you 
that the primal and the dual optimality 

233
00:12:22,210 --> 00:12:25,620
have the same cost, right? 
So, I take an optimal solution to the 

234
00:12:25,620 --> 00:12:29,640
primal x star, okay? 
And then, obviously yielding all of the 

235
00:12:29,640 --> 00:12:32,080
things that we have seen in the previous 
lectures. 

236
00:12:32,080 --> 00:12:37,580
I know that, you know, the value of that 
particular that particular optimal 

237
00:12:37,580 --> 00:12:43,300
solution has to be given in terms of a 
basis, and associating this value to the 

238
00:12:43,300 --> 00:12:45,290
basic variables, all the non-basic 
variables being 0. 

239
00:12:45,290 --> 00:12:51,490
So, I know that x star has to be A B to, 
you know, the, the, the matrix for the 

240
00:12:51,490 --> 00:12:55,540
basis, minus 1, I have to invert it, 
times b, which is the right-hand side. 

241
00:12:55,540 --> 00:12:57,390
When I state the system. 
Okay? 

242
00:12:57,390 --> 00:13:01,210
Now, I told you that the dual, has a 
feasible solution which is obtained by 

243
00:13:01,210 --> 00:13:04,400
the simplex multiplier, that this is 
what, that this is expressing. 

244
00:13:04,400 --> 00:13:09,468
And the simplex multipliers are simply 
expressed as cB times AB minus 1. 

245
00:13:09,468 --> 00:13:13,410
Okay. 
And therefore, I know can come to this 

246
00:13:13,410 --> 00:13:18,510
interesting derivation. 
So the, the objective value of the dual 

247
00:13:18,510 --> 00:13:22,640
is this value there that you see, right? 
So, y star b, okay? 

248
00:13:22,640 --> 00:13:25,030
Now, y star, I just gave you the formula 
there. 

249
00:13:25,030 --> 00:13:29,550
It's cB AB minus 1. 
So, I have cB AB minus 1 stein b, but AB 

250
00:13:29,550 --> 00:13:35,160
minus 1 times b is, what is the value of 
the, you know, the, the basic variables 

251
00:13:35,160 --> 00:13:38,520
in the primal? 
So, I get here cBx star. 

252
00:13:38,520 --> 00:13:43,570
So, what I get here is that this feasible 
solution of the dual is exactly the same 

253
00:13:43,570 --> 00:13:47,440
cost as the optimal solution to the, to 
the primal. 

254
00:13:47,440 --> 00:13:51,220
So, I have one feasible solution to the 
dual, same solution as the primal. 

255
00:13:51,220 --> 00:13:55,320
I know that there are no solution of the 
dual that can be better, so I fit, what 

256
00:13:55,320 --> 00:13:58,170
you see here is that these two, the 
primal is going down. 

257
00:13:58,170 --> 00:14:03,250
The dual is going up, and then the meet 
at this optimal point. 

258
00:14:03,250 --> 00:14:06,720
Okay. 
So, that's, that's basically the result. 

259
00:14:06,720 --> 00:14:08,450
So, you will have the primal, you have 
the dual. 

260
00:14:08,450 --> 00:14:10,280
These two programs are closely related 
right. 

261
00:14:10,280 --> 00:14:13,310
To derive one from the other. 
And then, you know they have the same 

262
00:14:13,310 --> 00:14:17,398
objective value of optimality, okay. 
So, I've shown you the primary and dual, 

263
00:14:17,398 --> 00:14:22,000
dual relationship in, in the general in 
the, in the, in the restricted cases. 

264
00:14:22,000 --> 00:14:26,450
So, this is the general formula on how to 
obtain the dual from the primal, in full 

265
00:14:26,450 --> 00:14:30,010
generality, okay? 
So, in full generality, I'm doing two 

266
00:14:30,010 --> 00:14:32,530
things. 
I'm allowing to have equations not only 

267
00:14:32,530 --> 00:14:35,410
inequalities. 
And I'm allowing some variables to be 

268
00:14:35,410 --> 00:14:38,975
not, you know, non-negative. 
They can take any arbitrary real value. 

269
00:14:38,975 --> 00:14:42,020
Okay? 
And once you do that, okay, so you can 

270
00:14:42,020 --> 00:14:44,060
derive the dual in essentially the same 
way. 

271
00:14:44,060 --> 00:14:48,330
There will be some constraints which are 
equalities, some variables which are 

272
00:14:48,330 --> 00:14:50,750
constrained to be non-negative, and some 
which are not. 

273
00:14:50,750 --> 00:14:52,870
How do we get them? 
Well, look at this thing. 

274
00:14:52,870 --> 00:14:55,530
You know. 
Every equality will have a dual variable 

275
00:14:55,530 --> 00:14:59,230
which is associated with it. 
And that dual variable here is not 

276
00:14:59,230 --> 00:15:02,395
going to be constrained. 
It's non, it's, it doesn't have to be 

277
00:15:02,395 --> 00:15:03,320
non-negative. 
Okay? 

278
00:15:03,320 --> 00:15:06,850
If you have an inequality that's these 
types of constraints, they will obviously 

279
00:15:06,850 --> 00:15:09,880
have a dual variable, and that dual 
variable is to be non-negative, that's 

280
00:15:09,880 --> 00:15:11,720
what I've shown you before. 
Right? 

281
00:15:11,720 --> 00:15:15,730
And, the same thing happens for, you 
know, the, the primal variables. 

282
00:15:15,730 --> 00:15:19,530
If a primal variable is non-negative, you 
know that the constraint we are deriving, 

283
00:15:19,530 --> 00:15:22,130
like I've shown you before, has to be an 
inequality. 

284
00:15:22,130 --> 00:15:27,420
And we know that if the variable is 
non-constraints, we will get an equality. 

285
00:15:27,420 --> 00:15:29,520
Okay? 
So, very simple, equalities, no 

286
00:15:29,520 --> 00:15:33,278
constraints. 
Inequalities, non-negativity constraints. 

287
00:15:33,278 --> 00:15:35,365
Okay? 
So, that's the general form of the dual. 

288
00:15:35,365 --> 00:15:38,370
Okay? 
Now, there are some very interesting 

289
00:15:38,370 --> 00:15:40,270
properties for this dual and primal. 
Okay? 

290
00:15:40,270 --> 00:15:44,250
So, you know, this is basically telling 
you that the friend of my friend is my 

291
00:15:44,250 --> 00:15:45,020
friend. 
Okay? 

292
00:15:45,020 --> 00:15:47,820
So, the dual, the dual of the dual is the 
primal. 

293
00:15:47,820 --> 00:15:50,220
Okay. 
So, if you take the dual, and then 

294
00:15:50,220 --> 00:15:53,140
reapply the dual of that dual, you get 
back to the primal. 

295
00:15:53,140 --> 00:15:55,510
You know, that's a good property to have, 
otherwise it would be crazy. 

296
00:15:55,510 --> 00:15:57,380
Right? 
But this is essentially saying that if 

297
00:15:57,380 --> 00:16:00,695
you take the dual of the dual of the 
primal, you get the primal back. 

298
00:16:00,695 --> 00:16:03,010
Okay? 
Now, the other thing that you have to 

299
00:16:03,010 --> 00:16:05,860
understand is, you know what is the 
relationship if these things are 

300
00:16:05,860 --> 00:16:08,480
feasible, unfeasible, unbounded and so 
on, okay. 

301
00:16:08,480 --> 00:16:13,420
So, we already know that if the primal is 
feasible, okay, the primal is feasible 

302
00:16:13,420 --> 00:16:16,340
then the dual has to be feasible. 
If we have a solution, the other guy can 

303
00:16:16,340 --> 00:16:19,130
get back to that part of the solution. 
Okay? 

304
00:16:19,130 --> 00:16:21,910
Now, what if the primer is unbounded, 
okay? 

305
00:16:21,910 --> 00:16:25,960
So, what, you know, this is a picture 
which I've been, you know, telling you, 

306
00:16:25,960 --> 00:16:28,030
okay? 
So, when they are both feasible, when, 

307
00:16:28,030 --> 00:16:31,060
you know, they are both bounded and 
feasible, okay? 

308
00:16:31,060 --> 00:16:36,100
So, you have the primer going down, you 
have the dual going up, and they meet. 

309
00:16:36,100 --> 00:16:38,180
You know, it's like in Pac-Man when they 
go to the next level. 

310
00:16:38,180 --> 00:16:39,260
Oh, they meet. 
Okay. 

311
00:16:39,260 --> 00:16:41,410
So, this is what you have here. 
Okay. 

312
00:16:41,410 --> 00:16:44,500
Now, if, if the primal is unbounded, what 
is happening? 

313
00:16:44,500 --> 00:16:46,980
This guy's going down, down, down, down, 
down, down forever. 

314
00:16:46,980 --> 00:16:49,790
Right. 
And we know that the cost of this guy has 

315
00:16:49,790 --> 00:16:52,660
to be always greater. 
The cost of the primal is always to be 

316
00:16:52,660 --> 00:16:54,590
greater than the cost of the dual. 
Okay. 

317
00:16:54,590 --> 00:16:58,050
Therefore, the dual cannot go up. 
You know, it can go up, it, it, it 

318
00:16:58,050 --> 00:17:00,990
cannot, you cannot have a fixed cost for 
this dual because, otherwise, the other 

319
00:17:00,990 --> 00:17:04,640
one is, is, you know, going through it. 
And therefore, the only possibility for 

320
00:17:04,640 --> 00:17:08,970
the dual is where it, it has to be 
infeasible, right? 

321
00:17:08,970 --> 00:17:12,348
So, we know that this guy is, is, this 
guy is in, is, is the primal is 

322
00:17:12,348 --> 00:17:14,760
unbounded, the dual has to be feasible, 
okay. 

323
00:17:14,760 --> 00:17:19,006
Now, we have the last column that we need 
to consider, which is what about if the 

324
00:17:19,006 --> 00:17:21,150
primal is infeasible? 
Okay? 

325
00:17:21,150 --> 00:17:23,900
If the primal is infeasible, can the dual 
be infeasible? 

326
00:17:23,900 --> 00:17:26,010
And can the, can the dual be unbounded? 
Okay? 

327
00:17:26,010 --> 00:17:30,390
So, by analogy to the, you know, to the 
previous you can already, you know, reach 

328
00:17:30,390 --> 00:17:31,940
one of the conclusions. 
Okay? 

329
00:17:31,940 --> 00:17:35,780
But this is, this is a very simple 
example with, with, which expresses the 

330
00:17:35,780 --> 00:17:39,510
possibility. 
This is the primal, I minimize, okay x1. 

331
00:17:39,510 --> 00:17:42,850
Can I, cannot be simpler than that, okay? 
And two constraints okay? 

332
00:17:42,850 --> 00:17:45,480
These two constraints are very 
interesting, because, you know, you look 

333
00:17:45,480 --> 00:17:48,160
at the left-hand side here. 
And the other left-hand side that shows 

334
00:17:48,160 --> 00:17:50,900
the negation of each other. 
And they both have to be greater than 1. 

335
00:17:50,900 --> 00:17:52,930
So, this is clearing infeasible. 
Right? 

336
00:17:52,930 --> 00:17:55,780
So, this is the dual, okay? 
And what do you see in the dual? 

337
00:17:55,780 --> 00:17:59,290
You see, you know, this variables here 
are not, the variables x1 and x2 are not 

338
00:17:59,290 --> 00:18:03,300
constraint. 
So, you get equations inside a dual. 

339
00:18:03,300 --> 00:18:07,998
and therefore, you, you see some very 
nice equations with the right-hand side. 

340
00:18:07,998 --> 00:18:10,280
Okay? 
It's the same for this, the left hand 

341
00:18:10,280 --> 00:18:14,350
side for these two things are the same, 
but the constant, the constant here, is 

342
00:18:14,350 --> 00:18:15,230
different. 
Okay? 

343
00:18:15,230 --> 00:18:17,760
So, once again, it's feas, it's 
infeasible. 

344
00:18:17,760 --> 00:18:22,704
So, if the primal is infeasible, we know 
that the dual can be infeasible. 

345
00:18:22,704 --> 00:18:25,320
Okay? 
And then, there is the other case. 

346
00:18:25,320 --> 00:18:29,730
It can also be the case that the primal 
is infeasible, but the dual is unbounded. 

347
00:18:29,730 --> 00:18:33,000
And the only thing that I did here, I 
kept essentially the same constraints on 

348
00:18:33,000 --> 00:18:36,200
the top, so it's still infeasible. 
But I added more constraints saying that 

349
00:18:36,200 --> 00:18:40,300
the variables have to be non-negative. 
When the variables are non-negative, 

350
00:18:40,300 --> 00:18:44,580
remember the impact of that is changing 
equations into inequalities. 

351
00:18:44,580 --> 00:18:47,630
And that's what you see there. 
So now, essentially you have these two 

352
00:18:47,630 --> 00:18:50,913
guys here, which have the same left hand 
side, okay. 

353
00:18:50,913 --> 00:18:54,490
But now they are smaller or equal to 1 
and 0, so you don't force them to be 

354
00:18:54,490 --> 00:18:55,640
feasible anymore. 
Okay. 

355
00:18:55,640 --> 00:18:58,080
So, these constraint are easy to satisfy, 
right. 

356
00:18:58,080 --> 00:19:03,955
So, you make y a little bigger than, 
than, than y2, a little bit bigger than 

357
00:19:03,955 --> 00:19:06,685
y1, okay. 
And these constraints are always going to 

358
00:19:06,685 --> 00:19:09,210
satisfied. 
And therefore, what I can do now is take 

359
00:19:09,210 --> 00:19:13,420
this objective function and drive it up, 
as much as I can. 

360
00:19:13,420 --> 00:19:16,395
Right? 
I'm, I'm basically getting a value for 

361
00:19:16,395 --> 00:19:20,760
y1, getting an even greater value for y2, 
and these values can go up, up, up, up, 

362
00:19:20,760 --> 00:19:22,462
up, up, up. 
And so, it's unbounded. 

363
00:19:22,462 --> 00:19:25,547
Okay. 
So, once the primal is feasible, okay. 

364
00:19:25,547 --> 00:19:28,540
It's infeasible. 
The dual can be infeasible or the dual 

365
00:19:28,540 --> 00:19:30,895
can be unbounded. 
So, you know, the relationship which is 

366
00:19:30,895 --> 00:19:32,700
primal and dual now. 
Okay. 

367
00:19:32,700 --> 00:19:34,925
Now, there is another thing which is very 
nice. 

368
00:19:34,925 --> 00:19:37,407
Right? 
So, one of the things about the theory of 

369
00:19:37,407 --> 00:19:40,740
NP completeness is I told you, okay. 
These problems are hard, we have to push 

370
00:19:40,740 --> 00:19:43,230
the exponential, okay. 
That's what we have been doing all along, 

371
00:19:43,230 --> 00:19:45,980
okay. 
But the nice thing about this problems is 

372
00:19:45,980 --> 00:19:50,230
that we can actually show that if you 
give me a solution, I can check if it's 

373
00:19:50,230 --> 00:19:51,170
feasible or not. 
Okay. 

374
00:19:51,170 --> 00:19:54,550
Very easy, you know, typically low 
polynomial type, okay. 

375
00:19:54,550 --> 00:19:58,960
But, but proving that something is 
optimal is kind of tough, right. 

376
00:19:58,960 --> 00:20:03,250
So, I don't have that, okay. 
Now, in linear programming, can you 

377
00:20:03,250 --> 00:20:06,910
actually provide me with a certificate of 
optimality? 

378
00:20:06,910 --> 00:20:08,650
And the answer is yes. 
This is nice. 

379
00:20:08,650 --> 00:20:11,450
In, in linear programming, I could show 
something is feasible. 

380
00:20:11,450 --> 00:20:14,880
But if I give you, if I give you a 
solution, you can check quickly if it's 

381
00:20:14,880 --> 00:20:17,080
satisfy, you know, if it's feasible or 
not. 

382
00:20:17,080 --> 00:20:21,520
But here, you can also convince me that 
you can act, that you actually have found 

383
00:20:21,520 --> 00:20:23,900
an optimal solution. 
How would you do that? 

384
00:20:23,900 --> 00:20:27,210
Think about it. 
How would you actually convince me that 

385
00:20:27,210 --> 00:20:30,270
you have an optimal solution? 
Well, this is what you would do, right. 

386
00:20:30,270 --> 00:20:33,890
So, you would say, oh, but you know, we 
have primal and you have a dual you know, 

387
00:20:33,890 --> 00:20:37,070
okay. 
So, von Neumann and [UNKNOWN] and some 

388
00:20:37,070 --> 00:20:41,130
people at Princeton, Ken Tucker and Dale, 
if i remember correctly, actually proved 

389
00:20:41,130 --> 00:20:42,920
this beautiful relation between these 
guys. 

390
00:20:42,920 --> 00:20:47,680
These, these primal and the dual. 
So now, and so you believe these guys. 

391
00:20:47,680 --> 00:20:53,330
So now, you can give me an x star which 
satisfy, you know, the constraints, the 

392
00:20:53,330 --> 00:20:57,310
constraints of the primal. 
You can give me a y star which satisfies 

393
00:20:57,310 --> 00:21:00,830
the constraints of the dual, and you can 
show me that the cost of these two things 

394
00:21:00,830 --> 00:21:04,010
are the same. 
If this is the case, you know, I know, 

395
00:21:04,010 --> 00:21:09,700
then, that, you know, x star is an 
optimal solution to the primal. 

396
00:21:09,700 --> 00:21:12,800
And of course, that y star is an optimal 
solution to the dual. 

397
00:21:12,800 --> 00:21:17,500
So, you can actually give me something 
that I can check very quickly, if this is 

398
00:21:17,500 --> 00:21:20,710
actually an optimal solution. 
And this is one of the beauty of linear 

399
00:21:20,710 --> 00:21:23,310
programming. 
That's the gap between NP completeness 

400
00:21:23,310 --> 00:21:24,830
and polynomial time. 
Okay? 

401
00:21:24,830 --> 00:21:27,050
So. 
We have seen the, you know, we have seen 

402
00:21:27,050 --> 00:21:29,500
the basic introduction to the dual here, 
which is beautiful right? 

403
00:21:29,500 --> 00:21:32,885
You have this primal and the dual, right? 
And they have the same objective value at 

404
00:21:32,885 --> 00:21:35,765
optimality, assuming that there is a 
feasible solution for both. 

405
00:21:35,765 --> 00:21:39,700
For, for, you know, for one of them 
because then they are solutions for both 

406
00:21:39,700 --> 00:21:41,980
of them. 
They have this beautiful relationship, 

407
00:21:41,980 --> 00:21:44,540
okay? 
And what I'm going to do next time is to 

408
00:21:44,540 --> 00:21:48,930
show you, you know, how we act, what this 
actually means in practice, and what does 

409
00:21:48,930 --> 00:21:53,590
it actually, what is, how do we actually 
get to these things, and why does it make 

410
00:21:53,590 --> 00:21:55,470
any sense, okay? 
Thank you very much.