Solving Reduced KKT Systems in Barrier Methods for Linear and QuadraticProgramming

摘要

In barrier methods for constrained optimization, the main work lies in solvinglarge linear systems Kp = r, where K is symmetric and indefinite. We have implemented reduced KKT systems in a primal-dual algorithm for linear programming, based on the sparse indefinite solver MA27 from the Harwell Subroutine Library. Some features of the algorithm are presented, along with results on the netlib LP test set.