ON THE COMPLEXITY OF COMPUTING ESTIMATES OF CONDITION
MEASURES OF A CONIC LINEAR SYSTEM
Robert M. FREUND and Jorge R. VERA
In this paper we present two algorithms for computing estimates of
condition measures for a convex feasibility problem $P(d)$ in the
standard primal form: find $x$ that satisfies $Ax=b, x \in C_X$,
where $d=(A,b)$ is the data for the problem $P(d)$. One algorithm
is an interior-point algorithm using a self-concordant barrier
function for the dual cone $C_X^*$. The other algorithm is a
variant of the ellipsoid algorithm using separation oracles for
the cones $C_X$ and $C_X^*$. Both algorithms will compute a
relative $\alpha$-estimate of the ``distance to ill-posedness'' of
the problem instance, with complexity bounds that are linear in
$\ln(C(d))$ (where $C(d)$ is the condition number of the data $d$
for $P(d)$), plus other quantities that arise naturally in
consideration of the problem $P(d)$. The main conclusion of this
work is that computing an estimate of the condition measures of
$P(d)$ is essentially not much harder than computing a solution of
$P(d)$ itself.
Technical Report 4/99, Dept. of Industrial and System Engineering,
Catholic University of Chile, 1999.
Contact: [email protected]