Polynomial worst-case iteration complexity of quasi-Newton primal-dual interior point algorithms for linear programming
From MaRDI portal
Publication:6408204
arXiv2208.08771MaRDI QIDQ6408204FDOQ6408204
Jacek Gondzio, Author name not available (Why is that?)
Publication date: 18 August 2022
Abstract: Quasi-Newton methods are well known techniques for large-scale numerical optimization. They use an approximation of the Hessian in optimization problems or the Jacobian in system of nonlinear equations. In the Interior Point context, quasi-Newton algorithms compute low-rank updates of the matrix associated with the Newton systems, instead of computing it from scratch at every iteration. In this work, we show that a simplified quasi-Newton primal-dual interior point algorithm for linear programming enjoys polynomial worst-case iteration complexity. Feasible and infeasible cases of the algorithm are considered and the most common neighborhoods of the central path are analyzed. To the best of our knowledge, this is the first attempt to deliver polynomial worst-case iteration complexity bounds for these methods. Unsurprisingly, the worst-case complexity results obtained when quasi-Newton directions are used are worse than their counterparts when Newton directions are employed. However, quasi-Newton updates are very attractive for large-scale optimization problems where the cost of factorizing the matrices is much higher than the cost of solving linear systems.
This page was built for publication: Polynomial worst-case iteration complexity of quasi-Newton primal-dual interior point algorithms for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408204)
