A computational method for the indefinite quadratic programming problem |
| |
Authors: | James R Bunch Linda Kaufman |
| |
Institution: | Department of Mathematics University of California at San Diego La Jolla, California 92093, U.S.A.;Bell Laboratories Murray Hill, New Jersey 07974, U.S.A. |
| |
Abstract: | We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=xTQx+cTx such that ATx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|