A Parametric Method for Semi-Definite Quadratic Programs

[摘要] This paper describes a parametric method for solving semi-definite quadratic programs which seems to be well suited for problems with a large number of constraints. All computations are performed by pivotal operations on a tableau, or more efficiently on an inverse, whose size may be considerably smaller when compared to other methods of solution. Updating of this inverse is accomplished by elementary row and column operations. Programming of the proposed algorithm for a computer is facilitated by the ability to make efficient use of the product form of the inverse mechanism of most commercially available linear programming systems. An existing solution to a slightly perturbed problem, if available, may be used as a starting solution for a new problem, with a possible substantial reduction of the required computational effort. Finally, an obvious but rather important advantage of the method is its use in post-optimality studies involving the requirements vector and/or the linear part of the objective function.

[发布机构] University of Wisconsin-Madison Department of Computer Sciences