NUMERICALLY STABLE DUAL PROJECTION METHODS FOR SOLVING POSITIVE DEFINITE QUADRATIC PROGRAMS.
Item
-
Title
-
NUMERICALLY STABLE DUAL PROJECTION METHODS FOR SOLVING POSITIVE DEFINITE QUADRATIC PROGRAMS.
-
Identifier
-
AAI8023710
-
identifier
-
8023710
-
Creator
-
IDNANI, ASHOK U.
-
Contributor
-
Donald Goldfarb
-
Date
-
1980
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
Powell's efficient algorithm for solving general non-linear programs (NLP) with non-linear constraints which is based upon methods due to Han and Biggs, requires solving a positive definite Quadratic Program (QP) at each iteration. An efficient dual projection (DP) method for solving such a QP is presented. The DP method for QP starts at an optimal, but, in general, infeasible point and seeks feasibility while maintaining optimality. It always takes steps in the direction of the normal of a violated constraint projected onto the currently active constraint manifold. Its finite termination is proved.;Another method which we call the primal-dual projection (P-DP) method is also developed. It incorporates ideas used in our DP method and resorts to solving subproblems by using the primal projection method. It has the advantage of being able to start from an arbitrary point.;Though the DP method is related to Van de Panne and Whinston's dual tableau method for QP, the projection method takes fewer operations per iteration even under the most unfavourable conditions.;An efficient numerically stable implementation using the orthogonal and triangular factors particularly suited for the positive definite QP is presented. Tests on the use of this numerically stable DP method in Powell's algorithm on six published NLP problems produced a 45 to 70 percent reduction in the computational effort over that required by Fletcher's QP algorithm. Rigorous testing on randomly generated problems with as many as 81 variables and 243 constraints of six different primal projection methods, and the DP method show that the DP method is far more efficient. In most cases, the feasible point routine for the primal methods required more computational effort than obtaining the solution using the DP method. When started from the unconstrained minimum, the P-DP method performed slightly worse than the DP method. Finally, a method based on our results is suggested for initiating the dual simplex method for Linear Programs (LP).
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
-
Program
-
Computer Science
