A primal-dual interior point method whose running time depends only on the constraint matrix
From MaRDI portal
Publication:1352307
DOI10.1007/BF02592148zbMath0868.90081OpenAlexW2059969305MaRDI QIDQ1352307
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
interior point methodstrongly polynomial timecharacterization of the central pathlayered least squares
Related Items
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, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, 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
