A data-independent distance to infeasibility for linear conic systems
From MaRDI portal
Publication:4959838
DOI10.1137/18M1189464zbMATH Open1437.90120arXiv1805.09494OpenAlexW3014219249MaRDI QIDQ4959838FDOQ4959838
Authors: Vera Roshchina, Javier Peña 
Publication date: 7 April 2020
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1805.09494
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
Numerical optimization and variational techniques (65K10) Quadratic programming (90C20) Convex programming (90C25) Ill-posedness and regularization problems in numerical linear algebra (65F22)
Cites Work
- Stable signal recovery from incomplete and inaccurate measurements
- Some perturbation theory for linear programming
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- A polynomial projection algorithm for linear feasibility problems
- On general minimax theorems
- The gap between the null space property and the restricted isometry property
- A geometric analysis of Renegar's condition number, and its interplay with conic curvature
- The convex geometry of linear inverse problems
- A geometrical stability condition for compressed sensing
- A coordinate-free condition number for convex programming
- Living on the edge: phase transitions in convex programs with random data
- Convex analysis and nonlinear optimization. Theory and examples.
- On the symmetry function of a convex set
- The radius of metric regularity
- Critical objective size and calmness modulus in linear programming
- Foundations of Optimization
- A simple polynomial-time rescaling algorithm for solving linear programs
- Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
- Condition measures and properties of the central trajectory of a linear program
- Linear programming, complexity theory and elementary functional analysis
- A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems
- The Relaxation Method for Solving Systems of Linear Inequalities
- Computational Experience and the Explanatory Value of Condition Measures for Linear Optimization
- Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
- A new condition number for linear programming
- Projective re-normalization for improving the behavior of a homogeneous conic linear system
- Complexity of convex optimization using geometry-based measures and a reference point
- Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
- Robust width: a characterization of uniformly stable and robust compressed sensing
- On condition number theorems in mathematical programming
- It is possible to know a problem instance is ill-posed? Some foundations for a general theory of condition numbers
- On strata of degenerate polyhedral cones. II: Relations between condition measures
- A simplified view of first order methods for optimization
- Solving conic systems via projection and rescaling
- An efficient rescaled perceptron algorithm for conic systems
- An improved version of Chubanov's method for solving a homogeneous feasibility problem
- An extension of Chubanov's algorithm to symmetric cones
- An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming
- A Condition Number for Multifold Conic Systems
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)
