Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system

A conic linear system is a system of the form¶¶(FP d )Ax = b ¶ x ∈ C X ,¶¶where A:X ? Y is a linear operator between n - and m -dimensional linear spaces X and Y , b ∈ Y , and C X ⊂X is a closed convex cone. The data for the system is d =( A,b ). This system is “well-posed” to the extent that (small) changes in the data d =( A,b ) do not alter the status of the system (the system remains feasible or not). Renegar defined the “distance to ill-posedness,”ρ( d ), to be the smallest change in the data Δ d =(Δ A ,Δ b ) needed to create a data instance d +Δ d that is “ill-posed,” i.e., that lies in the intersection of the closures of the sets of feasible and infeasible instances d ′ =( A ′ , b ′ ) of (FP (·) ). Renegar also defined the condition number ?( d ) of the data instance d as the scale-invariant reciprocal of ρ( d ) : ?( d )= .¶In this paper we develop an elementary algorithm that computes a solution of (FP d ) when it is feasible, or demonstrates that (FP d ) has no solution by computing a solution of the alternative system. The algorithm is based on a generalization of von Neumann’s algorithm for solving linear inequalities. The number of iterations of the algorithm is essentially bounded by¶¶ O ( ?( d ) 2 ln(?( d )))¶¶where the constant depends only on the properties of the cone C X and is independent of data d . Each iteration of the algorithm performs a small number of matrix-vector and vector-vector multiplications (that take full advantage of the sparsity of the original data) plus a small number of other operations involving the cone C X . The algorithm is “elementary” in the sense that it performs only a few relatively simple computations at each iteration.¶The solution of the system (FP d ) generated by the algorithm has the property of being “reliable” in the sense that the distance from to the boundary of the cone C X , dist( ,∂ C X ), and the size of the solution, ∥ ∥, satisfy the following inequalities:¶¶∥ ∥≤ c 1 ?( d ),dist( ,∂ C X )≥ c 2 , and ≤ c 3 ?( d ),¶¶where c 1 , c 2 , c 3 are constants that depend only on properties of the cone C X and are independent of the data d (with analogous results for the alternative system when the system (FP d ) is infeasible).Peer Reviewedhttp://deepblue.lib.umich.edu/bitstream/2027.42/42344/1/10107-88-3-451_00880451.pd