Implementation of Interior-point Methods for LP based on Krylov Subspace Iterative Solvers with Inner-iteration Preconditioning

摘要: We apply novel inner-iteration preconditioned Krylov subspace methods to the interior-point algorithm for linear programming (LP). Inner-iteration preconditioners recently proposed by Morikuni and Hayami enable us overcome severe ill-conditioning of equations solved in final phase iterations. The do not suffer from rank-deficiency therefore no preprocessing is necessary even if rows constraint matrix are linearly independent. By means these methods, a new recurrence order omit one matrix-vector product at each step. Extensive numerical experiments conducted over diverse instances 138 LP problems including Netlib, QAPLIB, Mittelmann Atomizer Basis Pursuit collections. largest problem has 434,580 unknowns. It turns out that our implementation more robust than standard public domain solvers SeDuMi (Self-Dual Minimization), SDPT3 (Semidefinite Programming Toh-Todd-Tutuncu) LSMR iterative solver PDCO (Primal-Dual Barrier Method Convex Objectives) without increasing CPU time. method based on succeeds solving fairly large number benchmark libraries under stopping criteria. work also presents extensive test several renowned direct solvers.