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 [GRAPHICS] where A : X ---> Y is a linear operator between n- and m-dimensional linear spaces X and Y, b E Y, and C(X) subset of 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," rho(d), to be the smallest change in the data Delta d = (Delta A, Delta b) needed to create a data instance d + Delta 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 C(d) of the data instance d as the scale-invariant reciprocal of rho(d): C(d) double bond Delta parallel to d parallel to/rho(d). In this paper we develop an elementary algorithm that computes a solution of (FPd) when it is feasible, or demonstrates that (FPd) 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((c) over tilde C(d)(2)ln(C(d))) where the constant (c) over tilde depends only on the properties of the cone Cx 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 (x) over cap of the system (FPd) generated by the algorithm has the property of being "reliable" in the sense that the distance from (x) over cap to the boundary of the cone C(X), dist((x) over cap, partial derivative C(X)), and the size of the solution, parallel to (x) over cap parallel to, satisfy the following inequalities: parallel to<(x) over cap>parallel to less than or equal to c(I)C(d), dist((x) over cap, partial derivative C(X)) greater than or equal to c(2) 1/C(d), and parallel to (x) over cap parallel to/dist((x) over cap, partial derivative C(X)) less than or equal to c(3)C(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 (FPd) is infeasible).