On the Complexity of Computing Estimates of Condition Measures of a Conic Linear System

References

• Epelman M., Freund R. M. Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system. Math. Programming (2000) 88(3):451–485Crossref, Google Scholar
• Filipowski S. On the complexity of solving sparse symmetric linear programs specified with approximate data. Math. Oper. Res. (1997) 22:769–792Link, Google Scholar
• Filipowski S. On the complexity of solving linear programs specified with approximate data and known to be feasible. SIAM J. Optim. (1999) 9:1010–1040Crossref, Google Scholar
• Freund R. M., Orlin J. B. On the complexity of four polyhedral set containment problems. Math. Programming (1985) 33:133–145Crossref, Google Scholar
• Freund R. M., Vera J. R. Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm. SIAM J. Optim. (2000a) 10(1):155–176Crossref, Google Scholar
• Freund R. M., Vera J. R. Some characterizations and properties of the “distance to ill-posedness” and the condition measure of a conic linear system. Math. Programming (2000b) 86:225–260Crossref, Google Scholar
• Grötschel M., Lovasz L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1988) (Springer-Verlag, Berlin, Germany) Crossref, Google Scholar
• Mangasarian O. Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. SIAM J. Control Optim. (1987) 25(3):41–87Crossref, Google Scholar
• Nesterov Y., Nemirovskii A.Interior-Point Polynomial Algorithms in Convex Programming (1994) (Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA) Crossref, Google Scholar
• Nunez M. A., Freund R. M. Condition measures and properties of the central trajectory of a linear program. Math. Programming (1998) 83(1):1–28Crossref, Google Scholar
• Peña J. Computing the distance to infeasibility: Theoretical and practical issues. (1997) . Technical report, Cornell University, Center for Applied Mathematics, Ithaca, NYGoogle Scholar
• Renegar J. Some perturbation theory for linear programming. Math. Programming (1994) 65(1):73–91Crossref, Google Scholar
• Renegar J. Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. (1995a) 5(3):506–524Crossref, Google Scholar
• Renegar J. Linear programming, complexity theory, and elementary functional analysis. Math. Programming (1995b) 70(3):279–351Crossref, Google Scholar
• Renegar J. Condition numbers, the barrier method, and the conjugate gradient method. SIAM J. Optim. (1996) 64(4):879–912Crossref, Google Scholar
• Vera J. R. Ill-posedness in mathematical programming and problem solving with approximate data. (1992) . Ph.D. thesis, Cornell University, Ithaca, NYGoogle Scholar
• Vera J. R. Ill-posedness and the complexity of deciding existence of solutions to linear programs with approximate data. SIAM J. Optim. (1996) 6(3):549–569Crossref, Google Scholar
• Vera J. R. On the complexity of linear programming under finite precision arithmetic. Math. Programming (1998) 80(1):91–123Crossref, Google Scholar
• Yudin D. B., Nemirovskii A. S. Informational complexity and efficient methods for solving complex extremal problems. Ekonomika i Matem. Metody (1976) 12:357–369Google Scholar