Equivalences among the chi measure, Hoffman constant, and Renegar's distance to ill-posedness
Abstract: We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a procedure to estimate $\chi(A)$ thereby opening an avenue to identify classes of linear programs solvable in polynomial time in the real model of computation.
Keywords: condition measures, chi measure, Hoffman constant, distance to ill-posedness, signed matrices
Category 1: Combinatorial Optimization (Polyhedra )
Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )
Category 3: Convex and Nonsmooth Optimization (Convex Optimization )
Citation: Technical Report, Carnegie Mellon University, May 2019.
Entry Submitted: 05/15/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|