##
Some Characterizations
and Properties of the 'Distance to Ill-Posedness' and the Condition
Measure of a Conic Linear System

###
Robert M. Freund and Jorge R. Vera

A conic linear system is a system of the form $$P: \ \
{\rm find}~ x ~{\rm
that~solves}~ b - Ax \in C_{Y}, ~ x \in C_{X},$$ where $C_{X}$ and
$C_{Y}$ are closed convex
cones, and the data for the system is $d=(A,b)$. This system
is``well-posed" to the extent that
(small) changes in the data $(A,b)$ do not alter the status of the
system (the system remains
solvable or not). Intuitively, the more well-posed the system is, the
easier it should be to solve
the system or to demonstrate its infeasibility via a theorem of the
alternative. Renegar defined
the ``distance to ill-posedness," $\rho(d)$, to be the smallest
distance of the data
$d=(A,b)$ to other data $\bar d=(\bar A,\bar b)$ for which the system
$P$ is ``ill=posed," i.e.,
$\bar d=(\bar A,\bar b)$ is in the intersection of the closure of
feasible and infeasible instances
$d'=(A',b')$ of $P$. Renegar also defined the ``condition measure" of
the data instance $d$ as
${\cal C}(d)\ {\underline {\underline \Delta}}\|d\|/\rho(d)$, and showed
that this measure is a
natural extension of the familiar condition measure associated with
systems of linear equation.
This study presents two categories of results related to $\rho(d)$, the
distance to ill-posedness,
and ${\cal C}(d)$, the condition measure of $d$. The first category of
results involves the
approximation of $\rho(d)$ as the optimal value of certain mathematical
programs. We present ten
different mathematical programs each of whose optimal values provides an
approximation of $\rho(d)$
to within certain constant factors, depending on whether $P$ is feasible
or not. The second
category of results involves the existence of certain inscribed and
intersecting balls involving the
feasible region of $P$ or the feasible region of its alternative system,
in the spirit of the
ellipsoid algorithm. These results roughly state that the feasible
region of $P$ (or its
alternative system when $P$ is not feasible) will contain a ball of
radius $r$ that is itself no
more than a distance $R$ from the origin, where the ratio $R/r$
satisfies $R/r \leq O(n\ {\cal
C}(d))$, and such that $r \geq \Omega \left( \frac{1}{n\ {\cal C}(d)}
\right)$ and $R \leq O(n\ {\cal
C}(d))$, where $n$ is the dimension of the feasible region. Therefore
the condition measure ${\cal
C}(d)$ is a relevant tool in proving the existence of an inscribed ball
in the feasible region of
$P$ that is not too far from the origin and whose radius is not too
small.
For a hard copy, send email to rfreund@mit.edu.