A condition-based algorithm for solving polyhedral feasibility problems

DOI10.1016/J.JCO.2014.02.001MaRDI QIDQ457560zbMATH OpenOpenAlexFDO

Authors Negar Soheili, Javier Peña

Publication date 29 September 2014

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2014.02.001

zbMATH Keywords

interior-point methodslinear inequalitiesGoldman-Tucker partition

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Linear programming (90C05) Interior-point methods (90C51)

Recommendations

• Condition numbers for polyhedra with real number data
• Improved complexity results on solving real-number linear feasibility problems
• A polynomial projection algorithm for linear feasibility problems
• On the Complexity of Computing Estimates of Condition Measures of a Conic Linear System
• Condition number based complexity estimate for solving polynomial systems

Cites work

• scientific article; zbMATH DE number 1090880 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A new condition number for linear programming
• Computing approximate solutions for convex conic systems of constraints
• Condition Numbers, the Barrier Method, and the Conjugate-Gradient Method
• Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
• Condition numbers for polyhedra with real number data
• Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
• Condition. The geometry of numerical algorithms
• Linear programming, complexity theory and elementary functional analysis
• On strata of degenerate polyhedral cones. I: Condition and distance to strata
• The Relaxation Method for Solving Systems of Linear Inequalities
• Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
• Unifying Condition Numbers for Linear Programming

Cited in

(5)

• A robust interior point method for computing the analytic center of an ill-conditioned polytope with errors
• Refining the partition for multifold conic optimization problems
• It is possible to know a problem instance is ill-posed? Some foundations for a general theory of condition numbers
• Condition numbers for polyhedra with real number data
• Inside-ellipsoid outside-sphere (IEOS) model for general bilinear feasibility problems: feasibility analysis and solution algorithm

This page was built for publication: A condition-based algorithm for solving polyhedral feasibility problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q457560)