Transcription
Welcome to my series of videos on mathematics for economists. In this video, I'm going to go through a number of examples for optimization under equality constraints. Uh, so we're going to apply the Lagrangian multiplier theorem, work out the necessary conditions, find candidate points that satisfy the necessary conditions, look at which one of them yields the highest value of the objective function, and then, for the so-found candidate for the optimum, check the second-order conditions. Then I'm going to look at a few examples where things go wrong and discuss constraint qualification in those examples. Okay, so let's have a look at this first example here where we have an objective function that goes from R3 to R and returns, for the input arguments X, Y, and Z, the product X * Y * Z, such that the two constraints are satisfied: X² + Y² is equal to 4, or, in other words, the vector XY has length equal to 4, and X + Z is equal to 2.
So the first thing we do is we write down our Lagrangian auxiliary function, which is the objective function X * Y * Z minus the first Lagrangian multiplier, which comes with the first constraint—left-hand side of the constraint minus right-hand side of the constraint—minus the second multiplier, which comes with the second part or the second constraint—left-hand side of the constraint minus right-hand side of the constraint. And now we find the necessary conditions by setting all the partial derivatives with respect to X, Y, Z, and with respect to λ₁ and to λ₂ equal to zero. So take the partial derivative with respect to X; this is YZ − 2λ₁X − λ₂ = 0. The partial derivative with respect to Y, this is XZ − 2λ₁Y = 0. The partial derivative with respect to Z, this is XY − λ₂ = 0. The partial derivative with respect to λ₁, this is X² + Y² − 4 = 0. And the partial derivative with respect to λ₂, this is X + Z − 2 = 0. The partial derivatives with respect to the Lagrangian multipliers are, of course, only repeating the constraints because those are the factors of the λ coefficients in the Lagrangian function.
So now the general structure of the problem that is facing you at this point is that you have a system of nonlinear equations—usually nonlinear—that you have to solve, and it's a square system in the sense that you have as many equations as there are unknowns; so here, five for X, Y, Z, λ₁, and λ₂. And because the system is nonlinear, methods of linear algebra are not going to help you here, but you have to be, in a sense, lucky that you find the right angle of attack to solve this nonlinear system of equations analytically. As long as there are no linearly dependent equations—in some sense, multiples or multiples of one equation added to another—there is going to be a solution, or maybe even several solutions, and you can't find them usually by—you can, you can find them definitely by numerical methods, but, of course, here we're interested in finding them analytically so that we can understand the structure of the problem. So let's see what we can do here in this case with these five equations. The basic idea is what you want to do is you have—you're dealing with five variables; you somehow want to reduce the number of variables that you have going on by isolating some of them and then plugging them in into other equations so that, ideally, you can somehow find one equation and one unknown, which you then can solve, hopefully.
So here we see from equation two that λ₁ is equal to X * Z / 2Y. Right, this happens if I—if I isolate λ₁ in equation two. In equation three, if I isolate λ₂, I get that it is XY. So now I'm working towards this goal of substituting—in the sense that I express λ₁ and λ₂ as functions of X, Y, and Z—so that I can replace λ₁ and λ₂ in the equations by X, Y, and Z so that I can express everything as a function of only three variables. So I go into equation one, which right now reads YZ − 2λ₁X − λ₂ = 0, and now I do exactly this: I replace λ₁ and λ₂. So I get YZ − now I have in λ₁ I have a—I have a two in the denominator, so the two cancels out; I have an XZ for λ₁ in the numerator, so I get 2 * X is X²Z / Y − I replace λ₂ by XY = 0. So I have gone from an equation in X, Y, and Z to an equation and just X—excuse me—from an equation in X, Y, Z, λ₁, and λ₂ to an equation in just X, Y, Z. All right, so let's multiply this by Y: Y²Z − X²Z − XY² = 0. Okay, I have gone from five unknowns to three unknowns; that's good, but it doesn't—doesn't lead me all the way yet. So I'm now using equation four because equation four tells me that Y² = 4 − X², and then I can replace the Y²s here by 4 − X², and then I'm using equation five, which tells me that Z = 2 − X. And then I get one equation and one unknown, which is Y² = 4 − X², Z = 2 − X, and then I get one equation and one unknown, which is (4 − X²) * (2 − X) − X² * (2 − X) − X * (4 − X²) must be equal to zero to satisfy the necessary condition.
Okay, so now, because this is a nonlinear system of equations, if you have done this and substituted until you arrived at one equation and one unknown, this equation can and will usually be a highly nonlinear object, and that's what we have in front of us here. You can see that the highest power of X that is going to occur in this polynomial, once I have cleaned it up, is going to be X³. So we don't have an algorithm ready at hand to solve for the roots of this third-degree polynomial, which is what we need to do because the first-order conditions say that this equation needs to be equal to zero. However, you can see here that this example is designed such that, if you look carefully at it, you can actually, by eyeballing, see what one root is going to be because, if you look at the first two terms, they both have the factor 2 − X. So if you set X = 2, the factor 2 − X is certainly going to be zero. What about the third term? X * (4 − X²) It does not have the factor 2 − X. However, if you set X equal to 2, then 4 − X² certainly is also equal to zero, and so you can actually see that X = 2 is a root of this polynomial. So let's write down what this polynomial is: 4 *—I'm just factoring out these three terms here—so 4 * 2 is 8 − 4X − 2X² + X³ − 2X² + X³ − 4X + X³ = 0. Now I see that I have 3X³, I have −4X², I have −8X, and I have +8 = 0. What does it mean that X = 2 is a root of this third-degree polynomial? This means that there is a second-degree polynomial out there which I don't know yet such that, if I multiply it by the linear factor X − 2, which sets the whole thing equal to 0 if X is equal to 2, will give me my original third-degree polynomial 3X³ − 4X² − 8X + 8. How do I find the second-degree polynomial? Well, by dividing the whole equation by X − 2. This is long division, which you may remember. You have to divide the leading term 3X³ by the leading term in the divisor; this is X, so you get 3X². Then you multiply your way back: 3X² * X + 3X² * −2, and you get 3X³ obviously − 6X². Then you subtract: 3X³ − 3X³ is 0; −4X² − −6X² is +2X², and then you can pull down the other terms from above, and you keep going. You divide the first term in the remainder polynomial by the first term in the divisor, and you get +2X. Then you multiply your way back, and you get 2X² obviously − 4X. Then you subtract: 2X² − 2X² = 0; −8X − −4X is −4X, and the +8 we haven't done anything with. −4X + 8 / X − 2 obviously is −4 because if you now multiply your way back, you get −4 * X − 4 * −2 is +8, and if you now subtract, you get the remainder zero. So we have found the second-degree polynomial, which is standing right here.
Okay, now we're supposed to set the whole expression equal to zero, and so we also need to find the two roots of this second-degree polynomial, and now you can apply your favorite formula for solving quadratic equations. Yeah, and if you call this ABC formula or PQ formula or whatever—let's write this as, since we have to set 3X² + 2X − 4 = 0, we might as well divide by 3, so we get (2/3)X − (4/3) = 0, and we get the two roots −2 times this coefficient here, so this is −(2/6) or −(1/3), plus or minus the square root of 1/4 * the square of this coefficient, which is 4/9, minus the third term, so this − −(4/3) is +(4/3). Yeah, and (4/3) that's (12/9) + (1/9) is (13/9), and so I can write this as −(1/3) ± the square root of (13/9) is some real number that I don't know by heart; the square root in the denominator of 9 is certainly 3. Okay, so we have three linear factors, so we can write—we have now found out—we can write our polynomial of degree 3 as the product (X − 2), that was the first one, (X − (−1/3) + the square root of 13/3) * (X − (−1/3) − the square root of 13/3). So now I can read the three roots of the polynomial from my decomposition into linear factors. Okay, um, so we have three candidate points for X that satisfy the necessary conditions. So let's find the corresponding Y's and Z's that go with this so that we have the full set of candidate points in XYZ. So let's start with X = 2. That—what's the first one we saw? From equation four, which reads X² + Y² = 4, if X = 2, X² is equal to 4, so we get Y² must equal zero, and this means that Y is going to be zero. Then, from equation five, which reads that X + Z must equal two, if X is equal to two, this means that Z must equal zero. So our first candidate point for X, Y, and Z is (2, 0, 0). Then we have the second root for for X here, so this would be, let me write it as the square root of 13 − 1 / 3. Again, I use equation four to find out what Y is going to be: Y² is 4 − X², right, and so Y is plus or minus the square root of 4 − X², so this is 4 − (the square root of 13 − 1 / 3)², and then five gives me that Z is 2 − X, so this is 2 − (the square root of 13 − 1 / 3). So this is my—actually my set of the next two candidate points because I have a positive and a negative value for Y here that are all going to satisfy the necessary conditions. So let's look at the last value for X here: the negative root of 13, so I have −1 − the square root of 13, so let me write the minus in front of the fraction, and then I get the square root of 13 + 1 / 3, and then I get, by equation four, that Y is plus or minus the square root of 4—now minus—and then I have X here; X has a minus, but it's going to be squared, so the minus is going to be neutralized, so I can write (the square root of 13 + 1 / 3)² here, and I get from five that Z is 2 − X, and that's 2 − (−the square root of 13 + 1/3). Yeah, we have again two further candidate points because we have again a positive and a negative Y here that's going to satisfy the first-order conditions. So we have a set of five candidate points that satisfy the first-order conditions. So, in order to find now which one maximizes our objective function, we just plug all five candidate points in and evaluate the objective function. So the objective function, remember, is X * Y * Z, so 2 * 0 * 0 is certainly 0, so the first one is easy. Then we have X = (the square root of 13 − 1 / 3), the positive square root of 4 − (the square root of 13 − 1 / 3)², and 2 − (the square root of 13 − 1 / 3). If you plug this into your pocket calculator, you find that the value that you get here for the objective function is roughly equal to 1.77, so it's certainly higher than zero. We have to evaluate the negative root, but, of course, we can, since we now put a minus in front of Y, and X and Z remain the same, and the objective function is X * Y * Z, all we're going to do is switch the sign, and since we want to maximize, this is actually not an interesting point. Now we want to have the negative square root of 13 in X; that's the second root of our quadratic remainder polynomial we found, so this is −(the square root of 13 + 1) divided by 3, and then we start with the positive root for Y for—and now X² again I—I ignore the minus because it's going to be neutralized, and then I get 2 − X is here plus the square root of 13 + 1/3, and if you put this into your computer, it will—it will return a value of −6.96 roughly, but now that's—that's absolutely high, but, of course, we're maximizing, so minus is not good, but now we need to also look at the negative root for Y, and that, of course, is going to neutralize the negative sign of X, and then we are going to switch the sign on the value of the objective function, and that's our interesting point that gives us our maximum of roughly 6.96, but just certainly higher than 1.77. Yeah, so this is the point of the candidate set of five points that satisfy the necessary condition which returns the highest value of the objective function. Let us verify that this is indeed a maximum by checking the second-order conditions.
Let me first repeat the Lagrangian, and let me multiply out all the terms that come with the—with the constraints and the Lagrangian multipliers because I want to take second-order derivatives, and so it is more convenient to have this in longhand. Sorry, this is λ₂. Okay, what happens in the—in the second-order conditions? As in unconstrained optimization, here we have a—we have a maximization problem, so as an unconstrained maximization, the Hessian matrix in the maximum must be negative definite, but because we're under equality constraints, the Hessian must be negative definite only in the admissible directions, which means only in those directions that satisfy the first order—that satisfy the constraints. We're only looking into the directions that satisfy the constraints. The directions here are the—are the vectors X, Y, and Z, and in order to do this, we—we use this object of the bordered Hessian, which is essentially a mnemonic device that—that gives us determinant conditions for the Hessian matrix to be—here negative definite because we have a maximization problem subject to the—to the constraint that we're only looking into the directions that satisfy the constraints. Yeah, so we need to form the Hessian in any case, so we are going to have to calculate all the second-order derivatives. So let's start at that simple point that we can certainly do without any further ado. So the second derivative with respect to—partial derivative with respect to X is −—excuse me—−2 * λ₁. The second derivative with respect to Y is also −2 * λ₁. The second derivative with respect to Z is equal to zero. And now the—the cross derivatives—the second-order derivative with respect to X and to Y is Z, and because the Lagrangian is twice continuously differentiable, this is also the second-order derivative with respect to Y and to X. Second order with respect to X and to Z is Y, and this is also with respect to Z and to X. And the second-order derivative with respect to Y into Z is X, and this is also the second derivative with respect to Z to Y. So we have all the elements in the Hessian. Now the bordered Hessian has also the gradients of the constraint functions, and the reason they are in there is exactly to ensure that we only look in directions that satisfy the constraints. So this was X² + Y² = 4, and this here is X + Z = 2. So the partial derivatives with respect to X, Y, and Z are (1, 0, 1). So we can form our—our bordered Hessian of degree 3. So let me write H—bordered Hessian of degree 3—this means that the degree here means that we—we have the X, Y, and Z dimension in the Hessian, so this is—it's not a power or anything; this is just—it's just a figure of speech. So what does it look like?
(0, 0, 0; 1, 0, 1; 0, 1, 0) Here we have the gradient of the first constraint; here we have the gradient of the second constraint; and now—and the remaining lower right 3 × 3 block matrix, we have the Hessian. So we need to have all those objects that we calculated here, so the diagonal is −2λ₁, −2λ₁, and 0; those are the second-order derivatives. Excuse me, I have a—that's better. And now the cross derivatives: X and Y, that's Z; X and Z, that's Y; and Y and Z, that's X. So this is my bordered Hessian where I have—where I have the Hessian for all three variables X, Y, and Z, and then I look also at the—at the fourth principal minor here, which means that I'm just looking at—so this here are the three, and now I'm just looking at two, so I get (0, 0; 0, 0), (0, 0; 2, 2), (0, 2; X, 2Y), (0, 2; 1, 0), −2λ₁, Z, Z; −2λ₁, and now, in the same fashion as an unconstrained maximization where you check whether the Hessian is negative definite by the Hurwitz criterion where you look at the determinants of the leading principal minors, we have a corresponding—a corresponding determinant criterion for the bordered Hessians, which are also in terms of the principal minors, but not all of them; you have to look a bit more carefully; that's a theorem here; I'm just applying it. So what we need to have is that the determinant of H<sub>b3</sub> be negative and that the determinant of H<sub>b2</sub> be positive, and if you now—well, the—we have X, Y, Z, λ₁ going on here; λ₂ doesn't figure in the bordered Hessian; so now we need to replace X, Y, Z, and λ₁ by our candidate point that we have identified, which is X = −(the square root of 13 + 1) / 3, Y was the negative square root of 4 − (the square root of 13 + 1 / 3)², and Z was 2 + (the square root of 13 + 1) / 3. λ₁ was, from the—from equation two, given by XZ / 2Y. Yeah, so given X, Y, and Z, we can also calculate λ₁, and if you now—if you now do this and plug these numbers into these matrices and then calculate the determinants, you find that the determinant of H<sub>b3</sub> is roughly equal to −13071 and the determinant of H<sub>b2</sub> is roughly equal to 6.57, so they do satisfy the second-order conditions, and we have indeed found a maximum subject to these equality constraints. Yeah, so this example is here finished, and we have arrived at a solution at the maximum of X * Y * Z subject to the constraints that X² + Y² = 4 and that X + Z = 2. Good, that's the recipe, and now I would like to discuss what can go wrong. Let's start a new—a new sheet here, and let's consider a new example. Let's consider the maximization function with respect to three variables X, Y, and Z—no, excuse me—no, let's just have a—a function from R² to R, so we have just an f(X, Y), and the objective function is just given by X; it's a bit boring; it just returns the first coordinate. The constraint we have—just one—is that X³ + Y² be equal to zero. Okay, now we follow the recipe and see where that leads us. So we form our Lagrangian, which is the objective function X − we only have one Lagrangian multiplier—left-hand side of the constraint X³ + Y² − right-hand side, that's just −0, so I can ignore this; so I can find the first-order conditions by taking the partial derivative of the Lagrangian with respect to X; this is 1 − 3λX², and this must equal zero to satisfy the first-order condition. With respect to Y, I get −2λY = 0, and with respect to the Lagrangian multiplier, I just repeat the constraint that X³ + Y² be zero. Good, now I can try to follow the same road and try to somehow substitute such that I end up with one equation and one unknown. Let me see if that—if that is successful. So let's start at equation one and solve it for λ. Yeah, so if I do this, I get that λ is equal to 1 / 3X². H—remember that the Lagrangian multipliers must be—the way we have written the Lagrangian—must be positive or can be zero, but they cannot be negative and they cannot be infinite because they must exist, and exist means they exist in R and they don't explode, and this means that X must be finite here. Yeah, because—sorry—this means that X must be—must not be equal to zero because if X was zero, then λ would be infinite, so X = 0 cannot be—okay, so if we assume that X is not equal to zero, we can go into—we can go into, let us say, equation two, so we have 2 * λ * Y is equal to 0 because I can multiply this equation by by −1, right? So 2 * λ this time Y, this is 2Y / 3X² must equal zero. Okay, so now we have—we have seen X cannot—cannot equal zero. Now, in order to—to have Y—to have this fraction equal to zero, Y must equal zero, right? Okay, um, so now we go into equation three, and then we see that we have a problem because if Y is equal to zero, then we get the equation that X³ must equal zero, and the only solution for X³ to equal zero is that X = 0, and we've seen that this cannot work with our first equation, so we have a contradiction here, which I symbolize by this little flash of lightning that hits us here. So we have a contradiction, and we cannot find a solution of our nonlinear system of equations. Why is this? So—there are two ways of explaining why this is—let's start with a…
Analytical one. Uh, this is because constraint qualification is not satisfied. What is constraint qualification? Constraint qualification says that the um gradients of the objective function in the optimum must be linearly independent. Here we only have one, and uh, linearly independent here means that it must not be equal zero; must not be equal to zero, right? So what is the gradient of G? Uh, G was uh X cubed + Y squared equal to zero. So the derivative with respect to X is uh is 3X squared, and the derivative with respect to Y is 2Y. And now we see that in the point X equal to 0 and Y equal to 0, which we have not yet established as a maximum, but it's clearly interesting from uh looking at the first order conditions, in the point 0, 0, the gradient of the constraint is zero. So it is degenerate here.
Now we can also look at the geometry of the situation. And if we look at the third condition, then we see that which which reads X cubed + Y squared = 0. Uh, this means we can write Y as plus or minus the square root of -X cubed. And in order for this the the the the number under the square root sign to be positive, X of course must have a negative value, because then X cubed is negative, and so -X cubed is positive. And so I'm only plotting in this picture here the negative uh the negative half space for X, and then I'm plotting the negative square root of -X cubed; that's the that's this orange curve here. And then the positive square root of -X cubed, and that's the blue curve here. So this constraint must be satisfied, and this means that only points on these curves are admissible. The objective function uh is only X. So if we were if we are to maximize X, this means that we have to find the the point on these curves that gives us the largest value on the X axis. And so eyeballing the geometry here, we can see that the solution to the problem, the highest point, the highest value for X that lies on these curves is the point X equal to 0, which then implies that Y is also equal to zero. So as we have kind of seen in the first order conditions, 0, 0 is the point we're looking after. However, because the the constraint is such that the gradient of the constraint in the point 0 is equal to the zero vector, uh we cannot find this point by solving the linear system of equations, solving the first order conditions. So this is one way how this can go wrong. Yeah, let's have a look at another example how this can go wrong, and let's start yet another sheet for this.
So we look at the same objective function, which maps from R2 to R, but just returns the boring first coordinate. And now we have two constraints which read X - 1 squared - Y + 1 = 0 and X - 1 squared + Y - 1 = 0. We follow the recipe again, form the Lagrangian, which is objective function minus now we have two Lagrange multipliers again, X - 1 squared - Y + 1, left hand side of the constraint minus right hand side of the constraint, which is just zero here, minus second Lagrange multiplier for the second constraint + Y - 1 - 0. And we go ahead and try and find the first order conditions by setting the partial derivatives with respect to X, to Y, to Lambda 1, and to Lambda 2 equal to zero. This is 1 - 2 Lambda 1 * X - 1 squared minus Y plus oh sorry, that's not good, what am I doing here? Uh, so that's better. Um - 2 Lambda 1 * X - 1, that's the derivative with respect to X of of the first term here. And now the derivative of the second term with respect to X, that's that would be - 2 Lambda 2 * X - 1, and we set this equal to zero. Okay, the derivative with respect to Y is uh it just appears here and there, so-- is plus Lambda 1 and minus plus is minus Lambda 2 is equal to 0. That's an interesting one, right? Because it tells us that Lambda 1 is equal to Lambda 2. Third is just repeating the first constraint, and the fourth is repeating the second constraint. Okay, so let's start with this interesting one here: Lambda 1 is equal to Lambda 2. Aha, so this means that in the let's call it Lambda, this means that in the first one, which is now 1 - 2 Lambda * X - 1 - 2 Lambda * X - 1, so this is -4 Lambda * X - 1 equal to 0. This means I can solve for Lambda, which is 1/4 * X - 1. And again from the discussion we had before, this thing must not explode. So we see that uh X cannot be equal to one. Okay, what do we get from equation three? We get that Y is equal to um 1 + X - 1 squared. And from equation four we get that Y is equal to uh 1 - X - 1 squared. So these two expressions must be the same. So 1 + X - 1 squared is 1 - X - 1 squared. I can subtract one on both sides, and I can bring uh the the negative one over to the other side, and so I get that 2 * X - 1 squared must equal zero. That's unfortunate, because the solution uh to this would be that um that X is so one of the solutions to this is that uh uh that X must uh must equal one, and this is a violation of Lambda being uh being finite. Um, this is the only solution for for X - 1 squared being equal to zero. I can of course divide by two here, so uh we have again a contradiction. So we cannot solve the the nonlinear system of equations, and we can again um kind of go into the forensics and try to explain why this is the case.
So let's look at our constraint qualification condition again. What is the uh de what are the partial derivatives of the first condition uh so with respect to X, this is 2 * X - 1, and with respect to Y, this is -1. And the second one, uh partial derivative with respect to X is again 2 * X - 1, and with respect to Y is +1. And now we see that in the point X equal to 1, this is exactly where we are in trouble, because we have the problem that the first the gradient of the first uh constraint is 0 and -1, and the gradient of the second constraint is 0 and 1, and these are linearly dependent obviously, because one is just -1 times the other. Yeah, so we can again look at the geometry of the situation. So if we look at essentially if we look at these two expressions for Y that we have here and we plot these two functions of X, then we have a parabola that opens to the bottom, that's the orange one here, and we have a parabola that opens to the top, that's the blue one here, and both are equality constraints that must hold, which means that we're looking at uh at points that lie on the intersection of these two curves. And the intersection of these two curves is a single point, which is X = 1 and then therefore Y = 1. So again we have seen in the in our attempt at solving the necessary conditions that X equal to one is very interesting, but uh we had a failure of constraint qualification there. And so uh geometrically here we see that the problem is that our set of admissible points that satisfies both constraints, that set consists actually of just one point, the one point 1 and 1. So this means that the maximization uh find the largest X such that these two constraints are satisfied has no bite because there's only one point. So if you have to satisfy the constraints, there's only one X, and therefore by definition it's also the largest one. And so um uh there is no way to further uh uh to find different points that would yield a higher X. And so 1 and 1 is in fact the solution to our problem, but it is uh uh only one point, and the constraint qualification condition does not hold in this point. So that's that's what's going on. Yeah, so we've seen two examples here where where the the recipe that we followed in the first example uh in order to find the the maximiz the maximum point for um for a function subject to equality constraints where this goes wrong because constraint qualification is not satisfied. And appreciate that geometrically these are two quite quite different situations, right? In one case we have this kind of cusp in the uh uh in the constraint curves, and in the other example we have um we have chosen the constraint such that the set of admissible points really is just one point, and so therefore our maximization has has no bite and can only choose that one point. Uh, but in both cases we can actually diagnose the problem by looking at the gradients of the constraints and checking whether they are linearly independent or not. Yeah, so this is uh these are some examples on uh optimization under equality constraints using the Lagrange multiplier theory. Thanks a lot for watching.