A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms

DOI10.1007/s10107-007-0141-5zbMath1151.90023OpenAlexW2165657556MaRDI QIDQ930345

Takashi Tsuchiya, Renato D. C. Monteiro

Publication date: 30 June 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-007-0141-5

zbMATH Keywords

adaptive-step primal-dual interior-point algorithms for linear programmingMizuno-Todd-Ye predictor-corrector algorithm for linear programming

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51)

Related Items

An analogue of the Klee-Walkup result for sonnevend's curvature of the central path, Two wide neighborhood interior-point methods for symmetric cone optimization, Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs, A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy, Curvature integrals and iteration complexities in SDP and symmetric cone programs, Doubly autoparallel structure and curvature integrals. Applications to iteration complexity for solving convex programs, Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes, The central curve in linear programming, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate, A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On scaled projections and pseudoinverses
• On the complexity of following the central path of linear programs by linear extrapolation. II
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• A modified layered-step interior-point algorithm for linear programming
• On the condition numbers for polyhedra in Karmarkar's form
• A primal-dual interior point method whose running time depends only on the constraint matrix
• A note on properties of condition numbers
• Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
• Path-Following Methods for Linear Programming
• Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Global Convergence of the Affine Scaling Algorithm for Convex Quadratic Programming
• A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
• On Linear Least-Squares Problems with Diagonally Dominant Weight Matrices
• On the Relationship Between the Curvature Integral and the Complexity of Path-Following Methods in Linear Programming
• A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm
• A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems