Sequential gradient-restoration algorithm for the minimization of constrained functions—Ordinary and conjugate gradient versions

The problem of minimizing a functionf(x) subject to the constraint (x)=0 is considered. Here,f is a scalar,x ann-vector, and aq-vector. Asequential algorithm is presented, composed of the alternate succession of gradient phases and restoration phases.In thegradient phase, a nominal pointx satisfying the constraint is assumed; a displacement x leading from pointx to a varied pointy is determined such that the value of the function is reduced. The determination of the displacement x incorporates information at only pointx for theordinary gradient version of the method (Part 1) and information at both pointsx and for theconjugate gradient version of the method (Part 2).In therestoration phase, a nominal pointy not satisfying the constraint is assumed; a displacement y leading from pointy to a varied point is determined such that the constraint is restored to a prescribed degree of accuracy. The restoration is done by requiring the least-square change of the coordinates.If the stepsize of the gradient phase is ofO(), then x=O() and y=O(²). For sufficiently small, the restoration phase preserves the descent property of the gradient phase: the functionf decreases between any two successive restoration phases.This research, supported by the NASA Manned Spacecraft Center, Grant No. NGR-44-006-089, and by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-828-67, is a condensation of the investigations reported in Refs. 1 and 2.