Optimization Online


Equivalences among the chi measure, Hoffman constant, and Renegar's distance to ill-posedness

Javier Pena(jfp***at***andrew.cmu.edu)
Juan Vera(j.c.veralizcano***at***uvt.nl)
Luis Zuluaga(luis.zuluaga***at***lehigh.edu)

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.

Download: [PDF]

Entry Submitted: 05/15/2019
Entry Accepted: 05/15/2019
Entry Last Modified: 05/15/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society