Condition Number Complexity of an Elementary Algorithm for Computing a Reliable Solution of a Conic Linear System

Marina Epelman and Robert M. Freund

A conic linear system is a system of the form FP_d: Ax=b, x \in C, where C is a closed convex cone, and the data for the system is d=(A,b). 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 bounded by O(c C(d)^2 \ln(C(d))). Here c is a constant that depends only on the properties of the cone C and is independent of data d, and C(d) is the condition number of FP_d originally developed by Renegar, which essentially is a scale-invariant reciprocal of the smalletst data perturbation needed to change the feasibility status of FP_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. The algorithm is ``elementary'' in the sense that it performs only a few relatively simple mathematical operations at each iteration. The algorithm will compute a solution \hat x of FP_d that is ``reliable'' in the sense that the distance from \hat x to the boundary of the cone C is not exessively small, the norm of \hat x is not excessively large, and the ratio of the above quantities is not exsessively large.

Massachusetts Institute of Technology, December 1998