Downloaded from https://www.everyspec.com AMCP 706-197 TABLE 12-2 OPTIMIZING CONSTRAINED PROBLEMS Convexity Theormns Vg(''f + eGt > 0 8. Otherwise, define a new set Theorem 1. If 6) is convex, V f( )d-- > 0 of planes to be associated with 9, t hee by deleting from the present set {th )k} y- one plane for which uj 0, and If the minimum vlue of t > 0, no return to step 4. is convex for all scalars (k). such direction exists and the con- Te Fieco-McCormick Conditions Theorem 2. The intersection putation is terminated. The current of any number of cone sets is point is generally a local constrain- 1. The interior of the con. convex, ed minimum. If. t 0 proceed to straintset is non-empty. step 5.
2. The functions f and gi are Thecrem 3. If (X) has co0- 5. Compute a step length a twice continuously differentiable. tinuous first and second derivatives, by minimizing f(; + -) subject to 3. The set of points in the the following tl'hr-e statements are the condition that Ti + oiF violates constraint set for which f(-) k is all equivalent: no constraints. bounded for all k a. f() is convex; 6. Using a 1 , compute a succes- 4. The function f(-) is bound. b. Jl) >f(x- 2 ) + Vf'(j). sorpoint.9 xi +ajT andre- ed below for f in the constralnt set. (k4 - i for any two turn to step2 with 1 replaced by i + 0 If conditions 1 throzgh 4 ponts E' 1 ,x 2 ; 1. hold, at leat one finite local mini- c.
the matrix of second par- Rosmns Gradient-Projection mumiof rar) [see Eq (24)] exists tial derivatives of f - isRoe sGrdntPjcin tial erivtive of holI within the constraint set for any r positive semideflnite for all > 0. Furthermore, f is monoto- points '. 1. Start at a point x 0 that sat- nically nonincreasing as r is reduced Theorem 4. A positive semi- isfies the constraints. The ith itera- (Ref. 25). tion, i - 0, 1, ... proceeds as fol- 5. f(-) is convex. dctiwte quadratic form is convex, lows: 6. The g(x) are concave func- Theorem 5. A positive linear 2. Compute V ffl). tions. combination of convex funetions is 7. P(' ) is strictly convex in convex. 3.
Determine which con- the interioi of the constraint set for Theorem 6. A function (-) I stmints are binding at F, and call any r > 0. convex If and only if the one- these the constraints associated 0 If conditions 6 though 7 dimensional function g() - f(o" + with Y,. also hold, there is a convex pro- disconve fo all f + 4. Compute il, the projection gramming problem; any local mini- c)is convex for all fixed f" and. of - V f(f), on the intersection of mum is global, and the procedure Zoutendijk's Method of Feasible the constraints associated with the converges to the global minimum as Directions point z. r -) 0. 5. If 71 is not the zero vector, 1.
Start with an initial point compute a step length a, by mini- The Fiacco-McCormick Method x o which satisfies all constraints, mizing g(,) - f(f + o ) subject to 1. Start with 'o, which must For i - 0, 1, .;., do the following the condition that x 5 + oi, violates be strictly inside the constaint set, steps. no constraints. This determines a and r, > 0. Let i - 1, 2,.... 2. At the current pqint, x, new point 9'+ "xIL + c. Return 2. Mninize P(f, r), starting determine which constraints VV to step 2 and replace i with i + 1. from .1, and subject to no con- binding (or almost binding) and 6. IfX zero, then straints. form the set I containing their I ri i z then 3. indices. V[(F) - u; / 3.
Reducer by chosingrj+1 3. Choose aset of 0(0' ri, and return to step 2 with i 1) used to steer away from nonlin. which is a linear combination of replaced by i + 1. ear constraint boundaries, normals F to the binding constraint 4. btop if the change in the 4, Compute a new usable planes- objective function fails to e ceed a feasible direction, F,, by solving the 7. If all uj > 0, then fj is the specified value for some predeter. direction-finding problem of mini. solution of the problem, for the mined number of Iterations. mizing t subject to the conditions Kuhn-Tucker conditions are satis- 2-ied. S 12-12