Barrier Methods for Large-Scale Quadratic Programming
STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB
Pagination or Media Count:
We present several new algorithms for solving the general large-scale quadratic programming QP problem. A feature of QP problems is the presence of linear inequality constraints, which introduce a combinatorial aspect to the problem. Currently the most common approach to solving QP problems is to apply active-set methods, in which only some of the inequalities are used to produce a search direction at each stage. The combinatorial element is therefore inherent. As problems become larger, there is a potential for an excessive number of iterations and consequent inefficiency. In contrast, we use the new familiar barrier function approach, which circumvents the combinatorial aspect by introducing a barrier transformation involving all of the inequalities. The barrier term enforces satisfaction of the inequalities by modifying the objective function. The transformed problem is solved by a modified Newton method applied to the nonlinear equations defining feasibility and optimality. The main computation at each iteration of the new algorithms is the solution of an indefinite system of linear equations. Barrier methods are known to lead to ill-conditioned systems. However, we show by a special sensitivity analysis that the particular manner in which we have formulated the barrier transformation leads to ill-conditioning that is benign.
- Operations Research