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
Contact: [email protected]
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)