Condition Number Complexity of an Elementary Algorithm for Resolving a Conic Linear System

Marina Epelman and Robert M. Freund

We develop an algorithm for resolving a conic linear system (FP$_d$), which is a system of the form $$\begin{array}{cl} \mbox{(FP$_d$):} & b-Ax\in C_Y\\ & x\in C_X,\\ \end{array}$$ where $C_{X}$ and $C_{Y}$ are closed convex cones, and the data for the system is $d=(A,b)$. The algorithm "resolves" the system in that it either finds an $\epsilon$-solution of (FP$_d$) for a pre-specified tolerance $\epsilon$, or demonstrates that (FP$_d$) has no solution by solving an alternative dual system. The algorithm is based on a generalization of von Neumann's algorithm for linear inequalities. The number of iterations of the algorithm is essentially bounded by $O\left({\cal C}(d)^2\ln({\cal C}(d))\ln\left(\frac{\|b\|}{\epsilon}\right)\right)$ when (FP$_d$) has a solution, and is bounded by $O\left({\cal C}(d)^2\right)$ when (FP$_d$) has no solution, and so depends only on two numbers, namely the feasibility tolerance $\epsilon$ and the condition number ${\cal C}(d)$ of the data $d=(A,b)$ (in addition to the norm of the vector $b$), and is independent of the dimensions of the problem. The quantity ${\cal C}(d)$ is the condition number of (FP$_d$), originally defined by Renegar as ${\cal C}(d)\ {\underline {\underline \Delta}}\|d\|/\rho(d)$, where $\rho(d)$ is smallest change in the data $\Delta d=(\Delta A, \Delta b)$ needed to create a data instance $d+\Delta d=(A+\Delta A, b+\Delta b)$ that is ill-posed, i.e., $\rho(d)$ is the "distance to ill-posedness". 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 cones $C_X$ and $C_Y$ that may be easy to compute or not, depending on the nature of the cones $C_X$ and $C_Y$ (and which are easy to compute when these cones are the nonnegative orthant $R^n_+$, the semi-definite cone $S^{k \times k}_+$, and/or the origin $\{0\}$). The algorithm is "elementary'' in the sense that it performs only a few relatively simple mathematical operations at each iterations.