next up previous
Next: Development of AI Up: Mathematical Algorithms and Previous: Approximating the Permanent

Interior Point Methods for General Large Scale Quadratic Programming Problems

Paul T. Boggs, Paul D. Domich and Janet E. Rogers, ACMD

Boggs, Domich, Rogers and Witzgall have continued to be active participants in the theoretical and computational aspects of the ongoing worldwide research on methods for solving the linear programming and quadratic programming problems, such as those that frequently arise in the context of airline scheduling, pooling and blending in chemical engineering, heat exchanger and chemical reactor networks, optimal control, mechanical design, entropy, and nonconvex energy optimization. They have obtained excellent results with an interior point method that is applicable for solving a class of such problems that is not currently solved by the primal dual methods being examined by other researchers. Their QP procedure also has application in sequential quadratic programming codes for solving nonlinear programming problems (NLP). Their approach combines several individual search directions to produce an optimal step at each iteration. Their original work, developed for LP, is an effective method that is competitive with the best of the LP algorithms developed elsewhere. Their QP approach has few, if any, competitors in terms of robustness and size of problems that can be efficiently handled.

A manuscript describing this work has been accepted for publication in the Annals of Operations Research special volume on Interior Point Methods for Mathematical Programming. It was also presented at the 15th International Symposium on Mathematical Programming in Ann Arbor, Michigan, and at the University of Colorado Computer Science Department Numerical Analysis Seminar, in Boulder, Colorado.

Boggs, Domich and Rogers are now researching a new approach that will combine their existing methods with a primal-dual approach. NIST IR 5020 describes this work.