1 00:00:00,090 --> 00:00:03,740 Ladies and gentlemen good morning or good afternoon or good evening. 2 00:00:03,740 --> 00:00:08,119 we are moving to the third part of this class which is mathematical programming. 3 00:00:08,119 --> 00:00:11,780 And this lecture is going to be the first part of that third part. 4 00:00:11,780 --> 00:00:13,400 And that's going to be about linear programming. 5 00:00:13,400 --> 00:00:16,570 Okay. So, linear programming what we are going 6 00:00:16,570 --> 00:00:20,170 to do in the lecture is first find out what is a linear program, and then talk 7 00:00:20,170 --> 00:00:24,300 about convexity and geometry. Okay, so let me give you the context 8 00:00:24,300 --> 00:00:26,230 here. So, linear programming was invented by 9 00:00:26,230 --> 00:00:31,852 George Dantzig in 1947, and it's one of the most fundamental truths in, in 10 00:00:31,852 --> 00:00:35,130 combinatorial optimization. It's one of the growing, it has been a 11 00:00:35,130 --> 00:00:39,880 growing area for, for decades. And actually, people are still working 12 00:00:39,880 --> 00:00:43,320 very actively in this, and I, as I will told you, you know, there are still some 13 00:00:43,320 --> 00:00:45,430 very interesting open issues in that area. 14 00:00:45,430 --> 00:00:50,950 But the, the really important thing for us is that this is a really fundamental 15 00:00:50,950 --> 00:00:53,345 tool for doing a lot of different things in optimization. 16 00:00:53,345 --> 00:00:55,990 Okay. The other thing which is very nice in 17 00:00:55,990 --> 00:00:58,040 linear programming is that you have, you have these two views. 18 00:00:58,040 --> 00:01:00,256 You have the geometrical views. You have the algebraic view. 19 00:01:00,256 --> 00:01:01,980 And they have beautiful connection between them. 20 00:01:01,980 --> 00:01:05,260 So, we'll switch typically from, you know, the algebraic view to the 21 00:01:05,260 --> 00:01:08,370 geometric, to the geometry view, and so on and so forth. 22 00:01:08,370 --> 00:01:10,740 And today, mostly we'll talk about the geometry. 23 00:01:10,740 --> 00:01:14,590 But the next lecture is going to be about linking the two things together, okay. 24 00:01:14,590 --> 00:01:19,130 So, fundamental tools, beautiful connection between, you know, visual, you 25 00:01:19,130 --> 00:01:23,680 know, geometrical intuition, and then the algebraic the algebraic, you know, 26 00:01:23,680 --> 00:01:29,110 expressions of, of the problem. This is what a linear program is, okay? 27 00:01:29,110 --> 00:01:33,580 So, what you see at the top is basically minimizing a linear objective function. 28 00:01:33,580 --> 00:01:35,980 Okay? Subject to a set of linear inequalities, 29 00:01:35,980 --> 00:01:38,760 okay? Now, one of the things that you have to 30 00:01:38,760 --> 00:01:42,090 see here is that the variables will have to be non-negative, all of them. 31 00:01:42,090 --> 00:01:46,021 So, in this expression, okay, so the x i are the variables, okay? 32 00:01:46,021 --> 00:01:51,092 Real numbers. And the ci's, the ai's, and the bi's are 33 00:01:51,092 --> 00:01:52,870 the constant. Okay. 34 00:01:52,870 --> 00:01:56,030 So, in this particular expression, obviously you have n variables. 35 00:01:56,030 --> 00:01:58,670 You have n constraints. Okay. 36 00:01:58,670 --> 00:02:01,060 the variables, as I said, are non-negative. 37 00:02:01,060 --> 00:02:05,960 They have to take, you know, a non-negative, you know, value. 38 00:02:05,960 --> 00:02:07,590 Okay. And all the constraints here are 39 00:02:07,590 --> 00:02:08,810 inequalities. Okay. 40 00:02:08,810 --> 00:02:11,355 So, that's the basic form of a linear program. 41 00:02:11,355 --> 00:02:13,190 Okay. So, when we think about linear 42 00:02:13,190 --> 00:02:17,224 programming, we think about this. Okay, minimizing, you know, a set of a 43 00:02:17,224 --> 00:02:20,912 linear objective function subject to a set of linear inequalities. 44 00:02:20,912 --> 00:02:26,500 Okay, so, here are the answer. Can I maximize? 45 00:02:26,500 --> 00:02:29,340 Yes you can. Okay, so the way you would do that is 46 00:02:29,340 --> 00:02:34,320 simply by replacing the maximization of your linear objective by the negation, 47 00:02:34,320 --> 00:02:38,660 the, the minus of that particular objective, and you will minimize that. 48 00:02:38,660 --> 00:02:41,220 Okay? So, if you minimize, you know, minus your 49 00:02:41,220 --> 00:02:42,710 objective function. Okay? 50 00:02:42,710 --> 00:02:45,005 So you will a sense, in a sense, maximize. 51 00:02:45,005 --> 00:02:49,850 So, if you want to maximize, just minimize and negate the entire, all the 52 00:02:49,850 --> 00:02:56,220 coefficients of your objective function. Now, can a variable xi take both positive 53 00:02:56,220 --> 00:02:58,600 and negative values? Can you actually represent that? 54 00:02:58,600 --> 00:03:00,730 You can, okay? And here is how you do it. 55 00:03:00,730 --> 00:03:05,620 You take variable xi, and everywhere inside your linear program, you replace 56 00:03:05,620 --> 00:03:09,940 it by a difference of two variables. xi plus and xi minus. 57 00:03:09,940 --> 00:03:12,030 Okay. So, essentially you take this term here 58 00:03:12,030 --> 00:03:15,970 and you replace xi everywhere by that particular term, okay? 59 00:03:15,970 --> 00:03:17,030 Now, where does it work? Okay. 60 00:03:17,030 --> 00:03:19,950 So, both of these variables have to take the non-negative values. 61 00:03:19,950 --> 00:03:22,440 Okay, that's the, you know, that's the linear programming does. 62 00:03:22,440 --> 00:03:25,240 All the variables have to take non-linear, non-negative values. 63 00:03:25,240 --> 00:03:28,580 But when you look at this difference, this difference can take both positive 64 00:03:28,580 --> 00:03:31,466 and negative values. You want a positive value, give it to xi 65 00:03:31,466 --> 00:03:32,490 plus. Okay. 66 00:03:32,490 --> 00:03:35,180 And the other terms can be zero. You want a negative value? 67 00:03:35,180 --> 00:03:40,970 Give a positive value to xi minus, a zero to xi plus, and you get a negative value. 68 00:03:40,970 --> 00:03:43,310 Okay? So as, in a sense, they're easy, right? 69 00:03:43,310 --> 00:03:46,180 So, you have a variable, it can take both positive and negative values. 70 00:03:46,180 --> 00:03:50,110 What you do is you replace them by this term everywhere inside the linear 71 00:03:50,110 --> 00:03:51,390 program. Okay? 72 00:03:51,390 --> 00:03:53,260 Now, what if you have an equality constraint. 73 00:03:53,260 --> 00:03:56,450 Very simple as well. You take that equations, you replace it 74 00:03:56,450 --> 00:03:58,570 by two inequalities. Okay. 75 00:03:58,570 --> 00:04:03,000 In one smaller equal, one greater equal, the smaller equal you can, you know, you 76 00:04:03,000 --> 00:04:05,040 just transform it into a smaller equal as well. 77 00:04:05,040 --> 00:04:08,830 And you have, essentially, an equation at that point. 78 00:04:08,830 --> 00:04:10,056 Okay. So, very simple. 79 00:04:10,056 --> 00:04:12,870 Okay. Now, what if my variable can take integer 80 00:04:12,870 --> 00:04:15,480 value? That you can't do it in linear program. 81 00:04:15,480 --> 00:04:17,700 Okay. So, this is something that we'll talk 82 00:04:17,700 --> 00:04:19,050 about later in the class. Okay. 83 00:04:19,050 --> 00:04:21,700 It's going to be what we call mixed teacher program. 84 00:04:21,700 --> 00:04:25,240 But this not a linear program. And you'll see, there is a fundamental 85 00:04:25,240 --> 00:04:27,400 difference between these two. Okay? 86 00:04:27,400 --> 00:04:31,563 Now, what about, you know, if I have a non-linear constraint? 87 00:04:31,563 --> 00:04:34,120 Okay? Well, what we are talking about here is a 88 00:04:34,120 --> 00:04:36,680 linear program. It's not a non-linear program. 89 00:04:36,680 --> 00:04:38,810 It's called a linear program for a reason. 90 00:04:38,810 --> 00:04:42,510 We only want to have linear, you know, linear constraints and a linear objective 91 00:04:42,510 --> 00:04:45,570 function. And, and that give me the opportunity to 92 00:04:45,570 --> 00:04:47,570 tell you a story about George Dantzig, of course. 93 00:04:47,570 --> 00:04:51,020 You know, when George Dantzig presented this, he was, you know, invented, you 94 00:04:51,020 --> 00:04:53,270 know, linear programming, he was a graduate student. 95 00:04:53,270 --> 00:04:56,340 And, you know, when he wanted to present these results, he went to this 96 00:04:56,340 --> 00:05:00,100 conference, and there were plenty of, you know, big shot in optimization there. 97 00:05:00,100 --> 00:05:05,440 And so, he presented this results. Okay, and then there was this big shock 98 00:05:05,440 --> 00:05:10,180 in optimization, this big German guy with the big, deep voice, right. 99 00:05:10,180 --> 00:05:13,600 And so, he stood up and said Mr. Dantzig, you very well know that the 100 00:05:13,600 --> 00:05:15,070 world is non-linear. Okay? 101 00:05:15,070 --> 00:05:19,430 And so, Dantzig was like shaking up a little bit, how am I going to answer that 102 00:05:19,430 --> 00:05:22,308 questions. And then, you know, that particular 103 00:05:22,308 --> 00:05:25,270 confront, [UNKNOWN], and you know, the genius in Computer Science and Applied 104 00:05:25,270 --> 00:05:28,800 Mathematics and Mathematics in general, was there and he stood up and said 105 00:05:28,800 --> 00:05:31,804 mister, you know, George Dantzig stated this axioms. 106 00:05:31,804 --> 00:05:34,310 Okay. He told you when you can apply, you know, 107 00:05:34,310 --> 00:05:37,468 the method. If you have a problem that [UNKNOWN] use 108 00:05:37,468 --> 00:05:41,090 it, if your problem doesn't, don't use it. 109 00:05:41,090 --> 00:05:45,270 And I think, you know, that was really classy and I'm sure, you know, George 110 00:05:45,270 --> 00:05:49,060 Dantzig appreciate that a lot. Okay, so, essentially, no linear 111 00:05:49,060 --> 00:05:52,320 constraints, no variable that can take integer value, that's outside the scope 112 00:05:52,320 --> 00:05:53,470 of linear programming. Okay? 113 00:05:53,470 --> 00:05:57,260 The rest here, you can express essentially, you know, the way you want. 114 00:05:57,260 --> 00:05:59,930 Okay? Now, let me talk about geometry. 115 00:05:59,930 --> 00:06:02,100 Right? So, we saw, we just saw the algebraic 116 00:06:02,100 --> 00:06:06,360 form of what a linear program is. So, I want to took a little bit what this 117 00:06:06,360 --> 00:06:09,825 means from a geometrical standpoint. So, I'm going to start with convex sets, 118 00:06:09,825 --> 00:06:12,910 okay. And so, I gave you a couple of sets here, 119 00:06:12,910 --> 00:06:16,460 okay, set of points like, you know, the points inside a circle, inside a square. 120 00:06:16,460 --> 00:06:20,460 Inside this, you know, this kind of apple, you know, square where you know 121 00:06:20,460 --> 00:06:25,460 the, the, the corner are rounded right, and then the spot is the star. 122 00:06:25,460 --> 00:06:28,620 Okay. So, which one of these are convex set? 123 00:06:28,620 --> 00:06:30,310 Okay. So, the intuition is very simple. 124 00:06:30,310 --> 00:06:33,620 Take two points, draw a line between them, okay. 125 00:06:33,620 --> 00:06:37,970 If all the points between these two, if all the points in the line between them 126 00:06:37,970 --> 00:06:42,080 are inside the, the set, okay, that means that the set is convex. 127 00:06:42,080 --> 00:06:43,045 Okay. This is convex. 128 00:06:43,045 --> 00:06:46,390 Okay, we are happy, okay. So, this is the star I'm showing. 129 00:06:46,390 --> 00:06:49,050 Let's take two points. Let's draw a line between them. 130 00:06:49,050 --> 00:06:51,780 What you get? You know, there are some points here 131 00:06:51,780 --> 00:06:55,390 which are all aside the set. Therefore, this is not a convex set. 132 00:06:55,390 --> 00:06:58,169 Okay, not happy. Okay, now this is 2D. 133 00:06:58,169 --> 00:07:03,860 2D is really boring, so let's move to 3D. Okay, and this is 3D. 134 00:07:03,860 --> 00:07:06,680 Okay. So, you see this this field, okay. 135 00:07:06,680 --> 00:07:09,630 It's a convex set, okay. You take the two points. 136 00:07:09,630 --> 00:07:11,340 You draw a line between them. And look. 137 00:07:11,340 --> 00:07:15,250 You know, whatever you look at it, okay. All the point in between these, all the 138 00:07:15,250 --> 00:07:18,180 points in this lines are inside the convex set. 139 00:07:18,180 --> 00:07:21,470 That's what the convex set is all about, okay. 140 00:07:21,470 --> 00:07:26,240 So, let's move to the next one. Okay, here is the next one, you know, 141 00:07:26,240 --> 00:07:27,740 okay? So you see this thing. 142 00:07:27,740 --> 00:07:30,680 It looks like a convex set, right? But look at this line. 143 00:07:30,680 --> 00:07:33,810 I've selected two points, I drew the line between them, I go to zip. 144 00:07:33,810 --> 00:07:36,610 Whoops. You know, you see there, you see, you can 145 00:07:36,610 --> 00:07:39,840 see clearly, you know, the line goes outside the, the set. 146 00:07:39,840 --> 00:07:42,380 This is not a convex set. Okay? 147 00:07:42,380 --> 00:07:44,180 So, beautiful thing here. Okay? 148 00:07:44,180 --> 00:07:47,390 You can look, you know, you take two points, you draw a line between them, 149 00:07:47,390 --> 00:07:50,880 it's outside a set, that's not a convex set. 150 00:07:50,880 --> 00:07:53,215 Okay? So, this is once again, you know, the 151 00:07:53,215 --> 00:07:56,300 geometric intuition. What I want to show you now is the 152 00:07:56,300 --> 00:07:57,690 algebraic expression. Okay? 153 00:07:57,690 --> 00:08:02,010 So, if you set up point v1 to a set of points v1 to vn, okay. 154 00:08:02,010 --> 00:08:05,160 So, we will define the convex combinations of these points. 155 00:08:05,160 --> 00:08:08,900 And the way you define these convex combination, and that's essentially the 156 00:08:08,900 --> 00:08:12,290 points which are on this line, right. So, so that of course, an arbitrary 157 00:08:12,290 --> 00:08:13,340 dimension. Okay. 158 00:08:13,340 --> 00:08:17,555 So, what you do is you multiply, you multiply every one of these by these 159 00:08:17,555 --> 00:08:20,590 Lambdas. Lambda 1, Lambda 2, Lambda n, if you have 160 00:08:20,590 --> 00:08:24,190 n, you know, points. And, and that's going to be your convex 161 00:08:24,190 --> 00:08:27,530 combination of all these points. v1 want to be n. 162 00:08:27,530 --> 00:08:31,220 Provided, of course, that the sum of these Lambda is one and they are all 163 00:08:31,220 --> 00:08:32,390 greater is equal to zero. Okay. 164 00:08:32,390 --> 00:08:37,490 So, if I have an expression like this okay, and I make sure that all the 165 00:08:37,490 --> 00:08:41,370 Lambdas are equal to 1. And all of them greater are equal to 166 00:08:41,370 --> 00:08:45,748 zero, then I have a convex combination of all the points v1 to vn. 167 00:08:45,748 --> 00:08:48,510 Okay. So, this is how I can define a convex 168 00:08:48,510 --> 00:08:49,290 set. Okay? 169 00:08:49,290 --> 00:08:52,250 So, why? Because essentially, now a convex set can 170 00:08:52,250 --> 00:08:56,520 be defined in the following fashion. So you say a convex set, okay, a set 171 00:08:56,520 --> 00:08:59,710 essentially is convex. If you take points of these things and 172 00:08:59,710 --> 00:09:04,290 all the convex combination of the points that you have in the set are inside the 173 00:09:04,290 --> 00:09:05,540 set. Okay? 174 00:09:05,540 --> 00:09:08,145 So, basically take a bunch of points, okay, these points are going to be from 175 00:09:08,145 --> 00:09:11,280 convex. If whatever, you know, convex combination 176 00:09:11,280 --> 00:09:14,335 you take, those points are inside the set. 177 00:09:14,335 --> 00:09:17,110 Okay? So, that's a convex set. 178 00:09:17,110 --> 00:09:20,520 Now, so this is an interesting result that we're going to use all the time. 179 00:09:20,520 --> 00:09:24,980 Okay, so essentially, you know, the intersection of a set, of convex sets, 180 00:09:24,980 --> 00:09:27,590 okay, is itself convex. Okay? 181 00:09:27,590 --> 00:09:28,830 And so is the proof. Okay? 182 00:09:28,830 --> 00:09:33,290 So very, very simple proof. So, so let's, you know, let's denote by 183 00:09:33,290 --> 00:09:37,850 this notation here, the intersection of all the set S i, okay, from 1 to n. 184 00:09:37,850 --> 00:09:39,730 Okay? So, we take this intersection of all 185 00:09:39,730 --> 00:09:41,380 these sets. Okay? 186 00:09:41,380 --> 00:09:44,639 And, and, of all the set S i. So right, that you see. 187 00:09:46,350 --> 00:09:50,290 And so, what are we going to do is we are going to consider, okay, a bunch of 188 00:09:50,290 --> 00:09:52,500 points inside this intersection. Okay? 189 00:09:52,500 --> 00:09:57,065 So, let's say v v 1 to v n are in, are the points inside that intersection. 190 00:09:57,065 --> 00:10:00,000 Okay? So what it follows, obviously, because 191 00:10:00,000 --> 00:10:03,930 they are inside the intersection, that basically means that they are inside 192 00:10:03,930 --> 00:10:05,500 every one of the sets. Okay? 193 00:10:05,500 --> 00:10:10,340 So the points inside a intersection, by definitions, are inside every one of 194 00:10:10,340 --> 00:10:13,580 these sets, okay? Now, what do we know about the sets, we 195 00:10:13,580 --> 00:10:17,390 know that the sets are convex, okay? So, essentially what that means is that 196 00:10:17,390 --> 00:10:21,700 all the convex combination of these points are also in the set i, and that's 197 00:10:21,700 --> 00:10:25,310 varied if it is S1, S2, S3 for all the sets right. 198 00:10:25,310 --> 00:10:28,300 So now what do I know? I know that every convex combination of 199 00:10:28,300 --> 00:10:30,300 these points are in every one of the sets. 200 00:10:30,300 --> 00:10:33,160 And therefore, they are in the intersection of this set. 201 00:10:33,160 --> 00:10:35,690 Okay? And, of the sets, and that, and that 202 00:10:35,690 --> 00:10:38,100 means what? That means that essentially, all the 203 00:10:38,100 --> 00:10:42,370 convex combinations of the points in that, inside the intersection are inside 204 00:10:42,370 --> 00:10:44,590 the intersection. And therefore, the intersection is 205 00:10:44,590 --> 00:10:47,160 convex, okay? Now why this is interesting? 206 00:10:47,160 --> 00:10:52,210 Okay, so look, when we look at linear programs we have these inequalities, 207 00:10:52,210 --> 00:10:56,040 right? And these inequalities, okay, so they are 208 00:10:56,040 --> 00:11:00,000 basically representing half spaces, and these half spaces are convex. 209 00:11:00,000 --> 00:11:01,940 You can prove that. Take the definition that I've shown you 210 00:11:01,940 --> 00:11:04,290 before, and try to prove that this is convex. 211 00:11:04,290 --> 00:11:06,770 And the proof is very simple, right? Three lines. 212 00:11:06,770 --> 00:11:08,740 Okay? But you can prove, essentially, that 213 00:11:08,740 --> 00:11:11,660 every one of these half spaces are convex. 214 00:11:11,660 --> 00:11:14,340 And so, when you look at the linear programs, and the constraints of the 215 00:11:14,340 --> 00:11:18,720 linear programs, what you have is essentially a bunch of these half spaces 216 00:11:18,720 --> 00:11:22,440 that are defining the feasible region of the linear program. 217 00:11:22,440 --> 00:11:26,740 And so, all of them, you know, are convex, and the intersection of them is 218 00:11:26,740 --> 00:11:27,970 also convex. Okay. 219 00:11:27,970 --> 00:11:30,830 And so, this is, this is called a polyhedron. 220 00:11:30,830 --> 00:11:33,250 Okay. The intersection of all these half space. 221 00:11:33,250 --> 00:11:36,775 And if it's this finite, that means it doesn't go to infinity in one of the 222 00:11:36,775 --> 00:11:39,470 dimensions, it's called a polytope. Okay? 223 00:11:39,470 --> 00:11:43,380 So, big idea here is what, you know, we are dealing with convex set. 224 00:11:43,380 --> 00:11:48,450 Every one of these sets is, every one of these inequalities is basically defining 225 00:11:48,450 --> 00:11:51,020 your convex set which is called a half space. 226 00:11:51,020 --> 00:11:54,530 You have many of them, so for having a solution you have to study by all of 227 00:11:54,530 --> 00:11:55,960 them. That means you have to be in the 228 00:11:55,960 --> 00:12:00,130 intersection of all of them and I told you that a intersection of a set of 229 00:12:00,130 --> 00:12:03,400 convex set was convex, And therefore, we know that the intersection of these 230 00:12:03,400 --> 00:12:05,420 things is going to be convex. Okay? 231 00:12:05,420 --> 00:12:08,240 So, let's look at these things a little bit geometrically, right? 232 00:12:08,240 --> 00:12:13,160 So, this is this is a hyperplane, okay? So, this is hyperplane, and that define, 233 00:12:13,160 --> 00:12:16,520 you know, a half space. And let's assume that, you know, we are 234 00:12:16,520 --> 00:12:20,290 looking at the solution on this side. That's part of our feasible region. 235 00:12:20,290 --> 00:12:21,760 Then, I can take another one. Right? 236 00:12:21,760 --> 00:12:24,600 So I take another half space. Okay? 237 00:12:24,600 --> 00:12:29,360 And I, you know, refine my feasible region, and the little guy over there, 238 00:12:29,360 --> 00:12:30,990 that's called a vertex. Okay? 239 00:12:30,990 --> 00:12:34,368 And you're going to see today, I'm going to really be obsessed with these 240 00:12:34,368 --> 00:12:35,410 vertices. Okay? 241 00:12:35,410 --> 00:12:37,910 But that's another one. I can take another one, and then the 242 00:12:37,910 --> 00:12:41,990 colors are getting uglier and uglier, and uglier, but I'm getting those 243 00:12:41,990 --> 00:12:45,280 intersection of the set. Actually I don't really know in there, 244 00:12:45,280 --> 00:12:49,320 you know, ugly because I'm colorblind, I don't see anything here, but anyway I was 245 00:12:49,320 --> 00:12:52,095 told that they are really ugly. So we are not going to represent them, 246 00:12:52,095 --> 00:12:53,890 we're going to represent the feasible region like this. 247 00:12:53,890 --> 00:12:55,900 So this is essentially all of my upper planes. 248 00:12:55,900 --> 00:12:59,790 They are defining half place, half space everywhere okay, think of them as 249 00:12:59,790 --> 00:13:02,760 inequalities. And then, this is the visible regions of 250 00:13:02,760 --> 00:13:04,370 the linear program. Okay? 251 00:13:04,370 --> 00:13:08,280 You see the algebraic version of every one of the inequalities that I have been 252 00:13:08,280 --> 00:13:09,990 mentioning here. Okay? 253 00:13:09,990 --> 00:13:14,960 So this is in 2D, right, so it's boring, so we're going to see 3D as well in a 254 00:13:14,960 --> 00:13:19,210 moment, right. But before that what I want to do is 255 00:13:19,210 --> 00:13:23,550 telling you a little bit more definitions here, so a face okay we'll talk about 256 00:13:23,550 --> 00:13:27,278 face and facets. So, face is basically the intersection of 257 00:13:27,278 --> 00:13:32,640 finitely hyperplanes, okay. And so, if we are in dimension n minus 1, 258 00:13:32,640 --> 00:13:36,210 we'll call, we'll call up, you know, we'll talk about facets. 259 00:13:36,210 --> 00:13:39,550 And this, you know, you'll see later on why this facet are important, not right 260 00:13:39,550 --> 00:13:43,370 now, not really for linear program, but later on they will become very important. 261 00:13:43,370 --> 00:13:47,300 And then, of course, when you are in dimension 0, you will have what, you 262 00:13:47,300 --> 00:13:50,840 know, what we call vertices okay. And your, your going to see I'm 263 00:13:50,840 --> 00:13:53,475 completely obsessed, today I'm going to be completely obsessed with these 264 00:13:53,475 --> 00:13:56,650 vertices, okay? So, this is in 3D. 265 00:13:56,650 --> 00:13:59,870 Okay, so this is the first hyperplane we see here. 266 00:13:59,870 --> 00:14:03,225 Okay, a single hyperplane. And we're going to increase the number of 267 00:14:03,225 --> 00:14:07,409 hyperplanes there, but you see the first one over there, right, in three 268 00:14:07,409 --> 00:14:11,370 dimensional. Okay, and now look at this. 269 00:14:11,370 --> 00:14:14,540 This is two hyperplanes, okay, so you see. 270 00:14:14,540 --> 00:14:17,560 You know, the top, and the, you know, the, mostly vertical and mostly 271 00:14:17,560 --> 00:14:20,520 horizontal hyperplanes. You see now that these two hyperplanes 272 00:14:20,520 --> 00:14:24,230 intersect, the intersection of these two hyperplanes is a line. 273 00:14:24,230 --> 00:14:26,460 Okay? You see the line clearly over here. 274 00:14:26,460 --> 00:14:30,320 Okay? And notice this is a really beautiful 275 00:14:30,320 --> 00:14:31,020 fort. Okay? 276 00:14:31,020 --> 00:14:33,556 So, you see these three hyperplanes now. Okay? 277 00:14:33,556 --> 00:14:37,540 So, two, when two of them meet here at these lines that you can see, okay, here 278 00:14:37,540 --> 00:14:41,010 or there. And, of course, when the, the, all three 279 00:14:41,010 --> 00:14:44,580 of them meets, you get this unique point that you see at the back of the picture 280 00:14:44,580 --> 00:14:46,990 there. Okay, so that's essentially what you get 281 00:14:46,990 --> 00:14:49,966 when you have a finite intersection of this hyperplane. 282 00:14:49,966 --> 00:14:52,770 Okay, in 2D, when you have two, you have a line. 283 00:14:52,770 --> 00:14:56,737 When you have three, you have a vertex, well you have a point, okay. 284 00:14:56,737 --> 00:15:01,380 Okay, so what you see on the screen now is a huge number, not a huge number, a 285 00:15:01,380 --> 00:15:06,190 nice number of hyperplanes. And you get a very nice polytope that you 286 00:15:06,190 --> 00:15:08,720 see over there, okay. So, you can see all the facets, you can 287 00:15:08,720 --> 00:15:11,862 see all the vertices. You can see, you know, this entire 288 00:15:11,862 --> 00:15:15,200 polytope. and that's essentially the kind of 289 00:15:15,200 --> 00:15:18,760 objects that, you know, we are going to manipulate inside, you know, linear 290 00:15:18,760 --> 00:15:20,390 programming. Okay? 291 00:15:20,390 --> 00:15:25,280 So, we have this polytope, okay, nice polytope, and we add a new hyperplane. 292 00:15:25,280 --> 00:15:26,300 Okay? So you can see the new hyperplane. 293 00:15:26,300 --> 00:15:29,780 So, intersect with that polytope. Okay? 294 00:15:29,780 --> 00:15:31,610 So, that's what we want to look at, here. Okay? 295 00:15:31,610 --> 00:15:35,240 So, we have the polytope, we have a new hyperplane, okay, that's a new 296 00:15:35,240 --> 00:15:38,709 constraints in your problem, right? And so, what's going to happen? 297 00:15:38,709 --> 00:15:41,420 And this is what happens. Look at these new polytopes, now. 298 00:15:41,420 --> 00:15:44,889 We have a new facet, okay? And a bunch of new vertices here that you 299 00:15:44,889 --> 00:15:46,760 can see. You know, this is from the top, this is 300 00:15:46,760 --> 00:15:49,822 from the side, okay? So, all these, so that what this 301 00:15:49,822 --> 00:15:54,410 hyperplane did was cutting through the polytopes, and then adding a new facet, 302 00:15:54,410 --> 00:15:57,316 okay? And then, adding of a couple of new 303 00:15:57,316 --> 00:16:00,540 vertices as well, okay? Once again, what you see there is 304 00:16:00,540 --> 00:16:04,620 basically what all these you know hyperplanes are creating. 305 00:16:04,620 --> 00:16:08,951 And they are creating this beautiful polytopes with a bunch of facets and a 306 00:16:08,951 --> 00:16:11,170 number of vertices here. Okay. 307 00:16:11,170 --> 00:16:13,420 Now, this is a very important result. Okay. 308 00:16:13,420 --> 00:16:18,090 So, every point, okay, in aside a polytopes, the polytope that I've just 309 00:16:18,090 --> 00:16:21,890 shown you which are defined by these hyperplanes and housespaces is a convex 310 00:16:21,890 --> 00:16:25,520 combination of the vertices. Okay. 311 00:16:25,520 --> 00:16:28,580 So, that's a very interesting result. The basic thing is that every point 312 00:16:28,580 --> 00:16:32,668 inside this polytope, right, can be expressed as a combination of the 313 00:16:32,668 --> 00:16:35,360 vertices. I have this point here, okay it's a 314 00:16:35,360 --> 00:16:38,800 combination of these two vertices, I have this point, it's a combination of these 315 00:16:38,800 --> 00:16:40,800 three vertices here. Okay. 316 00:16:40,800 --> 00:16:44,120 So, that's a very interesting result. And we're going to use it for, you know, 317 00:16:44,120 --> 00:16:47,800 actually proving some very interesting results in, in the theory of linear 318 00:16:47,800 --> 00:16:49,200 programs. Okay. 319 00:16:49,200 --> 00:16:51,190 Now why, why am I so obsessed with these vertices? 320 00:16:51,190 --> 00:16:55,470 And this is the reason why. If you have a nice linear program that I, 321 00:16:55,470 --> 00:16:58,280 as I, as I, as I have shown you so far, okay. 322 00:16:58,280 --> 00:17:03,290 What you know, okay, is that at least one of the point, where the objective value, 323 00:17:03,290 --> 00:17:07,350 this guy here, right, is minimal. Okay, is going to be at the vertex. 324 00:17:07,350 --> 00:17:10,710 It doesn't mean that, you know, there are no other points where the solution is 325 00:17:10,710 --> 00:17:11,660 optimal. Okay? 326 00:17:11,660 --> 00:17:17,330 But there will be at least one of them which is located at a vertex, okay? 327 00:17:17,330 --> 00:17:21,000 So, in a sense, that's why we are obsessed with these vertices, right? 328 00:17:21,000 --> 00:17:26,940 So, because we know that one, at least one of the optimal solutions, okay, is 329 00:17:26,940 --> 00:17:30,760 going to be at one of these vertices. Okay and I'm going to show you the proof. 330 00:17:30,760 --> 00:17:35,455 Okay, but essentially what so, so lets, first let's look at it in a, in a, in a 331 00:17:35,455 --> 00:17:39,510 geometry in a geometry equate right? So, this is a hyperplane right? 332 00:17:39,510 --> 00:17:42,770 So, I'm basically saying, you know, I have the, I, I take the objective 333 00:17:42,770 --> 00:17:45,360 function, and I assume that it's equal to a positive value B. 334 00:17:45,360 --> 00:17:49,810 Okay, that defines an hyperplane and you see this hyperplane here, right? 335 00:17:49,810 --> 00:17:54,160 So, what I'm trying to do in a sense is minimize is minimize that b, right? 336 00:17:54,160 --> 00:18:00,900 So, in a sense I'm trying to take this hyper plane okay and bring it down, okay? 337 00:18:00,900 --> 00:18:06,065 And so, this is what this is what we going to do okay so when we optimize 338 00:18:06,065 --> 00:18:08,540 [SOUND]. We get to a particle point with this 339 00:18:08,540 --> 00:18:11,060 hyper, this value for B is going to be minimal. 340 00:18:11,060 --> 00:18:13,460 And so, this is a point that you see over there. 341 00:18:13,460 --> 00:18:16,870 And that point is on a vertex. Okay. 342 00:18:16,870 --> 00:18:20,220 And we're going to call it B star. And so, you'll see optimal solutions, I 343 00:18:20,220 --> 00:18:23,550 always going to have a little star, in, in, in these lectures. 344 00:18:23,550 --> 00:18:26,030 Okay. So, in a sense, once again we took, we 345 00:18:26,030 --> 00:18:29,670 took that, that hyperplace and we tried to minimize the value of b because that's 346 00:18:29,670 --> 00:18:33,600 the value of the objective function. And so, we move that hyperplane, and when 347 00:18:33,600 --> 00:18:37,230 it's minimal you can be sure that at least one of these points is a vertex. 348 00:18:38,550 --> 00:18:41,650 So, once again, you know, we take this thing, [SOUND], we bring it down. 349 00:18:41,650 --> 00:18:44,332 It's beautiful. Okay. 350 00:18:44,332 --> 00:18:47,690 And we have the optimal solution there. Now this is boring. 351 00:18:47,690 --> 00:18:50,940 Okay. So let's do it in 3D. 352 00:18:50,940 --> 00:18:53,820 And now, ladies and gentlemen, the 3D version right? 353 00:18:53,820 --> 00:18:56,510 So, what you see there is more beautiful polytopes. 354 00:18:56,510 --> 00:19:00,730 And you see this hyperplane there, which is defining the objective function, okay? 355 00:19:00,730 --> 00:19:03,250 And what you are trying to do in this one is maximize, okay? 356 00:19:03,250 --> 00:19:06,910 So, we're going to take his hyperplane and do exactly what we did in 2D's, 357 00:19:06,910 --> 00:19:09,330 right? So this point, it is equal to a constant, 358 00:19:09,330 --> 00:19:14,329 and we are going to try to drive it towards one of the vertices of this 359 00:19:14,329 --> 00:19:17,180 polytope. And this is the result, right. 360 00:19:17,180 --> 00:19:21,635 So, you see this hyperplane now and you see it intersecting finally with this 361 00:19:21,635 --> 00:19:25,180 polytope, okay. And this is probably the best angle here, 362 00:19:25,180 --> 00:19:26,230 right. So, you see that? 363 00:19:26,230 --> 00:19:29,220 It's intersecting with that vertices, okay. 364 00:19:29,220 --> 00:19:32,510 Everywhere else it doesn't touch the polytope, okay. 365 00:19:32,510 --> 00:19:34,940 And so this is, ooh, this is also very nice, okay? 366 00:19:34,940 --> 00:19:40,040 So, you can see that now, this object, it has been maximized, and it's basically a 367 00:19:40,040 --> 00:19:44,570 topological vertex of this polytope. So, I told you, you know, that at least 368 00:19:44,570 --> 00:19:48,380 one of the optimal solution is located on a vertex, and this is the proof, okay? 369 00:19:48,380 --> 00:19:50,830 So, it's a beautiful proof, very simple proof, okay? 370 00:19:50,830 --> 00:19:54,220 And that's why I want to go into, you know, it's something that you can 371 00:19:54,220 --> 00:19:55,850 understand inside the lecture. Okay? 372 00:19:55,850 --> 00:19:58,390 So, let's talk about x star, which is the minimum value. 373 00:19:58,390 --> 00:20:02,430 That's where, you know, the, the, the, that's where the linear program is 374 00:20:02,430 --> 00:20:03,230 optimal. Okay? 375 00:20:03,230 --> 00:20:07,670 This is the point somewhere, okay, and we assume that this, you know, that, that, 376 00:20:07,670 --> 00:20:09,870 we basically, you know, this is the optimal value. 377 00:20:09,870 --> 00:20:12,385 This is one of the optimal solution. Okay? 378 00:20:12,385 --> 00:20:14,600 Now, we know, we don't know where this point is. 379 00:20:14,600 --> 00:20:16,100 Right? So, we want to show that it's on a 380 00:20:16,100 --> 00:20:17,420 vertex. Right? 381 00:20:17,420 --> 00:20:23,400 So, we, we take that point, okay, and we know that every point inside a polytope 382 00:20:23,400 --> 00:20:26,250 can be expressed as a convex combination of the vertices. 383 00:20:26,250 --> 00:20:28,880 Okay? So, let's assume that these vertices are 384 00:20:28,880 --> 00:20:32,730 v1 to vt. We can reexpress x star, okay, this 385 00:20:32,730 --> 00:20:36,620 optimal point, as a convex combination of these vertices. 386 00:20:36,620 --> 00:20:40,830 And we have this, you know, these Lambda 1, Lambda 2, Lambda n, Lambda t, and we 387 00:20:40,830 --> 00:20:42,740 know that some of these Lambdas has to be equal to 1. 388 00:20:42,740 --> 00:20:44,248 And we're going to to use that information later on. 389 00:20:44,248 --> 00:20:47,510 Okay? So now, the objective value at optimality 390 00:20:47,510 --> 00:20:50,900 is c times, you know, x star of the optimal solution. 391 00:20:50,900 --> 00:20:54,718 And therefore, you know, we can reexpress it in terms of the vertices and the 392 00:20:54,718 --> 00:20:59,680 Lambdas by, by simply multiplying that, you know right inside by c. 393 00:20:59,680 --> 00:21:02,482 Okay? So, we basically have at that point that 394 00:21:02,482 --> 00:21:08,130 cx star is equal Lambda 1 times, you know, c1, c times by v1 plus, you know, 395 00:21:08,130 --> 00:21:10,900 the same thing for the other vertices. Okay. 396 00:21:10,900 --> 00:21:13,920 And so, at this point, you know, we just have done, you know, some very simple, 397 00:21:13,920 --> 00:21:19,350 you know algebraic manipulation, you know, knowing that every point inside 398 00:21:19,350 --> 00:21:21,866 the, every point inside the polytope is the convex combination of the, the 399 00:21:21,866 --> 00:21:25,610 vertices. So, what I'm going to do now is assume 400 00:21:25,610 --> 00:21:30,480 that this point, you know, this x star is not on the vertex, okay. 401 00:21:30,480 --> 00:21:34,970 And I'm going to assume that, it's, it's not a vertex, so what I'm assuming is 402 00:21:34,970 --> 00:21:39,810 essentially that cx star is always smaller than c times Vi. 403 00:21:39,810 --> 00:21:43,725 Okay, with Vi is one of the verticies, it's going to be smaller than all of the 404 00:21:43,725 --> 00:21:44,680 vertices. Okay? 405 00:21:44,680 --> 00:21:47,410 And what I'm going to do is derive a contradiction of course. 406 00:21:47,410 --> 00:21:49,630 Okay? And that will prove that it'll actually, 407 00:21:49,630 --> 00:21:52,190 it has to be at least on one of these vertices. 408 00:21:52,190 --> 00:21:54,200 Okay? And how do we get the contradiction? 409 00:21:54,200 --> 00:21:56,580 Well, let's start, let's start with cx star. 410 00:21:56,580 --> 00:21:58,800 So, we start with cx star. Okay? 411 00:21:58,800 --> 00:22:02,270 And then, we simply rewrite, you know, the formula that is shown before, but 412 00:22:02,270 --> 00:22:05,160 know at this point you see c, c v 1. What do we do? 413 00:22:05,160 --> 00:22:10,380 We, we made the hypothesis that cx star was smaller than c Vi. 414 00:22:10,380 --> 00:22:15,650 So, if we can replace every one of these c Vi, okay, by cx star, and we all know 415 00:22:15,650 --> 00:22:20,170 that cx star is going to be greater than that, because I'm replacing every one of 416 00:22:20,170 --> 00:22:21,753 these component by something which is smaller. 417 00:22:21,753 --> 00:22:25,700 Okay? Now, I factorize the cx star, okay, and I 418 00:22:25,700 --> 00:22:29,660 get the sum of the Lambdas and cx star. I know that because this is a convex 419 00:22:29,660 --> 00:22:34,320 combination that the sum of the Lambdas are equal to 1, so I get cx star. 420 00:22:34,320 --> 00:22:37,970 So, what I get is the formula, well, well, it's basically the contradiction 421 00:22:37,970 --> 00:22:40,430 here. I have that cx star is greater than cx 422 00:22:40,430 --> 00:22:42,600 star which is really difficult to do. Right. 423 00:22:42,600 --> 00:22:46,120 And therefore, you know, one of the hypothesis that I took, you know, was 424 00:22:46,120 --> 00:22:49,930 wrong, and this is the hypothesis that the value of the objective was, you know, 425 00:22:49,930 --> 00:22:53,540 smaller then all the vertices. So, I know that essentially, you know, 426 00:22:53,540 --> 00:22:58,865 the optimal solution has to be on a vertex, okay, very simple proof right. 427 00:22:58,865 --> 00:23:03,310 So, at this point still, so we know we have a lot of information, right? 428 00:23:03,310 --> 00:23:09,265 So, we know that the, the solution of a linear program is located to one of these 429 00:23:09,265 --> 00:23:11,465 vertices. Okay, so now, I have a geometry 430 00:23:11,465 --> 00:23:14,472 categorism to do that, right? I can solve the linear program 431 00:23:14,472 --> 00:23:17,869 geometrically. I just draw this polytope, okay, and then 432 00:23:17,869 --> 00:23:21,870 I inumerate all the vertices for every one of them, I compute a value of the 433 00:23:21,870 --> 00:23:24,820 objective function. And that's going to be giving me the 434 00:23:24,820 --> 00:23:28,930 optimal solution. Okay, so that's the algebraic view, okay. 435 00:23:28,930 --> 00:23:33,160 So, what we're going to do next time is to show how this algebraic, this 436 00:23:33,160 --> 00:23:37,400 geometrical view, can be, you know, can be translated to an algebraic view which 437 00:23:37,400 --> 00:23:41,498 we will be able to solve in a little bit, you know, in a little bit easier fashion. 438 00:23:41,498 --> 00:23:43,998 Okay, thank you.