A primal-dual interior point method whose running time depends only on the constraint matrix

DOI10.1007/BF02592148zbMath0868.90081OpenAlexW2059969305MaRDI QIDQ1352307

Yinyu Ye, Stephen A. Vavasis

Publication date: 1996

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

Full work available at URL: https://doi.org/10.1007/bf02592148

zbMATH Keywords

interior point methodstrongly polynomial timecharacterization of the central pathlayered least squares

Mathematics Subject Classification ID

Interior-point methods (90C51)

Related Items (41)

Analysis of some interior point continuous trajectories for convex programming ⋮ An analogue of the Klee-Walkup result for sonnevend's curvature of the central path ⋮ The weighted uncapacitated planned maintenance problem: complexity and polyhedral properties ⋮ A note on properties of condition numbers ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Log-Barrier Interior Point Methods Are Not Strongly Polynomial ⋮ On circuit diameter bounds via circuit imbalances ⋮ Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs ⋮ A polynomial arc-search interior-point algorithm for linear programming ⋮ Linear programming, complexity theory and elementary functional analysis ⋮ An update-and-stabilize framework for the minimum-norm-point problem ⋮ On Chubanov's Method for Linear Programming ⋮ A complementarity partition theorem for multifold conic systems ⋮ Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory ⋮ 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 ⋮ A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem ⋮ A simpler and tighter redundant Klee-Minty construction ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ The Convergent Generalized Central Paths for Linearly Constrained Convex Programming ⋮ Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes ⋮ How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds ⋮ The central curve in linear programming ⋮ On the probabilistic complexity of finding an approximate solution for linear programming ⋮ Probabilistic analysis of condition numbers for linear programming ⋮ Improved complexity results on solving real-number linear feasibility problems ⋮ Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem ⋮ Examples of ill-behaved central paths in convex optimization ⋮ New characterizations of Hoffman constants for systems of linear constraints ⋮ Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem ⋮ A strongly polynomial algorithm for approximate Forster transforms and its application to halfspace learning ⋮ Minimizing convex functions with rational minimizers ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Spectrally constrained optimization ⋮ On circuit diameter bounds via circuit imbalances ⋮ On strata of degenerate polyhedral cones. I: Condition and distance to strata ⋮ Further development of multiple centrality correctors for interior point methods ⋮ Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming ⋮ A modified layered-step interior-point algorithm for linear programming ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ On the condition numbers for polyhedra in Karmarkar's form ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An active-set strategy in an interior point method for linear programming
• On the finite convergence of interior-point algorithms for linear programming
• A new polynomial-time algorithm for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• On bounds for scaled projections and pseudoinverses
• A geometric property of the least squares solution of linear equations
• A polynomial-time algorithm, based on Newton's method, for linear programming
• On scaled projections and pseudoinverses
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• On the complexity of following the central path of linear programs by linear extrapolation. II
• On the complexity of approximating extremal determinants in matrices
• Condition numbers for polyhedra with real number data
• A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Path-Following Methods for Linear Programming
• A Short-Cut Potential Reduction Algorithm for Linear Programming
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Stable Numerical Algorithms for Equilibrium Systems
• On Linear Least-Squares Problems with Diagonally Dominant Weight Matrices
• A Surface of Analytic Centers and Primal-Dual Infeasible-Interior-Point Algorithms for Linear Programming
• Stable Finite Elements for Problems with Wild Coefficients
• A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm
• Systems of distinct representatives and linear algebra

This page was built for publication: A primal-dual interior point method whose running time depends only on the constraint matrix