Karush, Kuhn, and Tucker

This chapter provides an informal discussion of the basic concepts behind the minimization of a function F x) vith constrained variables x. The necessary and sufficient conditions to solve a constrained minimization problem are called KKT conditions (by Karush, Kuhn, and Tucker) or Fritz John conditions in certain specific situations. 

The Attic method is based on the necessary conditions by Karush, Kuhn, and Tucker (KKT) applied to a problem, which is linear in its objective function and constraints. 

One of the most important theoretical results in optimization are the Karush, Kuhn and Tucker conditions. They must be satisfied at any optimum, local or global, of any linear and most nonlinear programs. The vector or e K satisfies these conditions for the program (A.l) if there exists vectors fi eW" and X e such that... 

The reader may refer to the follo ving references for further and mathematically formal studies (Karush, 1939 Kuhn and Tucker, 1951 Nocedal and Wright, 2000 Bazaraa et al, 2006). 

Now consider the imposition of inequality [g(x) < 0] and equality constraints 7i(x) = 0] in Fig. 3-55. Continuing the kinematic interpretation, the inequality constraints g(x) < 0 act as fences in the valley, and equality constraints h(x) = 0 act as "rails. Consider now a ball, constrained on a rail and within fences, to roll to its lowest point. This stationary point occurs when the normal forces exerted by the fences [- Vg(x )] and rails [- V/i(x )] on the ball are balanced by the force of gravity [— Vfix )]. This condition can be stated by the following Karush-Kuhn-Tucker (KKT) necessary conditions for constrained optimality ... 

The first-order necessary conditions for problems with inequality constraints are called the Kuhn-Tucker conditions (also called Karush-Kuhn-Tucker conditions). The idea of a cone aids the understanding of the Kuhn-Tucker conditions (KTC). A cone is a set of points R such that, if x is in R, Tx is also in R for X 0. A convex cone is a cone that is a convex set. An example of a convex cone in two dimensions is shown in Figure 8.2. In two and three dimensions, the definition of a convex cone coincides with the usual meaning of the word. 

Under this assumption, (X,y) e S x R " must be an optimal solution that is, the solution that maximizes and minimizes the functions, respectively, for Eqs. (l)-(2) if and only if it satisfies the Karush-Kuhn-Tucker condition ... 

Remark 1 Note that the saddle point sufficiency conditions do not require either additional convexity assumptions or a constraint qualification like condition. Note also that the saddle point sufficiency conditions do not require any differentiability on the Lagrange function. If in addition, the functions /(jc), h(x),g(x) are differentiable, and hence the Lagrange function is differentiable, and (3c, A,p) is a Karush-Kuhn-Tucker Saddle point, then it is a Karush-Kuhn-Tucker point [i.e., it is a solution of (3.3) and it satisfies the constraint qualification]. 

Quadratic programming is discussed in Chapter 11. The quadratic programming methods are implemented by handling the numerical evaluation of Hessian in a novel way. Reduced gradient and gradient projection are described as conventional methods they are then compared to the novel proposed approach based on the Karush-Kuhn-Tucker direction projection method. It represents the basic core for the development of successive quadratic programming (SQP) methods. 

Control variables are discretized at the same level as the state variables, and the Karush-Kuhn-Tucker (KKT) conditions of the simultaneous NLP are consistent with the optimality conditions of the discretized variational problem. 

---