Transcription
Welcome back to my series of videos on mathematics for economists. In this video, I'm going to go through two examples for optimization subject to inequality constraints. So I'm going to specify the KKT conditions, identify a set of candidate points that satisfy the KKT conditions, then evaluate the objective function on the set of points in order to decide which one actually yields the highest value of the objective function. Then I'm going to check sufficiency, and I'm going to check constraint qualification.
Yeah, so let's start with this example here where we have a maximization problem for a linear objective function, 3x + 4y, such that two constraints be satisfied. One is that the vector of choice variables x and y have length less than or equal to 2, which means that x² + y² is less than or equal to 4, and the second constraint is that -x be less than or equal to -1, which is the standard form for x larger than or equal to 1.
So we begin with specifying the Lagrange auxiliary function. So this is L(x, y) given by the objective function, 3x + 4y - (first Lagrange multiplier) * (the left-hand side of the constraint - the right-hand side of the constraint), and likewise for the second constraint. The way we have specified the L auxiliary function now is that the Lagrange multipliers must be positive numbers. If we arrive at a negative Lagrange multiplier, it does not satisfy the KKT conditions, and we have a contradiction, so to say.
Okay, then we can list the four resulting KKT conditions, and I'm just going to number them in this fashion so that I can refer to them as we go along. The first two involve the partial derivatives of the Lagrange auxiliary function with regard to the choice variables x and y and simply set the first derivatives equal to zero. So the one with regard to x is 3 - 2λ₁x + λ₂ = 0, and the second is the partial derivative of L with respect to y, which is 4 - 2λ₁y = 0. These are identical to the conditions you would write down under equality constraints. Then we get to the complementary slack conditions, which are different from the case of equality constraints.
Complementary slack says that the Lagrange multiplier times the slack in the constraint—which, for the first one, is x² + y² - 4—the product with the Lagrange multiplier must be equal to zero. This means that if there is slack in the constraint, that is to say x² + y² is strictly less than 4, if there is slack in the constraint, then x² + y² - 4 is strictly less than zero. In this case, economically you're not exhausting your resources, which means that imposing this constraint does not cost you anything, so you're not incurring opportunity costs, so your shadow price is equal to zero. So that the product of these two numbers, zero with something strictly negative, is equal to zero. Or the other way around, if the constraint is not slack but is active or binding, so that the slack is equal to zero, then the Lagrange multiplier is going to be strictly positive because you're essentially operating at capacity, and imposing the constraint is actually costing you in terms of opportunity costs. If you were to increase your capacity, so to say, from four to five to six units, you would, for every unit gain, λ₁ units in your objective function. Yeah, so this is complementary slack, and we get the corresponding expression for the second constraint, of course, complementary slack.
So we have, just as in the case of optimization under equality constraints, four equations and four unknowns, but these equations are nonlinear, so we cannot solve this by methods of linear algebra, and we can also not say much about the existence of solutions or how many there are. We just kind of have to work our way through. Working our way through means that, in some sense, we keep substituting until we arrive at, hopefully, one equation and one unknown that can be solved in an analytically tractable fashion, and then we can work our way backwards by plugging in the values that we get and hopefully solve the system of equations this way. Sometimes one is lucky enough that one can say, from looking at this equation, something about some of the involved variables, irrespective of the configuration of activity and inactivity of the constraints, but it is certainly a safe way to just go through all the combinations there are.
So here, in this case where we have two constraints, we can look at four different cases: both constraints are active, both constraints are inactive, constraint one is active, constraint two is inactive, or constraint one is inactive and constraint two is active. So with two constraints, this is a still doable task. Of course, if there are more than two constraints, this can become a bit confusing quite quickly, and then we are hopefully in a situation where we can solve for some of the variables without having to go through all these cases. But here we can certainly do it, and we can be certain that we're not going to miss anything if we go through all possible cases.
So let's do this, and let's begin with the case where both constraints are binding; both constraints are active. What does this mean? This means that x² + y² = 4, and this means that λ₁ is strictly positive, and it also means that x = 1; the constraint is binding, the second one, and therefore the second Lagrange multiplier is also positive. Now if x = 1, then x², still 1 + y², is equal to 4 from the first constraint, and we get that y² = 3, and therefore y is equal to the positive or the negative square root of 3. So we have two possible cases to consider. Let's begin with the case where y is equal to the positive √3. Then I look at condition number two, which is 4 - 2λ₁y = 0, and now I have y = √3, so I get 4 - 2 * √3λ₁ = 0, and from that I get a value for λ₁, namely 2/√3, which is a positive number, so that's certainly good. With this, I go into the first condition, which reads 3 - 2λ₁x + λ₂ = 0. Now I have x = 1 and I have λ₁ = 2/√3, so I have 3 - 4/√3 + λ₂ = 0, and from that I get that λ₂ = 4/√3 - 3, which unfortunately is a negative number, so this is not satisfying the KKT conditions, and I am not getting a candidate point from this case.
Then I move on to the second subcase where y is equal to the negative square root of 3, and I can see now that, from if I proceed the same way from the second condition, for -2λ₁y, now λ is—now y is -√3, so this is plus 2 * √3λ₁ = 0, I get right away that λ₁ now is a negative number, so this is also not getting me anywhere, so no candidate points here. We move on to the second possible configuration where constraint one is binding, active, and constraint two is slack, not binding, inactive. This means that x² + y² = 4, λ₁ therefore strictly positive, x > 1, so constraint number two is slack, and λ₂ is therefore equal to zero.
Now I can certainly write, from the first constraint, I can write x as plus or minus the square root of 4 - y², and since x is supposed to be larger than one, I can also eliminate the negative case here, so I only need to consider the positive case. So with this, I go into the first condition, 3 - 2λ₁x = 0, because λ₂ = 0. I can thus write x = 3/2λ₁. I'm going to use this later. I can also write, because I have x = the positive √(4 - y²), I can also write 3 - 2 * √(4 - y²) * λ₁ = 0, and this gives me an expression for λ₁ in terms of y, namely 3/2 * √(4 - y²). Now I go into the second condition, which reads 4 - 2λ₁y = 0. Now I plug in λ₁, so I get 4 - 3y/√(4 - y²) = 0. I multiply the equation through by the √(4 - y²), so I get 4 * √(4 - y²), and then I have -3y = 0. So I bring this over to the right-hand side, so I have positive 3y here. Now I square the whole affair: 16 * (4 - y²) = 9y², or 64 - 16y² = 9y², or 64 = 25y², or y = plus or minus 8/5. So this is the first time that I am arriving at one equation and one unknown, and I can actually solve it. So I have my first numerical value for one of my unknowns. Well, actually, we have already assumed that λ₂ = 0, so by definition of the configuration I'm looking at here, I have λ₂ already, but this is the first one that I could calculate by repeated substitution in my system of equations here. Yeah, so I get two candidate values for y. Now I'm going into my expression for λ₁ that I had derived here, 3/2 * √(4 - y²), and since this is y² that is entering, I don't need to worry about the plus or minus 8/5, so I get that λ₁ = 3/2 * √(4 - now (8/5)²). This is 64/25; that's the square root, and this is okay. So now what is the radicand? That's 4 * 25 is 100, so I have 100/25 - 64/25, that is 36/25, and the square root of 36/25 is 6/5, so I get 3/2 * 6/5, and this is 9/5. If we think about it, this is a positive number, so that's good. Now I can go and calculate x from this expression that I arrived at upstairs here, so x = 3/2λ₁, so this is 3/2 * 9/5 or 6/5. Yeah, so I have, through repeated substitution, arrived at one equation and one unknown, solved, and then I went back and plugged in with these solved values and could work my way backwards, and now I have all four values. I have x = 6/5, I have y = 8/5 and -8/5, and I have λ₁ = 5/4, and I have λ₂ = 0. So I get two candidate points from this. These are (x, y) = (6/5, 8/5) and (x, y) = (6/5, -8/5). Good. Two cases are covered; two to go.
Case number three: constraint one is inactive (is slack), constraint two is active (binding). This means that x² + y² < 4, which means that λ₁ = 0, and this means that x = 1, which means that λ₂ is strictly positive. Go into constraint two, which says—going to condition two, which says that 4 - 2λ₁y = 0. Now λ₁ = 0, which means 4 = 0. If this is not a contradiction, then I don't know what is, so no candidate point from this case. Four: both constraints are inactive. This means that x² + y² < 4, λ₁ therefore zero, x is strictly bigger than one, λ₂ therefore zero. I can go into condition two, since λ₁ = 0. This is going to give me the same contradiction as the other case, as the case before, and so I also get no candidate points from this case. So I am left with the two candidate points that I found. So now I can go ahead and check the maximality of the candidate points by evaluating the objective function on these points. So I'm interested in the function value of the objective function for x = 6/5 and y = 8/5, which is 3 * 6/5 + 4y, and this is equal to 18/5 + 32/5, so this is equal to 10. And then I can already anticipate I'm not going to get anything from the negative value for y because all I'm going to do is—here I'm going to subtract this term, and that's certainly not going to maximize the function—so I get 18/5 - 32/5 here, so this is -14/5, certainly smaller than 10. So this is my candidate for a maximum.
Let's check sufficiency. Here we answer the question: is the Lagrange auxiliary function concave if we understand it as a function of x and y? Then the optimum candidate—and this means, since we're going to understand the Lagrange function as a function of x and y, we're not going to plug in x = 6/5 and y = 8/5; it's going to be a consideration of the function in x and y, but we're going to plug in the values for the Lagrange multipliers that we found in this point—and this is λ₁ = 5/4 and λ₂ = 0 because constraint two was slack. So we get that the Lagrange auxiliary function for these specific values of λ₁ and λ₂ is equal to 3x + 4y - λ₁, so -5/4 times the right-hand side—the left-hand side of the constraint minus the right-hand side of the constraint—so in parentheses (x² + y² - 4). And if we multiply this out, we get -5/4x² - 5/4y² + 5. Yeah, so these are negative parabolas in x² and y², and we're adding a linear term 3x and 4y. This still renders the function concave in x and y, and this means that we are indeed looking at a maximum, so (x, y) = (6/5, 8/5) is a maximum.
Last thing: the last thing that remains to be checked is constraint qualification. We can quickly check that constraint qualification holds in the maximal point. So the objects to consider are the gradients of the constraint functions. So since the constraint function G₁ is given by x² + y², the gradient is 2x (partial derivative of x² + y² with respect to x) and (partial derivative of x² + y² with respect to y), and the gradient of the second, which is -x ≤ -1, with respect to x (-x, derivative with respect to x, that's -1), and y doesn't figure, so it has a coefficient of zero. So irrespective of the value of x and y, the gradient of the second constraint is (-1, 0). So the gradient of the first constraint at (6/5, 8/5) is (12/5, 16/5), and the gradient of the second constraint at (6/5, 8/5) is (-1, 0). These two vectors are linearly independent, and so constraint qualification holds in the optimum. But the interesting question now is: are there points floating out there where constraint qualification does not hold and we did not pick them up in the KKT conditions, therefore, but the objective function actually assumes a maximum on those points? Yeah, this is the interesting question when one checks constraint qualification: have we missed points by focusing on the KKT conditions because constraint qualification breaks down in those points, and KKT is not able to pick them up? So this would be points where—so where could it go wrong? Check for points where the gradients of the constraint functions are linearly dependent. Yeah, what would those points be? Where are the vectors (2x, 2y) and (-1, 0) linearly dependent? Well, this would be for y = 0 and for x anything—because 2x then is something—not anything, but something not equal to zero—so x any nonzero value, because then this is certainly a multiple of -1 for a properly chosen coefficient. However, we also have to satisfy the second constraint that x be bigger than one, so it can actually not be just any x, but any x > 1, so that it satisfies the second constraint. Yeah.
Well, with that we can go into—into our—let's start from the first constraint, x² + y² ≤ 4. Now y = 0. This means that x² ≤ 4, which means that x ≤ the positive or the negative square root of 4, which is 2. Now x > 1, which means we can forget about the negative case, so we see that we have to look at—check points where y = 0 and x is in the left open interval (1, 2), yeah, because x must be must be bigger than one but less than or equal to two. So but we are only interested in maxima we may have missed. So if the objective function is given by 3x + 4y, then and y = 0, then we have just the objective function 3 * x, so we want to pick then certainly the biggest value for x, so we only need to look at the point (2, 0). This is the interesting point to check, and here f(2, 0) = 3 * 2 = 6. This is less than the value of 10 that we have already found, and so we did not find a point here that actually yielded a higher value than the one we have already identified, and from this we can then finally conclude that the pair (6/5, 8/5) is indeed the maximum such that the constraints hold. Now, end of example number one. Let's do the same thing for a second example with a maybe slightly more interesting objective function.
So let's say we have the problem: we want to maximize, with respect again to two choice variables x and y, the function given by 2x² + 3xy, and the constraints be G₁ = 12x² + y ≤ 4, and the second constraint be -y ≤ -2, or y ≥ 2. Then, just as before, we set up the Lagrange auxiliary function: objective function - (Lagrange multiplier) * (left-hand side of the first constraint - right-hand side of the first constraint) - (second Lagrange multiplier) * (left-hand side - right-hand side of the second constraint), and again λ₁ and λ₂ must here be positive. Then we can collect the KKT conditions. First two again involve partial derivatives with respect to the choice variables: with respect to x, 4x + 3y - λ₁x = 0; second, partial derivative of L with respect to y, 3x - λ₁ + λ₂ = 0. So far as inequality constraints, now complementary slack: λ₁ * (the slack is essentially standing right there) 12x² + y - 4 = 0, and finally λ₂ * (-y + 2) = 0. And again we have four equations and four unknowns: x, y, λ₁, and λ₂, and again we're going through the different configurations of activity and inactivity of the constraints, and so we begin again with the case that both constraints are binding. Both constraints are binding. This means that 12x² + y = 4, and λ₁ therefore strictly positive, and y = 2, and λ₂ therefore strictly positive. Then the first constraint says 12x² + y, which is now 2 = 4, or in other words, 12x² = 2, or x² = 1/6, or x = plus or minus 1/√6. I have two subcases to consider therefore. Let's start with the positive one. I'm looking at constraint number one, which reads—condition number one, excuse me, from the KKT conditions—condition number one reads 4x + 3y - λ₁x = 0. So 4x = 8/√6, 3y = 6, x is now +1/√6, λ₁ = 0. I get that λ₁ = (8/√6)/(1/√6) = 8, which is a positive number, so that's good news. I go into condition number two, which reads 3x - λ₁ + λ₂ = 0, so I have (3/√6) - 8 + λ₂ = 0. This means that λ₂ = 8 - (3/√6), which is also a positive number. Again, good news, and I have found a candidate point. The candidate point is (x, y) = (1/√6, 2), and the corresponding Lagrange multipliers are 8 and 8 - (3/√6). Let's look at subcase B where x takes the negative value of the square root, so -1/√6. I go into condition one again: 4x + 3y - λ₁x = 0, and now I plug in x = -1/√6, so I get -4/√6; y is still 2 because the constraint is binding, so this is still +6, and now -(-1/√6) is + (1/√6)λ₁ = 0. I get that λ₁ = (4/√6) / (1/√6) = 4, which is a positive number; good news. I go into condition two: 3x - λ₁ + λ₂ = 0, so this is (-3/√6) - 4 + λ₂ = 0, meaning λ₂ = 4 + (3/√6). The two have switched roles. This is a positive value also; good news. I have found another candidate point. This is: x and y are equal to -1/√6 and 2. So here the first case where both constraints are binding gave me two candidate points. I go into the second case: constraint one is active, constraint two is inactive. Activity of the first constraint means 12x² + y = 4, and the corresponding Lagrange multiplier is strictly positive. Inactivity of constraint two means y is strictly larger than two, and the corresponding Lagrange multiplier is therefore equal to zero. Now I write, from the constraint, that y = 4 - 12x². That's not surprising. I look at condition number two, which reads 3x - λ₁ + λ₂ = 0. This, since λ₂ = 0 now, this is just 3x - λ₁ = 0, and this means that λ₁ = 3x. Going to use that later. I go into condition number one, which reads 4x + 3y - λ₁x = 0. Now I plug in for y from here, so I get 4x + 3(4 - 12x²)—you can see what I'm doing; I'm repeatedly substituting so that I get one equation and one unknown. So here I'm shooting for one equation in x. Yeah, λ₁ I found to be 3x, so -λ₁ * x is -3x² = 0. This certainly is one equation in x that I know how to solve. Yeah, let me clean it up a bit, so I get 4x + 12 - 36x² - 3x² = 0, so I get -39x² + 4x + 12 = 0. Now I multiply through with -1/39...
x² - 8/9x - 8/3 = 0. Solving a quadratic equation, you get x₁ and x₂ = 4/9 ± √(1/4 * the coefficient of x², so 8/9² that is um 8 * 8 that's 64, 9 * 9, 81, and then minus the absolute term, so - (-8/3) = +8/3. This is 4/9 ± √(16/81 + 8/3), which is 4/9 ± √(16 + 216)/81. This unfortunately is not a nice square root, so it remains as √232/√81. Certainly √81 is 9, um but I'm left with this term. So I have again two candidate values for x. I have to consider two subcases.
Let's start with the positive one: 4/9 + √232/9. So I go into my expression for y, which was 4 - 12x². This is 4 - 12(4/9 + √232/9)². This is 4 - 12(16/81 + 8√232/81 + 232/81). After a few steps, you can convince yourself that this is equal to 200 - 4√232/81, numerically roughly 1.717. This is less than two. Since y is supposed to be bigger than two, this is actually a violation of a constraint, and so this does not give me a candidate point unfortunately, because I'm violating constraint number two.
Let's consider the second subcase where x = 4/9 - √232/9. I can evaluate λ as 3x because this is essentially the fastest way to see that I'm running into a contradiction here as well. This is 4/3 - √232/3, and this is a numerical value roughly equal to 1.52, something, so certainly bigger than 4/3. This is a negative value, so I'm running into a contradiction here as well. I don't get any candidate points out of this case, despite all my negations to solve this equation for x. So I have to move on into case number three, where constraint one is inactive and constraint two is active. This means that 12x² + y < 4, which means that the first Lagrange multiplier is equal to zero, and here activity means that y = 2 and the Lagrange multiplier is therefore strictly positive.
I go into Kuhn-Tucker condition two, which says 3x - λ₁ + λ₂ = 0. Now λ₁ = 0, and therefore I get immediately that λ₂ = -3x. I go into condition one, which reads that 4x + 3y - λ₁x = 0. Now λ₁ = 0, so I get that 4x + 6 = 0, because the constraint is active, and thus I get that x = -3/2. Then I get that λ₂ = -3 * x = 9/2. This is positive, which is good news. So I get here a candidate point because, by assumption, λ₁ = 0, λ₂ is 9/2, and x = -3/2, y = 2. So candidate point (x, y) is (-3/2, 2).
Last case: both constraints are inactive, slack not binding: 12x² + y < 4 and thus λ₁ = 0, y > 2 and thus λ₂ = 0. I go into condition two, which now only reads 3x = 0 because λ₁ and λ₂ are equal to zero. This means that x = 0. Then I get from constraint one, since now λ₁, λ₂, and x are equal to zero, this reads now just that 3y = 0, and we get that y = 0. So I get another candidate point where everything is equal to zero. Now I can, I'm going, I have gone through all four possible configurations of activity and inactivity of the constraints. I have exhausted the set of points that satisfy the Kuhn-Tucker conditions. I am left with four candidate points, and I can check the maximality of those four candidate points.
So the objective function was 2x² + 3xy. Now we have the candidate points (x, y) = (2, 2). So I get 2 * 4 + 3 * 4 = 20. Then I have the candidate point (x, y) = (-2, 2). This is 2 * 4 - 3 * 4 = -4, certainly not a better point. Then I get I have the candidate point (-3/2, 2). This is 2 * 9/4 - 9/2 = -9/2, also not a winner. And then finally I have the origin, and there of course I just get zero. So clearly my candidate here is the point (2, 2).
So I can check sufficiency. Again, is the Lagrange auxiliary function a concave function in the maximum, the optimum, or here concave and the maximum, convex in the minimum? So again, plug in λ₁ and λ₂ from the optimal point. Those were λ₁ = 7 and λ₂ = 1. The Lagrange function as a function of x and y is 2x² + 3xy - 7(12x² + y - 4) + 1(y - 2). This, after cleaning up, is -82x² + 3xy - 6y - 26. This is a concave function in x and y: negative parabola in x and linear in y, and thus we have sufficiency. Indeed, the case for point (2, 2) strengthens. The only thing that's left to check is constraint qualification. Have we missed a point that does not satisfy constraint qualification but nevertheless is a maximal point? What are the gradients of the constraint functions? The gradient of the first constraint function is (12x, 1) and the gradient of the second constraint function is (0, -1). When are they linearly dependent? Well, for x = 0. If x = 0, we get from the first condition that 3y = 0. This means that y = 0. So the only point where constraint qualification breaks down is the origin, and that one we have already checked. It does not—the function value, the objective function value is zero here, certainly less than our maximum value of 20. And so the points where constraint qualification breaks down do not give any higher function value, and so we have identified our maximum. So we have therefore established that the point (x, y) = (2, 2) is the maximum of f given the constraints, and that concludes the second example, and this concludes the video. So thank you very much for watching.