Barrier Methods for Large-Scale Quadratic Programming
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1991
- Accession Number
- ADA238554
Entities
People
- Dulce B. Ponceleon
Organizations
- Stanford University