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

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 … Read more

On the Grassmann condition number

We give new insight into the Grassmann condition of the conic feasibility problem \[ x \in L \cap K \setminus\{0\}. \] Here $K\subseteq V$ is a regular convex cone and $L\subseteq V$ is a linear subspace of the finite dimensional Euclidean vector space $V$. The Grassmann condition of this problem is the reciprocal of the … Read more

Local convergence for alternating and averaged nonconvex projections

The idea of a finite collection of closed sets having “strongly regular intersection” at a given point is crucial in variational analysis. We show that this central theoretical tool also has striking algorithmic consequences. Specifically, we consider the case of two sets, one of which we assume to be suitably “regular” (special cases being convex … Read more

Perturbations and metric regularity

A point x is an approximate solution of a generalized equation [b lies in F(x)] if the distance from the point b to the set F(x) is small. Metric regularity of the set-valued mapping F means that, locally, a constant multiple of this distance bounds the distance from x to an exact solution. The smallest … Read more

Unifying Condition Numbers for Linear Programming

In recent years, several condition numbers were defined for a variety of linear programming problems based upon relative distances to ill-posedness. In this paper we provide a unifying view of these condition numbers. To do so, we introduce yet another linear programming problem and show that its distance to ill-posedness naturally captures the most commonly … Read more