Interior-Point Abstracts

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.