Name
Title | ||
|---|---|---|
Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system |
Abstract | ||
|---|---|---|
. A conic linear system is a system of the form¶¶(FP
d
)Ax=b¶x∈C
X
,¶¶where A:X?Y is a linear operator between n- and m-dimensional linear spaces X and Y, b∈Y, and C
X
⊂X is a 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 ?(d) of the data instance d as the scale-invariant reciprocal of ρ(d) : ?(d)=.¶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 essentially bounded by¶¶O( ?(d)2ln(?(d)))¶¶where the constant depends only on the properties of the cone C
X
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 C
X
. The algorithm is “elementary” in the sense that it performs only a few relatively simple computations at each iteration.¶The
solution of the system (FP
d
) generated by the algorithm has the property of being “reliable” in the sense that the distance from to the boundary of the cone C
X
, dist(,∂C
X
), and the size of the solution, ∥∥, satisfy the following inequalities:¶¶∥∥≤c
1?(d),dist(,∂C
X
)≥c
2
, and ≤c
3?(d),¶¶where c
1, c
2, c
3 are constants that depend only on properties of the cone C
X
and are independent of the data d (with analogous results for the alternative system when the system (FP
d
) is infeasible). |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/s101070000136 | Math. Program. |
Keywords | Field | DocType |
Key words: complexity of convex programming – conditioning – error analysis,Mathematics Subject Classification (1991): 90C,90C05,90C60 | Discrete mathematics,Condition number,Mathematical optimization,Linear system,Algorithm,Linear map,Conic section,Linear inequality,Convex optimization,Mathematics,Convex cone,Bounded function | Journal |
Volume | Issue | ISSN |
88 | 3 | 0025-5610 |
Citations | PageRank | References |
23 | 1.81 | 20 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marina A. Epelman | 1 | 209 | 18.62 |
| Robert M. Freund | 2 | 1632 | 340.67 |
| Robert M. Freund | 3 | 1632 | 340.67 |