caa a22 4500 475769716 CHVBK 20180406123616.0 cr unu---uuuuu 170329e20000901xx s 000 0 eng 10.1007/s101070000136 doi (NATIONALLICENCE)springer-10.1007/s101070000136 Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system [Elektronische Daten] [Marina Epelman, Robert M. Freund] 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). Springer-Verlag Berlin Heidelberg, 2000 Key words: complexity of convex programming - conditioning - error analysis nationallicence Mathematics Subject Classification (1991): 90C, 90C05, 90C60 nationallicence Epelman Marina University of Michigan, Industrial and Operations Engineering, 1205 Beal Avenue, Ann Arbor, MI 48109-2117, USA, e-mail: mepelman@umich.edu, US aut Freund Robert M. M.I.T. Sloan School of Management, 50 Memorial Drive, Cambridge, MA 02142-1347, USA, e-mail: rfreund@mit.edu, US aut https://doi.org/10.1007/s101070000136 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101070000136 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Epelman Marina University of Michigan, Industrial and Operations Engineering, 1205 Beal Avenue, Ann Arbor, MI 48109-2117, USA, e-mail: mepelman@umich.edu, US aut NATIONALLICENCE 700 1- Freund Robert M. M.I.T. Sloan School of Management, 50 Memorial Drive, Cambridge, MA 02142-1347, USA, e-mail: rfreund@mit.edu, US aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer