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 (11)

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

This page was built for publication: 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