Transcription
Welcome back to my series of videos on mathematics for economists. In this video, I'm going to discuss why, when we consider optimization problems given inequality constraints, the Lagrange multiplier lambda is never negative; it's positive or equal to zero. Whereas, if we consider optimization problems given equality constraints, the Lagrange multiplier can be either negative or positive.
I was approached by a student with this question, and the intuition the student had looked something like this. I'm going to push a graph into the picture. The student said, "So let's consider a situation like this where we have an objective function that is given by, say, this plane here, and we have a constraint that is given by, say, this parabola. Then clearly we can see geometrically that the gradient of F, which is pointing in this direction—the steepest descent—is a different direction from the gradient of the constraint, it's called G, given by this parabola, which is the direction of steepest descent somewhere in this direction. So how come that if we consider this as an inequality problem where we want to maximize F, the objective function given by this plane—so this is actually 3 times X plus 4 times Y—so we want to maximize 3 times X plus 4 times Y given that all points X and Y should shall lie underneath or on this surface of this parabola? That's a good question. Let me sit down and come back with a good answer."
So I decided to make this video because this is sometimes a source of confusion, and it's actually kind of a subtle point. So let's try to understand why: if we understand the situation as maximization given an inequality constraint, we're still going to see a positive Lagrange multiplier; whereas, if we actually phrase this problem as an optimization problem given an equality constraint, we will see a negative Lagrange multiplier. So let's get this straight. Let's begin with the situation of an equality constraint. Let's say that we want to maximize f(x, y), which is 3x + 4y, such that the constraint -x + 1/2 squared - y + 1/2 squared + 2 = 0. This is our constraint G(x, y). Okay, and we again consider first the equality case, and then we will see that indeed our intuition is correct. Let me graph the situation. No, indeed our intuition is correct; lambda is going to be negative because we're looking at all points x and y that lie on this circle here—all points x and y that lie on the circle. Yeah. Now we want to maximize 3x + 4y, which is this plane here, such that we only use points from the circle. And of course, we expect we're going to pick a point somewhere around here because that is going to correspond to the highest possible value of 3x + 4y that we can achieve. And in that point, we're going to have a gradient for G, for the constraint function, which is the parabola, pointing in that direction, and a gradient for the objective function, which is this plane here, pointing in that direction. I'm not going to point in the same direction, but opposite directions. So let's confirm this analytically.
So we proceed as usual. So again, the statement of the Lagrange multiplier theorem is that the gradient of f is given as a multiple of the gradient of G. The gradient of F here, of course, is (3, 4), and the gradient of G is (-2x + 1) with respect to X and (-2y + 1) with respect to Y. The Lagrange auxiliary function is given by the objective function 3x + 4y - lambda times the constraint -x + 1/2 squared - y + 1/2 squared + 2. And we can consider the first-order conditions, which are: partial derivative with respect to X equal to 0; this would be 3 + lambda times (2x + 1) shall be equal to 0; partial derivative of the Lagrangian with respect to Y, which is 4 + lambda times (2y + 1) equal to 0. So from this, we get two different expressions for lambda: one is -3/(2x + 1) and the other is -4/(2y + 1). And finally, the derivative with respect to lambda, which just repeats the constraint: -x + 1/2 squared - y + 1/2 squared + 2 = 0. Now again, we are in the situation that we have a system of three equations and three unknowns: X, Y, and lambda. And so, since these equations are nonlinear, we just proceed by repeated substitution until we boil the whole situation down to one equation and one unknown, which hopefully we can solve. So let's start with the last one. So we write y + 1/2 squared = 2 - x + 1/2 squared, so y = +/- the square root of 2 - x + 1/2 squared - 1/2. Now we can plug this into, say, the second equation—to do this one here—so 4 + lambda, now we use because we're using the second equation; we're using the lambda from the first equation, so + lambda = -3/(2x + 1), and then for y here we replace with the expression that we just found. So we write +/- 2 times y, so 2 times the square root of (2 - x + 1/2 squared) - 1/2. This should be in parentheses, so this is -1 -1, and let me get +1 because this is 2y + 1, cancels, and the whole thing must be equal to 0. All right, so we can -3/(2x + 1) +/- 2 squared. I take the 2 inside, so this is 8 - 2(x + 1/2) squared goes away, equal to 0. Okay, so let's multiply through with 2x + 1, so we get 8x + 4 - 3 times that's minus the square root of 8 - 2(x + 1/2) squared = 0, so +/- the square root of 8 - 2(x + 1/2) squared = 8/3x + 4/3. I didn't make a mistake; please check, and if I did, then please comment, and I'm going to correct things more or less without accident here, equal to 8x squared. Okay, so again we have one, we have cheap one equation, one unknown, so we're just working this thing until it gives away what X is. So okay, so we have two polynomials of second order going on here. We can bring them over to the other side, so this is equal to the other side: 0 = just multiply 8 - 4(x + 1/2) squared = 64/9x squared + 64/9x + 16. Okay, so now I bring it over to the other side, so I get 0 = 60x squared + 100/9x - 79. So now I multiply through by 9/100 and I get x squared + x - 0. Okay, we can solve x1 & x2 = -this and 25 - 18/5, so -candidate points here -5 +/- 2 times the square root of 18 divided by 10, or 2 times the square root of 18 - 5. Numerically this is about 0.3485 and this is -. Okay, so these are my candidate points for X. I can go back into my original equation here, into this one, and then you can convince yourself that that x1 = 0.3, or roughly equal to 0.845, solves the plus case of the square root, and x2 roughly equal to -1.384534 hit 5 gives me we had y - x squared x squared - 1/2 here, but then we square half, so we got two candidates, x1 and y1, because x1 solved the positive card, so x1 corresponds to y1. This is roughly 0.34853485 and 0.6314. And if we evaluate the objective function 3 times x1 + 4 times y1, we find that this is roughly 3.57. The other candidate point is x2, y2, because remember x2 solved the negative card that corresponds to y2. This is give or take -1.3485 and -1.663, and these are negative, so I can already see that that 3x2 + 4y2 is not going to do anything that's better for me. Here's -10.571 if you punch it into your calculator, and that's of course not maximizing F. The gradient of G in the maximum point that we found indicates maximum. The gradient of G in this point 0.345634 is given by -2x -1, right, so -2(0.3485) - 1 - 2(0.6314) - 1 is of course negative, and it should be equal to lambda times 1/lambda times the gradient of F, so we can already see lambda must be negative: this -1.6 -2.26, and we relate this to delta F which is 3/4, and we see that lambda -1.7678. Okay, let's pause you because we solved the problem given an equality constraint, right, and we found that if for the equality constraint indeed the geometric intuition here, into the picture, the geometric intuition here that the gradient of f and gradient of G point in opposite directions, and therefore lambda is negative, must be true. Fine. Now, well, which point did we find? I put a sphere into the points. Oh, look at it from above. This is the point on the circle, as expected. It is on this side where we can achieve the highest value of the objective function 3x + 4y and this on this plane here. You can see this corresponds to what we expected. Good. But now we want to understand how come that if we now pose this problem as a maximization given an inequality constraint, that lambda then must be positive, puzzling me. All right, so for that we have to phrase the whole problem as an inequality constraint. So I'm going to raise the graph and just plot the original situation again. Here we go. So now, if we understand this as maximizing 3X + 4Y values on this plane such that X and Y comes from underneath or on the surface of this parabola, how come lambda must be positive? In some sense, the answer is very easy; that's why I can make a video of it. So let's write it down as a maximization problem given an inequality constraint. We're still supposed to maximize with respect to x and y the function f(x) f(x, y) = 3x + such that here comes - here's the question: how do I phrase inequality if the points are supposed to come from underneath or on this function surface? Then I'm going to, just by geometric intuition, I'm going to end up somewhere here. I guess it's kind of hard to say because this is a two-dimensional projection of a three-dimensional object, but but somewhere around there I'm going to end up because there is the highest point of the function 3x + 4y on the surface. Then I'm going to phrase my constraint that 3x + 4y, which is the point on the surface, is less than or equal to now you see where this is going: -x + 1/2 squared - y + 1/2 squared + 2, right, because you want to find the highest point 3x + 4y such that 3x + 4y is still underneath or on the surface of the constraint, and that means that 3x + 4y is less than or equal to the surface of the constraint. Now you see what's going on because now we have to write 3x + 4y. I know we take the negative of the right-hand side over to the left-hand side; we get +x + 1/2 squared + y + 1/2 squared - 2 less than or equal to 0. Under standard formulation, I see. Okay, of course, this here now is our G(x, y), and the inequality formulation, the gradient of G is of course going to point in the opposite direction of the one that was pointing in in the equality situation. All right, so in some sense we're done here, and we we have found the reason, but that's just for completeness, calculate this through because the inequality constraint of course also looks a bit different. So our Lagrange auxiliary function looks a bit different; we get 3x + 4y - lambda times the constraint, which is now 3x + 4y + x + 1/2 squared + y + 1/2 squared - 2. And then I get for the first-order conditions, Kuhn-Tucker conditions, gradient with other partial with respect to x is 3 - 3lambda - lambda times (2x + 1), which is equal to -2lambda x - 3. This be equal to 0. The partial with respect to y: 4 - 4lambda - lambda times (y + 1). Ya know it's positive, equals -2lambda - 5 + 4 be equal to 0. And then the complimentary slackness condition is lambda times the constraint 3x. Good. The gradient of this new constraint G(x, y) is 3 + 2x + 1 with respect to X and 4 + 2y + 1 with respect to Y, which is 2x + 4, and the gradient of F, of course, still... yeah. So again we solve. So from from the first give these numbers 0 1 2 3, we get that lambda = 3/(2x + 4)/5. We need to solve for x and y, so what I'm doing is I again use the use constraint and... yeah, I just multiplied the whole thing. I think I see, I just just what is this? This is 3x + 4y + x squared + x + 1/4 + y squared + y + 1/4 - 2 be equal to 0. So this is x squared + y squared + 4x + 5y - 3/2 = 0. Now I'm using using the first condition, but I'm using the lambda expression from 1, so I'm replacing lambda = 3/(2x + 4) in 2. So what does that give me? That gives me -2 times 3/(2x + 4). Of course, I could've done it the other way; it doesn't matter. This is just the way I prepared it here so that I don't get confused myself along the way: 2x + 4 + many ways each room. We just have to solve the system of equations whichever way you want to do so. After cleaning this up a bit, you get -6y - 15x = 60. So let's write this as a it's a second-degree polynomial, so there's x squared + 4x + and now all the terms with y: y squared + 5y - 3/2 = 0. So this we can solve and we get of course a function in Y: +/- i square root of 4 - y squared + 5y, and this gives us -6y that's 8x - 6y + 8x - 2 sending into this equation -2 +/- +/- 4y squared = 6y + 15. So we square the whole ordeal: 64 - y square = 61 + 15 squared: 256 - 64. Again, please do let me know in the comments if I'm making a mistake here. Then we're going to fix that at the point geometrically, and it'd look reasonable, which gives us the polynomial y squared + 0, or y squared + 5y - 27 = 0, which gives us the points y1 & y2 = numerically give or take 0.24 - 3 - 5. What's the x-axis? This equation on the positive part, so okay, I get two kinds of points for y. So again, I can go into condition here, then I convince you can convince yourself that I can convince myself that y1 solves the positive, y2 solves the negative, the negative part here, and so I get in x1 that then corresponds to y1, the positive part, -2 + the square root of 4 - y square my + 5y - -3/2, so that's - + 7 squared - 5 square... 100 - 3/2, the whole thing in parentheses, and the whole thing draw an ugly square root here, but just say that this is this is numerically, as you can check, roughly equal to 0.0567, and it's true then accordingly the negative square root: ugly 4 - -5/2 - square root of 75 - divided by 100 squared + 5 times -5/2 - square root 7 5 2 parenthesis square root, and this is numerically equal to roughly -4.67. Well, okay, so now we have candidate points x1, y1 and x2, y2. Then we found relations for lambda here. Something something happened here; I must have hit the back button a few times too aggressively. So this was 4/(2y + 5), and here I had condition 3... so here I found two expressions for lambda, which of course now both must hold; would express the next and why they must both be correct. So let's check what lambda is for our candidate points here. So so 3/(2x1 + 4) is roughly equal to 0.7293, and 4/(2y1 + 5) is equal to also 0.7293, and lambda is positive, so this is good. What about x2? x2 is negative, so we can already and it's largely negative: 2 times -4.0567 + 4, which is x2 - 0.723, and 4/(2y2 + 5) there's also negative 0.7293. So now, by the Kuhn-Tucker complimentary slackness condition, lambda must be positive or equal to zero, so here we have a contradiction. So our only candidate point is 3x1 x1 + y1, so the projective contracted function evaluated at this point is 1.3. y2 x2 we get a negative number: 3 times -5 points + 4 times -4 point something, it's obviously not gonna give us a higher volume. Yeah, so so here we see that indeed lambda is positive, which geometrically we have now of course expected. So let's look at the geometric situation again. So now I'm going to plot this optimal point in our picture, and not surprisingly, I was a bit off with my guess that somewhere somewhere up front, it's actually surprisingly further back, but again that's because of the projection of three dimensions onto onto to, but you see clearly this corresponds to our intuition. This point has to lie from this from this angle. It also looks quite natural. So you see that indeed working with the same constraint function in the equality case and in the inequality case gives you two different signs of lambda, and the way to think about this is if we go back, if we go back to the formulation of our constraint function here, then we see this is exactly the reason. Of course, you could ask, well, what if I now oppose the constraint function with opposite signs open alright +x too many again, or my program is just dying on me. Anyway, what if I if I opposed and the other sign here, if I now write on the right-hand side +x + 1/2 squared + y + 1/2 squared - 2, and then bring it over to the other side, and then I'm again in the situation where where I have apparently a problem with my gradient, and of course we can we can very quickly graph that situation -G. If we want to if we want to maximize, of course, this would not pose a constraint, so we could just pick 3x + 4y infinitely large and so on, but this I hope clarifies why in inequality problems—inequality problems, picture again—the Lagrange multiplier is always positive, even in a geometric situation where our intuition at first pass is going to tell us this might be negative. Now, so the reason is the formulation of the constraint inequality case. I hope this video helped you in understanding the optimization problems with respect to equality and inequality constraints, and thank you for watching.