1 00:00:01,060 --> 00:00:03,460 And now, we finally get to Lagrange's Method. 2 00:00:05,800 --> 00:00:08,980 Hey guys. I'm, I'm starting up again. 3 00:00:10,990 --> 00:00:12,970 So now I get to Lagrange's Method. 4 00:00:16,340 --> 00:00:18,510 So the problem I am trying to solve. 5 00:00:18,510 --> 00:00:20,143 Remember when I go back to my 6 00:00:20,143 --> 00:00:23,690 portfolio optimization, I want to maximize a function. 7 00:00:25,550 --> 00:00:29,840 So I'm going to call this my objective subject to one or more constraints. 8 00:00:29,840 --> 00:00:31,688 So I'm, I'm going to use n for the number 9 00:00:31,688 --> 00:00:34,340 of variables of the function I am trying to maximize. 10 00:00:34,340 --> 00:00:38,730 And then I'm going to think about having n con-, m constraints. 11 00:00:38,730 --> 00:00:40,660 So g1 up to gm. 12 00:00:44,370 --> 00:00:49,006 So there was a 18th century mathematician named Joseph Louis Lagrange 13 00:00:49,006 --> 00:00:53,810 who proposed the following method for, for a solution for this problem. 14 00:00:57,540 --> 00:01:00,350 And his solution was to make this function 15 00:01:02,650 --> 00:01:08,580 It's now a function of the original n variable so x one up to xn. 16 00:01:09,590 --> 00:01:11,730 And then also these values lambda. 17 00:01:11,730 --> 00:01:15,400 So you get one lambda for each of the constraints you have. 18 00:01:15,400 --> 00:01:20,380 So lambdas going to go there's, or the subscript on lambda will go from one to m. 19 00:01:20,380 --> 00:01:24,190 So there's Lambda 1 for g1, Lambda 2 for g2, and so on. 20 00:01:25,540 --> 00:01:28,060 And the way you make this function 21 00:01:28,060 --> 00:01:31,660 is you just put the objective here, and then you 22 00:01:31,660 --> 00:01:37,230 add Lambda times each of these constraints to that objective function. 23 00:01:37,230 --> 00:01:40,116 So you have Lambda 1 times g1 plus Lambda 2 24 00:01:40,116 --> 00:01:43,020 times g2 plus Lambda 3 times g3 and so on. 25 00:01:44,080 --> 00:01:47,811 And also note that I've written the constraints 26 00:01:47,811 --> 00:01:50,960 so that they have to be equal to zero. 27 00:01:50,960 --> 00:01:53,202 So this is zero isn't a variable that's kind 28 00:01:53,202 --> 00:01:55,160 of hard coded in that spot. 29 00:01:55,160 --> 00:01:59,960 So if you have something like a condition X squared plus Y squared equals 1, 30 00:01:59,960 --> 00:02:04,523 you have to write that as X squared plus Y squared and minus 1 equals 0. 31 00:02:09,030 --> 00:02:12,474 And then it turns out the optimal value, so, the 32 00:02:12,474 --> 00:02:15,918 maximum value of f, the biggest or smallest I can 33 00:02:15,918 --> 00:02:19,614 make f, subject to these m constraints, is going to 34 00:02:19,614 --> 00:02:23,980 occur at one of the critical points for this function here. 35 00:02:31,430 --> 00:02:33,620 Suggest a little terminology to get us started. 36 00:02:33,620 --> 00:02:39,108 This function, capital F, so is a function of n variables 37 00:02:39,108 --> 00:02:44,320 and the m lambda values is called the Lagrangian. 38 00:02:48,290 --> 00:02:52,706 And the vector Lambda that has Lambda 1 through Lambda 39 00:02:52,706 --> 00:02:58,930 m as it's components is called the Lagrange multipliers vector. 40 00:02:58,930 --> 00:03:02,092 So each one of these things is called a Lagrange multiplier, 41 00:03:02,092 --> 00:03:05,850 and then the whole vector is called the Lagrange multipliers vector. 42 00:03:09,250 --> 00:03:13,060 And then there's one necessary condition for this meth-, method to work. 43 00:03:14,770 --> 00:03:16,945 So if I rename the inputs to the 44 00:03:16,945 --> 00:03:22,560 original function, to the objective function, lowercase f. 45 00:03:22,560 --> 00:03:25,679 I'm going to put those in a vector and just call that x. 46 00:03:29,410 --> 00:03:37,090 And then, if I let g of x just be this vector valued function. 47 00:03:37,090 --> 00:03:41,118 So remember, again, when I put parentheses around a 48 00:03:41,118 --> 00:03:44,690 row, what I really mean is a, a column vector. 49 00:03:44,690 --> 00:03:49,110 So this is a column vector that has G1 as its first element. 50 00:03:49,110 --> 00:03:50,980 G2 as it's second element, and so on, 51 00:03:50,980 --> 00:03:53,620 so it's a vector-valued function of the constraints. 52 00:03:56,090 --> 00:03:59,080 Then the gradient, and now remember that, so if I have 53 00:03:59,080 --> 00:04:03,033 a vector-valued function, the gradient's now going to be a matrix. 54 00:04:03,033 --> 00:04:08,230 The gradient of this vector-valued function, g(x). 55 00:04:08,230 --> 00:04:11,558 Has to have full rank at any point where 56 00:04:11,558 --> 00:04:15,750 the constraint g of x equals zero is satisfied. 57 00:04:18,270 --> 00:04:24,720 So that means you have to figure out what this gradient matrix looks like. 58 00:04:24,720 --> 00:04:28,090 Pick a point that satisfies the contraint. 59 00:04:28,090 --> 00:04:30,756 So, pick a point that satisfies g of x 60 00:04:30,756 --> 00:04:35,370 equals zero, then evaluate the gradient at that point. 61 00:04:35,370 --> 00:04:38,106 So that will give me a matrix now just of numbers, because 62 00:04:38,106 --> 00:04:42,620 it's sort of a matrix of functions, evaluated at one particular point. 63 00:04:42,620 --> 00:04:43,874 You can do elimination 64 00:04:43,874 --> 00:04:47,229 on that matrix, and you'd end up with a full set of pivots. 65 00:04:48,770 --> 00:04:52,775 So if that condition holds, then I say that the rank of 66 00:04:52,775 --> 00:04:57,314 the gradient of this vector value function g is equal to m, so 67 00:04:57,314 --> 00:05:01,230 it's this matrix is going to have m rows, and so in each 68 00:05:01,230 --> 00:05:05,930 row, I'm able to find a pivot, that means I have full rank. 69 00:05:08,880 --> 00:05:11,008 And so I said oh you can do that for one point but 70 00:05:11,008 --> 00:05:14,990 actually for this condition to hold you have to do it at every point. 71 00:05:14,990 --> 00:05:21,095 So this this can sometimes be pretty problematic to to do 72 00:05:22,470 --> 00:05:26,990 Most of the time I don't bother checking this, unless something really goes wrong. 73 00:05:26,990 --> 00:05:29,240 And then you wonder, why is this not working. 74 00:05:29,240 --> 00:05:32,180 You know, oh, maybe it's the, the condition isn't, isn't being held. 75 00:05:35,170 --> 00:05:35,670 Okay. 76 00:05:37,440 --> 00:05:42,790 So the Lagrangian is going to be a function that has N plus M variables, so. 77 00:05:44,110 --> 00:05:48,710 X is this is the argument for the, for the objective function. 78 00:05:48,710 --> 00:05:51,490 Little f. Which was a function of n variables. 79 00:05:51,490 --> 00:05:54,590 And then I'm also going to have m Lagrange multipliers. 80 00:05:54,590 --> 00:05:57,870 So, the Lagrangian has n plus m variables. 81 00:05:58,960 --> 00:06:01,540 And I need to compute the gradient of this thing. 82 00:06:01,540 --> 00:06:02,540 Because. 83 00:06:02,540 --> 00:06:07,603 I need to find the critical points, because what I'm after is a critical 84 00:06:07,603 --> 00:06:10,591 point of the Lagrangian will correspond to 85 00:06:10,591 --> 00:06:14,580 an extreme value of, of my optimization problem. 86 00:06:16,260 --> 00:06:18,554 So I can think about doing this in two steps, 87 00:06:18,554 --> 00:06:21,139 and it turns out this, this step is pretty easy. 88 00:06:23,330 --> 00:06:28,940 So, I'll write d sub x of the lagrangian. So, this will be 89 00:06:28,940 --> 00:06:33,680 the gradient, but I'm only going to take partial derivatives with respect to x. 90 00:06:34,730 --> 00:06:36,350 And then, this will be the gradient 91 00:06:36,350 --> 00:06:39,320 with the partial derivatives with respect to lambda. 92 00:06:39,320 --> 00:06:43,627 And since this should just be one long row vector, so it's a row vector 93 00:06:43,627 --> 00:06:46,328 because I'm using the square brackets here, so 94 00:06:46,328 --> 00:06:48,372 I mean I want everything to stay in 95 00:06:48,372 --> 00:06:50,562 a row and the first n elements will be 96 00:06:50,562 --> 00:06:54,810 these partial derivatives with respect to the x variables. 97 00:06:54,810 --> 00:06:56,350 And the last m elements will be the 98 00:06:56,350 --> 00:06:59,389 partial derivatives with respect to the Lagrange multipliers. 99 00:07:02,430 --> 00:07:05,580 And now let's remember what the Lagrangian looks like. 100 00:07:05,580 --> 00:07:10,116 And now if I want to take the partial derivative of the Lagrangian 101 00:07:10,116 --> 00:07:15,070 with respect to one of the x variables, what I'll end up with. 102 00:07:15,070 --> 00:07:18,529 Because the differentiation is a, is a linear operation. 103 00:07:19,710 --> 00:07:23,310 So the derivative of a sum is the sum of the derivatives. 104 00:07:23,310 --> 00:07:25,970 So I'll have one derivative. 105 00:07:25,970 --> 00:07:27,357 So if I'm taking the, 106 00:07:27,357 --> 00:07:30,350 the partial with respect to xj, I'll end up with 107 00:07:30,350 --> 00:07:33,750 the partial derivative of little f with respect to xj. 108 00:07:33,750 --> 00:07:35,100 So that's my first term here. 109 00:07:37,530 --> 00:07:40,420 And then for lambda 1, I'm going to end up 110 00:07:40,420 --> 00:07:43,990 with lambda 1 times the partial derivative of g 1 111 00:07:43,990 --> 00:07:47,135 with respect to x j, plus lambda 2 times the 112 00:07:47,135 --> 00:07:51,120 partial derivative of g 2 with respect to x j. 113 00:07:51,120 --> 00:07:55,600 So I can actually just move that differentiation operation across the sum. 114 00:07:55,600 --> 00:07:57,425 And what I'll end up with. 115 00:07:57,425 --> 00:08:02,710 Partial derivative of f with respect to xj, plus the sum from 1 to m. 116 00:08:02,710 --> 00:08:05,248 So summing over each one of these 117 00:08:05,248 --> 00:08:09,854 Lagrange multipliers terms, of the Lagragne multiplier 118 00:08:09,854 --> 00:08:15,900 so lambda i times the partial derivative of constraint i with respect to xj. 119 00:08:19,350 --> 00:08:22,660 And then on the right hand side, this turns out to be quite a bit easier. 120 00:08:22,660 --> 00:08:26,052 So when I'm taking the partial derivative with respect to each 121 00:08:26,052 --> 00:08:29,828 of the lambdas, the objective function doesn't have a lambda in it, 122 00:08:29,828 --> 00:08:33,220 so this the derivative of this, the partial derivative of this 123 00:08:33,220 --> 00:08:36,400 with respect to anyone of the lambdas is going to be zero. 124 00:08:38,160 --> 00:08:43,250 And also, the g doesn't have any lambdas in it. 125 00:08:43,250 --> 00:08:44,456 It's also a function 126 00:08:44,456 --> 00:08:46,890 just of the, the x variables. 127 00:08:46,890 --> 00:08:50,102 So the only place the Lagrange multipliers are going 128 00:08:50,102 --> 00:08:52,413 to show up are just lambda i to the 1. 129 00:08:53,970 --> 00:08:58,195 And so when I'm taking the partial derivative with respect to lamda i, every 130 00:08:58,195 --> 00:09:01,530 one of these is going to be equal to zero, except for lamda i. 131 00:09:02,620 --> 00:09:05,630 And so what I end up with is just a gi of x. 132 00:09:13,500 --> 00:09:18,610 So the gradient of f is going to be these partial derivatives with respect to x. 133 00:09:21,300 --> 00:09:25,660 The gradient of g is going to be this, so it's a little tricky to see. 134 00:09:25,660 --> 00:09:31,250 But the, there, there's n columns so x1, x2, all the way up to xn. 135 00:09:32,250 --> 00:09:35,800 And then there's m rows. So it's a m by n matrix. 136 00:09:37,650 --> 00:09:40,658 And then, each row is just going to be the gradient. 137 00:09:40,658 --> 00:09:45,110 Of g, i of x. 138 00:09:45,110 --> 00:09:46,406 So here, first row is 139 00:09:46,406 --> 00:09:50,330 the gradient of g1, second row is the gradient of g2 and so on. 140 00:09:50,330 --> 00:09:54,470 And so I end up with this matrix being the gradient of a vector valued function. 141 00:09:57,510 --> 00:10:00,840 So now I can express the, the sum. 142 00:10:00,840 --> 00:10:06,582 And the second term using matrix notation, so I had this sum of lambda 143 00:10:06,582 --> 00:10:11,829 i times the partial derivative of gi which respect to xj and so if 144 00:10:11,829 --> 00:10:17,373 I look at a column here, if I pick a particular j, so suppose I pick j 145 00:10:17,373 --> 00:10:22,850 equals 2, that's going to be the second column of this matrix. 146 00:10:24,640 --> 00:10:30,404 So, this sum is just going to be equal to lambda times 147 00:10:30,404 --> 00:10:36,440 the second column of this matrix. So that's what I mean when I say. 148 00:10:36,440 --> 00:10:39,449 Matrix sub j, I mean the jth column so if I put a little two down 149 00:10:39,449 --> 00:10:41,691 here, I'll be talking about the column back 150 00:10:41,691 --> 00:10:44,230 there, that's the second column of this matrix. 151 00:10:45,340 --> 00:10:50,540 And I can write this sum then as lambda transposed times 152 00:10:50,540 --> 00:10:54,619 dot specific so the jth column of this matrix. 153 00:10:55,720 --> 00:10:58,710 That's going to make my notation a little bit easier to handle now. 154 00:10:58,710 --> 00:11:00,952 I don't have to write out all of these partial 155 00:11:00,952 --> 00:11:04,030 derivatives, I can just write it out in terms of gradients. 156 00:11:07,150 --> 00:11:13,020 So it follows that my gradient for the whole Lagrangian now. 157 00:11:14,150 --> 00:11:17,972 This is going to be the gradient of f, plus this 158 00:11:17,972 --> 00:11:21,892 thing that I just worked out up here, and so I'm 159 00:11:21,892 --> 00:11:26,498 going to be able to do this plus operation because the, the 160 00:11:26,498 --> 00:11:30,919 gradient of f is going to be a row vector with n elements. 161 00:11:33,610 --> 00:11:35,830 And then lamba transpose. 162 00:11:35,830 --> 00:11:38,490 That's also going to be a row vector with n elements. 163 00:11:38,490 --> 00:11:41,178 And I'm going to multiply that by an n by n 164 00:11:41,178 --> 00:11:45,352 matrix, so it's going to stay a row vector with n elements. 165 00:11:45,352 --> 00:11:46,756 So this term is a row vector with n 166 00:11:46,756 --> 00:11:49,140 elements; this term is a row vector with n elements. 167 00:11:53,560 --> 00:11:57,032 And so I can do the sum just by doing the summation element wise, and 168 00:11:57,032 --> 00:12:01,050 I end up getting exactly what I had in the sum formula in the previous slide. 169 00:12:04,320 --> 00:12:06,820 And then the derivatives for 170 00:12:09,030 --> 00:12:10,977 For the part of the Lagrangian that just 171 00:12:10,977 --> 00:12:14,340 corresponds to taking derivatives with respect to lambda, they 172 00:12:14,340 --> 00:12:16,995 just end up being the constraints again, so remember 173 00:12:16,995 --> 00:12:19,560 g was a vector valued function of the constraints. 174 00:12:20,900 --> 00:12:23,120 So if I take g transpose, that's just going 175 00:12:23,120 --> 00:12:25,880 to be that same vector but put into a row. 176 00:12:25,880 --> 00:12:29,280 And I have to do that because this whole thing has to end up being a row. 177 00:12:29,280 --> 00:12:34,152 So I end up with a row vector here of n elements, and a row vector here 178 00:12:34,152 --> 00:12:39,807 of m elements, and so when I put those two next to each other, I end up with this 179 00:12:39,807 --> 00:12:45,350 row vector with n plus m elements that's the gradient of the Lagrangian.