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

Source abstract

Condition numbers based on the “distance to ill-posedness” ρ(d) have been shown to play a crucial role in the theoretical complexity of solving convex optimization models. In this paper, we present two algorithms and corresponding complexity analysis for computing estimates of ρ(d) for a finite-dimensional convex feasibility problem P(d) in standard primal form: find x that satisfies Ax = b, x ∈ C X , where d = (A, b) is the data for the problem P(d). Under one choice of norms for the m- and n-dimensional spaces, the problem of estimating ρ(d) is hard (co-NP complete even when C X = ℜ n + ). However, when the norms are suitably chosen, the problem becomes much easier: We can estimate ρ(d) to within a constant factor of its true value 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 first algorithm is an interior-point algorithm, and the second algorithm is a variant of the ellipsoid algorithm. The main conclusion of this work is that when the norms are suitably chosen, computing an estimate of the condition measures of P(d) is essentially not much harder than computing a solution of P(d) itself.