New complexity analysis of the primal-dual Newton method for linear optimization

DOI10.1023/A:1019280614748zbMath0990.90065OpenAlexW1536070618MaRDI QIDQ5933827

Cornelis Roos, Jiming Peng, Tamás Terlaky

Publication date: 14 June 2001

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1019280614748

zbMATH Keywords

interior-point methodprimal-dual methodlinear optimizationpolynomial complexityproximity measure

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interior-point methods (90C51)

Related Items (21)

A new infeasible interior-point algorithm with full step for linear optimization based on a simple function ⋮ A full-step interior-point algorithm for linear complementarity problem based on a simple function ⋮ Complexity analysis and numerical implementation of large-update interior-point methods for SDLCP based on a new parametric barrier kernel function ⋮ A full-step interior-point algorithm for second-order cone optimization based on a simple locally kernel function ⋮ On central-path proximity measures in interior-point methods ⋮ A full Nesterov-Todd-step feasible primal-dual interior point algorithm for convex quadratic semi-definite optimization ⋮ A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function ⋮ A full-Newton step interior-point algorithm based on modified Newton direction ⋮ A new kind of simple kennel function yielding good iteration bounds for primal-dual interior-point methods ⋮ A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO ⋮ An infeasible interior-point algorithm with full-Newton step for linear optimization ⋮ A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function ⋮ Interior Point Methods for Nonlinear Optimization ⋮ An easy way to teach interior-point methods. ⋮ A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP ⋮ New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction ⋮ Interior-point methods for CartesianP_*(κ)-linear complementarity problems over symmetric cones based on the eligible kernel functions ⋮ Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions ⋮ Complexity analysis and numerical implementation of a full-Newton step interior-point algorithm for LCCO ⋮ A primal-dual interior-point method based on a new kernel function for linear complementarity problem ⋮ A new class of polynomial primal-dual methods for linear and semidefinite optimization

This page was built for publication: New complexity analysis of the primal-dual Newton method for linear optimization