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