A conic linear system is a system of the form (FPd) Ax = b, x ∈ CX, where A : X → Y is a linear operator between n- and m-dimensional linear spaces X and Y, b ∈ Y, and CX ⊂ X is 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 C(d) of the data instance d as the scale-invariant reciprocal of ρ(d): C(d) =▵∥d∥/ρ(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(&ctilde;C(d)2ln(C(d))) where the constant &ctilde; 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 CX. The algorithm is ‘elementary’ in the sense that it performs only a few relatively simple computations at each iteration. The solution &xcrcmflx; of the system (FPd) generated by the algorithm has the property of being ‘reliable’ in the sense that the distance from ◯ to the boundary of the cone CX, dist(◯, ∂CX), and the size of the solution, ∥◯∥, satisfy the following inequalities: ∥◯∥ ≤ c1C(d), dist(◯, ∂CX) ≥ c2 1/C(d), and ∥◯∥/dist(◯, ∂CX) ≤ c3C(d), where c1, c2, c3 are constants that depend only on properties of the cone CX and are independent of the data d (with analogous results for the alternative system when the system (FPd) is infeasible).
