Nonlinear Programming:The Karush-Kuhn-Tucker (Kkt) Conditions For Constrained Optimization

The Karush-Kuhn-Tucker (Kkt) Conditions For Constrained Optimization

We now focus on the question of how to recognize an optimal solution for a nonlinear programming problem (with differentiable functions) when the problem is in the form shown at the beginning of the chapter. What are the necessary and (perhaps) sufficient conditions that such a solution must satisfy?

In the preceding sections we already noted these conditions for unconstrained optimization, as summarized in the first two rows of Table 13.4. Early in Sec. 13.3 we also gave these conditions for the slight extension of unconstrained optimization where the only constraints are nonnegativity constraints. These conditions are shown in the third row of Table 13.4. As indicated in the last row of the table, the conditions for the general case are called the Karush-Kuhn-Tucker conditions (or KKT conditions), because they were derived independently by Karush11 and by Kuhn and Tucker.12 Their basic result is em- bodied in the following theorem.

12H. W. Kuhn and A. W. Tucker, “Nonlinear Programming,” in Jerzy Neyman (ed.), Proceedings of the Second Berkeley Symposium, University of California Press, Berkeley, 1951, pp. 481–492.

Note that both conditions 2 and 4 require that the product of two quantities be zero. Therefore, each of these conditions really is saying that at least one of the two quantities must be zero. Consequently, condition 4 can be combined with condition 3 to express them in another equivalent form as When m = 0 (no functional constraints), this summation drops out and the combined condition (1, 2) reduces to the condition given in the third row of Table 13.4. Thus, for m > 0, each term in the summation modifies the m = 0 condition to incorporate the ef- fect of the corresponding functional constraint.

In conditions 1, 2, 4, and 6, the ui correspond to the dual variables of linear programming (we expand on this correspondence at the end of the section), and they have a comparable economic interpretation. However, the ui actually arose in the mathematical derivation as Lagrange multipliers (discussed in Appendix 3). Conditions 3 and 5 do noth- ing more than ensure the feasibility of the solution. The other conditions eliminate most of the feasible solutions as possible candidates for an optimal solution.

However, note that satisfying these conditions does not guarantee that the solution is optimal. As summarized in the rightmost column of Table 13.4, certain additional convexity assumptions are needed to obtain this guarantee. These assumptions are spelled out in the following extension of the theorem.

Corollary. Assume that f (x) is a concave function and that g1(x), g2(x), . . . , gm(x) are convex functions (i.e., this problem is a convex programming problem), where all these functions satisfy the regularity conditions. Then x* = (x1*, x2*, . . . , xn*) is an optimal solution if and only if all the conditions of the theorem are satisfied.

Therefore, there exists a number u1 = 1 such that x1 = 0, x2 = 3, and u1 = 1 satisfy all the conditions. Consequently, x* = (0, 3) is an optimal solution for this problem.

This particular problem was relatively easy to solve because the first two steps above quickly led to the remaining conclusions. It often is more difficult to see how to get started. The particular progression of steps needed to solve the KKT conditions will differ from one problem to the next. When the logic is not apparent, it is sometimes helpful to con- sider separately the different cases where each xj and ui are specified to be either equal to or greater than 0 and then trying each case until one leads to a solution.

To illustrate, suppose this approach of considering the different cases separately had been applied to the above example instead of using the logic involved in the above seven steps. For this example, eight cases need to be considered. These cases correspond to the eight combinations of x1 = 0 versus x1 > 0, x2 = 0 versus x2 > 0, and u1 = 0 versus u1 > 0. Each case leads to a simpler statement and analysis of the conditions. To illustrate, con- sider first the case shown next, where x1 = 0, x2 = 0, and u1 = 0.

If you would like to see another example of using the KKT conditions to solve for an optimal solution, one is provided in the Solved Examples section of the book’s website.

For problems more complicated than the above example, it may be difficult, if not essentially impossible, to derive an optimal solution directly from the KKT conditions. Nevertheless, these conditions still provide valuable clues as to the identity of an optimal solution, and they also permit us to check whether a proposed solution may be optimal.

There also are many valuable indirect applications of the KKT conditions. One of these applications arises in the duality theory that has been developed for nonlinear programming to parallel the duality theory for linear programming presented in Chap. 6. In particular, for any given constrained maximization problem (call it the primal problem), the KKT conditions can be used to define a closely associated dual problem that is a constrained minimization problem. The variables in the dual problem consist of both the Lagrange multipliers ui (i = 1, 2, . . . , m) and the primal variables xj ( j = 1, 2, . . . , n).

In the special case where the primal problem is a linear programming problem, the xj variables drop out of the dual problem and it becomes the familiar dual problem of linear programming (where the ui variables here correspond to the yi variables in Chap. 6). When the primal problem is a convex programming problem, it is possible to establish relationships between the primal problem and the dual problem that are similar to those for linear programming. For example, the strong duality property of Sec. 6.1, which states that the optimal objective function values of the two problems are equal, also holds here. Furthermore, the values of the ui variables in an optimal solution for the dual problem can again be interpreted as shadow prices (see Secs. 4.7 and 6.2); i.e., they give the rate at which the optimal objective function value for the primal problem could be increased by (slightly) increasing the right-hand side of the corresponding constraint. Because duality theory for nonlinear programming is a relatively advanced topic, the interested reader is referred elsewhere for further information.14 You will see another indirect application of the KKT conditions in the next section.