20. Polynomial worst-case complexity for quasi-Newton Interior Point Methods
Invited abstract in session WB-11: Interior point methods and applications - Part I, stream Interior point methods and applications.
Wednesday, 10:30-12:30Room: B100/5017
Authors (first author is the speaker)
| 1. | Francisco Sobral
|
| Department of Mathematics, State University of Maringá | |
| 2. | Jacek Gondzio
|
| School of Mathematics, University of Edinburgh |
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. 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.
Keywords
- Linear and nonlinear optimization
- Large-scale optimization
Status: accepted
Back to the list of papers