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]


 [DVI]  [PS]  [IP PAGE]  [SEARCH AGAIN]