A data-independent distance to infeasibility for linear conic systems
From MaRDI portal
Publication:4959838
Abstract: We offer a unified treatment of distinct measures of well-posedness for homogeneous conic systems. To that end, we introduce a distance to infeasibility based entirely on geometric considerations of the elements defining the conic system. Our approach sheds new light on and connects several well-known condition measures for conic systems, including {em Renegar's} distance to infeasibility, the {em Grassmannian} condition measure, a measure of the {em most interior} solution, and other geometric measures of {em symmetry} and of {em depth} of the conic system.
Recommendations
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
- The Structured Distance to Ill-Posedness for Conic Systems
- A geometric analysis of Renegar's condition number, and its interplay with conic curvature
- On the Complexity of Computing Estimates of Condition Measures of a Conic Linear System
Cites work
- A Condition Number for Multifold Conic Systems
- A coordinate-free condition number for convex programming
- A geometric analysis of Renegar's condition number, and its interplay with conic curvature
- A geometrical stability condition for compressed sensing
- A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems
- A new condition number for linear programming
- A polynomial projection algorithm for linear feasibility problems
- A simple polynomial-time rescaling algorithm for solving linear programs
- A simplified view of first order methods for optimization
- An efficient rescaled perceptron algorithm for conic systems
- An extension of Chubanov's algorithm to symmetric cones
- An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming
- An improved version of Chubanov's method for solving a homogeneous feasibility problem
- Complexity of convex optimization using geometry-based measures and a reference point
- Computational Experience and the Explanatory Value of Condition Measures for Linear Optimization
- Condition measures and properties of the central trajectory of a linear program
- Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
- Convex analysis and nonlinear optimization. Theory and examples.
- Critical objective size and calmness modulus in linear programming
- Foundations of Optimization
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- It is possible to know a problem instance is ill-posed? Some foundations for a general theory of condition numbers
- Linear programming, complexity theory and elementary functional analysis
- Living on the edge: phase transitions in convex programs with random data
- On condition number theorems in mathematical programming
- On general minimax theorems
- On strata of degenerate polyhedral cones. II: Relations between condition measures
- On the symmetry function of a convex set
- Projective re-normalization for improving the behavior of a homogeneous conic linear system
- Robust width: a characterization of uniformly stable and robust compressed sensing
- Solving conic systems via projection and rescaling
- Some perturbation theory for linear programming
- Stable signal recovery from incomplete and inaccurate measurements
- The Relaxation Method for Solving Systems of Linear Inequalities
- The convex geometry of linear inverse problems
- The gap between the null space property and the restricted isometry property
- The radius of metric regularity
- Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
- Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
Cited in
(8)- A geometric analysis of Renegar's condition number, and its interplay with conic curvature
- Distance to ill-posedness in linear optimization via the Fenchel-Legendre conjugate
- Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
- Feasible distance in non-conic convex optimization problems
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- The Condition Number of Riemannian Approximation Problems
- Characterizations of interiors of feasible and infeasible data instances and feasibility for conic linear programming
- The Structured Distance to Ill-Posedness for Conic Systems
This page was built for publication: A data-independent distance to infeasibility for linear conic systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4959838)
