On improving the accuracy of primal-dual interior point methods for linear programming

[摘要] Implementations of the primal-dual approach in solving linear programming problems still face issues in maintaining numerical stability and in attaining high accuracy. The major source of numerical problems occurs during the solving of a highly ill-conditioned linear system within the algorithm. We perform a numerical investigation to better understand the numerical behavior related to the solution accuracy of an implementation of an infeasible primal-dual interior-point (IPDIP) algorithm in LIPSOL, a linear programming solver. From our study, we learned that most test problems can achieve higher than the standard 10-8 accuracy used in practice, and a high condition number of the ill-conditioned coefficient matrix does not solely determine the attainable solution accuracy. Furthermore, we learned that the convergence of the primal residual is usually most affected by numerical errors. Most importantly, early satisfaction of the primal equality constraints is often conducive to eventually achieving high solution accuracy.

[发布机构] Rice University

[效力级别] Operations