On the Complexity of Computing Estimates of Condition Measures of a Conic Linear System

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: nd x that satises Ax = b; x 2 CX , 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 CX and C X . Both algorithms will compute a relative -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. AMS Subject Classication: 90C, 90C05, 90C60 K..