(617e) Faster Methods for Solving Large Quadratic Programs

In this work we present a novel method for solving quadratic programs (QPs). Work has been done in the past by our group [Chmielewski and Manousiouthakis, Systems & Control Letters (29) p. 121 – 129, 1996] on the solution to infinite-time linear quadratic optimal control problems. In addition to chemical process control, there are also many problems in statistics and economics which can become quite large (more than 1000 variables and more than 10,000 constraints) and where very efficient computational methods for solving the resulting QPs become necessary.

We present here a proof and algorithm for solving QPs which could potentially present huge savings in computation time in certain problems over traditional (active constraint) methods. The treatment involves using properties of the dual of the QP to simplify the problem into one that is unconstrained and then solving the resulting unconstrained problem from a logical starting point.