KKT Examples

2.853/2.854 KKT Examples The purpose of this note is to supplement the slides that describe the Karush-Kuhn-Tucker conditions. Neither these notes nor the slides are a complete description of these conditions; they are only intended to provide some intuition about how the conditions are sometimes used and what they mean. The KKT conditions are usually not solved directly in the analysis of practical large nonlinear programming problems by software packages. Iterative successive approximation methods are most often used. The results, however they are obtained, must satisfy these conditions. Example 0 No constraints: min J = x21 + x22 + x23 + x24 The solution is x1 = x2 = x3 = x4 = 0 and J = 0. Example 1 One equality constraint: min J = x21 + x22 + x23 + x24 subject to x1 + x 2 + x 3 + x 4 = 1 1 (1) Solution: Adjoin the constraint min J¯ = x21 + x22 + x23 + x24 + λ(1 − x1 − x2 − x3 − x4 ) subject to x1 + x 2 + x 3 + x 4 = 1 In this context, λ is called a Lagrange multiplier. The KKT conditions reduce, in this case, to setting ∂J¯/∂x to zero:  Therefore ∂J¯   = ∂x  2x1 − λ 2x 2 − λ 2x3 − λ 2x4 − λ       =   λ x1 + x 2 + x 3 + x 4 = 4 2 so x1 = x 2 = x 3 = x 4 = x4 !      (2) λ 2 x1 = x 2 = x 3 = x 4 = so 0 0 0 0 = 1 or λ = 1 2 1 1 and J = 4 4 x1= x4= λ 2 ( 14 , 14 , 14 , 14 ) x1 equality constraint J=constant Figure 1: Example 1, represented in two dimensions Comments • Why should we adjoin the constraints? The answer to this question has two parts: 2 ? First, it does no harm. There is no difference between J and J¯ for any set of xi that satisfies the problem since the set of xi that satisfies the problem must satisfy (1). Furthermore, it works. This may not feel like a very satisfying answer, but this is also why we plug x = Ceλt into a linear differential equation with constant coefficients. We could have done a zillion other things that would have done no harm, but they would not have done any good either. There is not much point in studying them; we only study what works. ? In this case, it provides a relationship that we can use among the components of x (equation (2)). In general, it replaces the minimization requirement with a set of equations and inequalities, and there are just enough of them to determine a unique solution (when the problem has a unique solution). • The solution is illustrated in Figure 1. We are seeking the smallest 4-dimensional sphere that intersects with the equality constraint (a 3-dimensional plane in 4-dimensional space). Equation (2) essentially tells us that the solution point is on a line that intersects with that plane. • If we asked for the maximum rather than the minimum of J, the same necessary conditions would have applied, and we would have gotten the same answer following the steps shown here. However, that answer would be wrong . After all, if it is a minimum, it cannot also be a maximum unless the function is a constant, which it certainly is not. We know that we have found a minimum because of the second order conditions: the second derivative matrix ∂ 2 J/∂x2 is positive definite. • It is a coincidence that for both Example 0 and Example 1 J = xi , i = 1, ..., 4 at the optimum. What is not a coincidence is that J for Example 1 is greater than J for Example 0. If you change an optimization problem by adding a constraint, you make the optimum worse; or, at best, you leave it unchanged. Example 2 One equality constraint and one inequality constraint: min J = x21 + x22 + x23 + x24 subject to x1 + x 2 + x 3 + x 4 = 1 x4 ≤ A (3) (4) in which A is a parameter that we will play with. Figures 2 and 3 illustrate two possible versions of this problem, depending on the value of A. (The shaded regions are the forbidden values of x, the places where x4 > A.) 3 x4 x4 x* inequality constraint x* inequality constraint x1 x1 equality constraint equality constraint J=constant J=constant Figure 2: Example 2, A large Figure 3: Example 2, A small Digression: The inequality constraint requires a new Lagrange multiplier. To understand it, let us temporarily ignore the equality constraint and consider the following scalar problem, in which J and g are arbitrary functions that are differentiable, whose derivatives are continuous, and where J has a minimum: min J(x) x (5) subject to g(x) ≤ 0 There are two possibilities: the solution x? satisfies g(x? ) < 0 (ie, where the solution is strictly in the interior of the inequality condition) or it satisfies g(x? ) = 0 (where the solution is on the boundary of the interior of the inequality condition). Figures 4 and 5 illustrate these two possibilities. Possibility 1, the interior solution: The necessary condition is that x? satisfies dJ ? (x ) = 0 dx (6) That is, the solution is the same as that of the problem without the inequality constraint. Possibility 2, the boundary solution: Let x = x? + δx. For x? to be the optimal solution to (5), δx = 0 must be the solution to min J(x? + δx) δx (7) subject to g(x? + δx) ≤ 0 This is certainly true if we restrict our attention to small δx. In that case, we can expand J and g as first order Taylor approximations and (7) becomes, approximately 4 g(x) < 0 g(x) < 0 Figure 4: Case 1, Interior solution Figure 5: Case 2, Boundary solution min J(x? ) + δx dJ ? (x )δx dx subject to dg ? (x )δx ≤ 0 dx g(x? ) + Since J(x? ) is independent of δx and g(x? ) = 0, this can be written min δx dJ ? (x )δx dx (8) subject to dg ? (x )δx ≤ 0 dx dg ? dJ ? (x ) and (x ) such that the solution to (8) is δx = 0. Note dx dx that (8) is a linear programming problem. To be really exhaustive about it, we must now consider the four cases in the table below 1 . Case 1, for example, reduces to We now seek conditions on min δx δx subject to δx ≤ 0 1 Actually, there are nine cases, since we could also have dJ/dx = 0 or dg/dx = 0. However, if dJ/dx = 0 at x = x∗ , then we really have a situation like the interior solution. That is, the constraint is still ineffective since we would have the same x∗ even if we ignored the g(x) ≤ 0 condition. If dg/dx = 0 at x = x∗ , then the constraint qualification is violated. This is discussed below. 5 since the magnitudes do not matter — only the signs matter. The solution is clearly δx = −∞. Similarly, Case 2 becomes min δx δx subject to δx ≥ 0 and it is clear that the solution is δx = 0. The other cases are similar. Case 1 2 3 4 dJ ? (x ) dx >0 >0 <0 <0 dg ? (x ) dx >0 <0 >0 <0 Solution δx = −∞ δx = 0 δx = 0 δx = ∞ Therefore, the only cases in which the solution is δx = 0 are Cases 2 and 3, the cases in which dJ ? dg ? the signs of (x ) and (x ) are opposite. Therefore, there is some positive number µ such dx dx that dg dJ ? (x ) = −µ (x? ) dx dx or dg dJ ? (x ) + µ (x? ) = 0 dx dx Equation (6) is implied by this if we require µ = 0 when g(x? ) < 0. Solution: For the problem of Example 2, define J¯ = x21 + x22 + x23 + x24 + λ(1 − x1 − x2 − x3 − x4 ) + µ(x4 − A) Then, the KKT conditions are 6 ∂J¯ =0 ∂x x1 + x 2 + x 3 + x 4 = 1 x4 ≤ A µ≥0 µ(x4 − A) = 0 (9) (10) (11) (12) (13) From (9):  Therefore  ∂J¯  = ∂x  2x1 − λ 2x 2 − λ 2x3 − λ 2x4 − λ + µ x1 = x 2 = x 3 =       =   0 0 0 0      λ−µ λ , x4 = 2 2 so, from (10), ! µ λ x1 + x 2 + x 3 + x 4 = 4 − =1 2 2 or 4λ − µ = 2 or λ = Therefore x1 = x 2 = x 3 = 2+µ 4 2+µ 1 µ 2+µ µ 1 3µ = + , x4 = − = − 8 4 8 8 2 4 8 (14) From (11), or 1 3µ ≤A − 8 4 3µ 1 ≥ −A 8 4 (15) Case 1: A > 1/4 This is the interior case illustrated in Figures 2 and 4. Since 1/4 − A ≤ 0, (15) implies that (12) is automatically satisfied. From (14) 1 1 x1 = x2 = x3 ≥ ; x4 = 1 − (x1 + x2 + x3 ) ≤ 4 4 But we have more from (14): (13) implies that µ = 0. Therefore 1 x1 = x 2 = x 3 = x 4 = 4 which is consistent with the answer to Example 1 and common sense. Example 1 says that this is optimal; if we also require that x4 is less than A and A is greater than 1/4, we haven’t changed anything. Note that the optimal J is again 1/4. 7 Case 2: A = 1/4 This behaves like Case 1. The unconstrained optimum lies on the boundary. Therefore, if we ignored the inequality constraint, we would get the same x∗ . Case 3: A < 1/4 If x4 were strictly less than A, then (13) would require that µ = 0. But then (14) would imply x = 1/4, which violates (11). Therefore x4 = A and 1 x1 = x2 = x3 = (1 − A) 3 Also 1 1 J = 3 (1 − A)2 + A2 = (1 − A)2 + A2 9 3   1 1 − 2A + 4A2 = 3 and that J ≥ 1/4 and that J = 1/4 when A = 1/4.   Comments • The comments after Example 1 hold here. • J=  1     4  if A ≥     1   1 − 2A + 4A2 3 8 1 4 otherwise The graph of J as a function of A is: 2.5 J 2 1.5 1 0.5 0 −1 −0.5 0 0.5 A 1 1/4 • The extension of the KKTs to more than one equation and/or more than one inequality constraint is straightforward, but there is one more condition to be applied in general, the so-called constraint qualification. This says that the gradients of the equations and of the effective inequality constraints must be linearly independent at the solution x? . • The informal discussion of the KKT conditions was modeled on that of Bryson and Ho (1975). There are plenty of other references, but this discussion is especially intuitive. References Bryson, A. E. and Y.-C. Ho (1975). Applied Optimal Control: Optimization, Estimation, and Control. Hemisphere Publishing Corporation. 9