##
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.