The Parallel Algorithm for an Improved SUMT Method for Equality Constrained Optimization

J.-J. Chen, L. Jia, J.-C. Chen, W.-W. Cheng (USA), and H.-M. Lee (Taiwan)

Keywords

SUMT method, constrained optimization, penalty function, quasiNewton method, Armijo line search, BFGS. r : penalty parameter gƒ (x) : gradient of f(x) Jc(x): Jc(x) = [∂ci(x)/∂xj],the constraints Jacobian

Abstract

: This paper presents a detailed derivation and description of an improved SUMT method for solving equality constrained optimization problem. The method is based upon the quadratic penalty function, but uses orthogonal transformations, derived from the Jacobian matrix of the constraints, to deal with the numerical ill conditioning that affects the methods of this type. The newly developed parallel algorithm is issued to find the optimal n-ary dimension variables for the constrained function. At each iteration of the new algorithm, the orthogonal search direction is determined by a quasi Newton method which can avoid the necessity of solving a set of equations and the step-length is chosen by a Armijo line search. The matrix which approaches the inverse of the projected Hessian of composite function is updated by means of the BFGS formula from iteration to iteration. As the penalty parameter approaches zero, the projected inverse Hessian has a special structure which can guarantee us to obtain the search direction accurately even if the Hessian of composite function is ill-conditioned in the former SUMT methods. where c(x)T c(x)/(2r) is the quadratic penalty term and r is the penalty parameter. It is known that if x* is the solution of (1) and x*(r) is the unconstrained minimum of (2), then under mild conditions [4, 10, 11], lim x* (r) = x* r→0 Thus, we deal with the unconstrained problem minimize φ (x,r) (2) instead of (1). The method we use to solve (2) will generate a sequence that converges (as r→0) to solution x* of the original problem (1). 2 Basic Idea In order to simplify our discussion, we introduce the following notation: f(x) : objective function c(x) : [ci(x)], the constraints vector φ (x, r) : composite function (φ (x, r) = f(x) + c(x) T c(x)/(2r))

Important Links:



Go Back