On the complexity of computing estimates of condition measures of a conic linear system

On the complexity of computing estimates of condition measures of a conic linear system

0.00 Avg rating0 Votes
Article ID: iaor20072078
Country: United States
Volume: 28
Issue: 4
Start Page Number: 625
End Page Number: 648
Publication Date: Nov 2003
Journal: Mathematics of Operations Research
Authors: ,
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 ∈ CX, where d = (A,b) are 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 CX=ℜ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.

Reviews

Required fields are marked *. Your email address will not be published.