Downloaded from https://www.everyspec.com AMCP 706-197 J ditions form the bais for the development of mum, no small, allowable change in the prob- 1- many computational procedures. In addition, lem variables can improve the objective func- the criteria for stopping many procedures tion. To illustrate this, consider the nonlinear (i.e., for recognizing when a local constrained programming problem shown in Fig. 12-11. It optimum has been achieved) are derived di- is evident that the optimum is at the intersec- rectly from these conditions. tion of the two constraints. At (1,1) in Fig.
The concept of a cone can be used to help 12-11 the set of all feasible directions lies visualize the Kuhn-Tucker conditions. A cone between the line - x - y + 2 = 0 and the tan- is defined as a set of points R such that, if x is gent line y = 2X - 1. In other words, this set in R, ,x is also in R for X > 0. A convex cone is the cone generated by these two lines. The R has the additional property that if x and y vector -Vf points in the direction of the are in R, x + y is also in R. The set of all maximum rate of decrease of the objective non-negative linear combinations of a finite function f(x,y).
A move along any direction set of vectors forms a convex cone; i.e., the making an angle of less than 90 deg with -V f set R is a convex cone, where will decrease f(xy). Thus, at the optimum, there can be no feasible direction with an R = {xix =(4x7 + + angle of less than 90 deg between it and -V f. (- 7 0; M}. The negative gradients - V g, and - V g 2 The vectors x 1 ,x 2 , ..,x. are called the gener- are also shown in Fig. 12-11;and - Vf is con- ators of the cone. For example, the convex tained in the cone generated by these negative cone of Fig. 12-10 is generated by the vectors gradient. If - V f were not contained in the (2,1) and (2,4).
Any vector that can be ex- cone, but slightly above -V g 2 , it would pressed as a non-negative linear combination make an angle of less than 90 deg with a feasi- of these vectors lies in this cone. In Fig. 12-10 ble direction just below the line -x - y + 2 = the vector (4,5) in the cone is given by 0. Similarly, if -V f were slightly below -V tn g, it would make an angle of less than 90 deg - (4,5) = 1 (2,1) + 1. (2,4). (12-18) with a feasible direction just above the line y = 2x - 1.
Neither of these cases can occur at The Kuhn-Tucker conditions are predi- an optimum point, and both cases are ex- cated on the fact that at any constrained opti- cluded if and only if - V f lies within the cone generated by - V g, and - V g 2 . This is the geometric statement of the Kuhn-Tucker con- YI ditions; a necessary condition for x to mini- mize f(x), subject to the constraints g(x) > 0 where i=l,- ,,r, is that the gradient V f lie within the cone generated by the gradients of the binding constraints.
5 (4,-- In an algebraic statement of the Kuhn- (2,4) ,Tucker conditions, since V f lies within the cone described, it must be a nonnegative line- 3 ar combination of the gradients of the binding constraints. In other words, there must exist 2 numbers u, > 0 such that 2 ,fx* U, vg,(x*) 1 (2.1) Vg(12-19) S1 2 3 4 X The shaded area represents a cone generated where the binding constraints a e assumed to by vectors (2,1) and (2,4). be g,," - .,gp,(p r). This relationship can be extended to include all constraints by defin. FIGURE 12.10. Convex Cone ing the coefficient u, to be zero if1g(x*)> 0. \ , 12-13