An accelerated conjugate direction method to solve linearly constrained minimization problems

摘要

An iterative method is described for the minimization of a continuously differentiable function F(x) of n variables subject to linear inequality constraints. Without any convexity or second-order derivative assumptions it is shown that every cluster point of the sequence {xj} constructed by the method is a stationary point. The method constructs sets of directions which are approximately conjugate. At appropriate points a special step is performed which utilizes the second-order information of the previous conjugate directions to accelerate the rate of convergence. If z is a cluster point of {xj} and F(x) is twice continuously differentiable in some neighborhood of z and the Hessian matrix of F(x) has certain properties, then {xj} converges to z and the rate of convergence is (n−q)-step superlinear, where q is the number of constraints which are active at z. Furthermore, if the Hessian matrix of F(x) satisfies a Lipschitz condition in a neighborhood of z then as a result of the accelerated step, the rate of convergence of {xj} will be (n−q+1)-step cubic.