Some characterizations and properties of the "distance to ill-posedness" and the condition measure of a conic linear system
A conic linear system is a system of the form P(d) : find x that solves b - Ax is an element of C-Y, x is an element of C-X, where CX and Cy are closed convex cones, and the data for the system is d = (A, b). This system is "well-posed" to the extent that (small) changes in the data (A, b) do not alter the status of the system (the system remains solvable or not). Renegar defined the "distance to ill-posedness", rho(d), to be the smallest change in the data Delta d = (Delta A, Delta b) for which the system P(d + Delta d) is "ill-posed", i.e., d + Delta d is hi the intersection of the closure of feasible and infeasible instances d' = (A', b') of P(.). Renegar also defined the "condition measure" of the data instance d as C(d) := parallel to d parallel to/rho(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear equations. This study presents two categories of results related to rho(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of rho(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal values provides an approximation of rho(d) to within certain constants, depending on whether P(d) is feasible or not, and where the constants depend on properties of the cones and the norms used. The second category of results involves the existence of certain inscribed and intersecting balls involving the feasible region of P(d) or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that the feasible region of P(d) (or its alternative system when P(d) is not feasible) will contain a ball of radius r that is itself no more than a distance R from me origin, where the ratio R/r satisfies R/r less than or equal to c(1)C(d), and such that r greater than or equal to c(2)/C9(d) and R less than or equal to c(3)C(d), where c(1),c(2), c(3) are constants that depend only on properties of the cones and the norms used. Therefore the condition measure C(d) is a relevant tool in proving the existence of an inscribed ball in the feasible region of P(d) that is not too far from the origin and whose radius is not too small.
conditioning complexity of linear programming infinite programming interior point methods error analysis