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.