Downloaded from https://www.everyspec.com AMCP 76-17 If this is done, the product ug,(x*) is zero for arises: proceeding in tha negative gradient di- all i. Eq. 12-19 is the form in which the rection at x, would violate the constraints. Kuhn-Tucker conditions usually are stated. There are many feasible directions in which If a minimization problem with inequality we could move from x 1 ; any direction point- constraints is a convex programming problem ing into the constraint set or along a con- whose constraint set has a nonempty interior, straint boundary would do.
The "best" direc- the Kuhn-Tucker conditions are both neces tion we can choose, however, is that feasible sary and sufficient for a point x to be a con- direction along which x 1 ) decreases most strained minimum (Ref. 15). rapidly, i.e., along which - srVf(x 1 ) is mini- mized. This is the feasiL.e direction that Most existing nonlinear programming makes the smallest angle with - Vf(x 1 ), and methods can be classified either as methods of is the projection of - V f(x 1 ) on the con- feasible direction (such as Zoutendijk's proce- straint boundary.
dure and Rosen's gradient projection method) or as penalty function techniques (such as the The farthest we can move along s I with- out crossing the constraint boundary is to the Fiacco-McCormick method). point x. Repeating the smallest angle proce- 12-3.5 METHODS OF FEASIBLE DIREC- dure leads us to xj with negative gradient TIONS - V f(x). At this point there is no usable fea- sible direction, since no feasible direction at Methods of feasible directions use the X 8 makes an angle of less than 90 deg with same general approach as the techniques of -V f(x 3 ).
In this case, x3 happens to be at unconstrained minimization, but they are the global minimum of f(x) over the con- constructed to deal with -inequality con- straint set. straints. The idea is to pick a starting point The global minimum is not, however, al- that satisfies the constraints, and then to f'id ways reached by this procedure. In this exam- a direction along which a small move violates pie, the same procedure, starting with yo in no constraint and, at the same time, improves Fig. 12-12, leads to a local minimum at the the objective function. We then move some point a, which is distinct from the global min- distance in the selected direction, obtaining a imum at x 3 .
This example illustrates the diffi- new and better point, and repeat the proce- culties such procedure may encounter with dure until we reach a point from which the local optima. These difficulties are common objective function cannot be improved with- to all methods, and one can be sure of avoid- out vic lating at least one constraint. In gener- ing them only for a convex programming al, such a point is a constrained local mini- problem. mum of the problem, not necessarily a global minimum for the entire region of interest.
12-3.5.1 Zoutendijk's Procedure A direction along which a small move can be made without violating any constraints is Consider the problem of minimizing f(x), called a feasible direction, while a direction subject to the inequality constraints g,(x) > 0; which is feasible and at the same time irm- i1,..,m. If a starting point x o that satisfies proves the objective function is called a usa- the constraints is assumed, the problem is to ble, feasible direction. Since there are many choose a vector s which is both usable and ways of choosing such directions, there are feasible. Let I be a set of indices i, for which many different methods-of-feasible-directions. g,(xo) = 0.
For all feasible vectors s, a small trated in Fig. 12-12. The starting point is x o , set I, move along the vector from x o makes no An iterative procedure of this type is ilius- binding constraint negative; i.e., for all i in the and the usable, feasible direction chosen is d I g(X) so= - vf(Xo) (12-20) da [g1 (x 0 + s)] = v8T(x 0 )s ; 0 "" ' ka = 0(12-21) I The procedure is to choose the distance moved along s o so as to minimize f, and tJe where is the scalar parameter that deter- first improved point is x,. Here, a problem mines how far along s one might go. A usable, 12-15