Unifying Condition Numbers for Linear Programming

References

• Cheung D., Cucker F. A new condition number for linear programming. Math. Programming (2001) 91:163–174Crossref, Google Scholar
• Cheung D., Cucker F. Solving linear programs with finite precision: I. Condition numbers and random programs. Math. Programming (2002) . ForthcomingGoogle Scholar
• Cheung D., Cucker F. Solving linear programs with finite precision: II. Algorithms. (2003) . Working paperGoogle Scholar
• Cheung D., Cucker F., Ye Y., Ciarlet P., Cucker F. Linear programming and condition numbers under the real number computation model. Handbook of Numerical Analysis (2003) XI(North-Holland, Amsterdam, The Netherlands) Crossref, Google Scholar
• Cucker F., Peña J. A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine. SIAM J. Optim. (2002) 12:522–554Crossref, Google Scholar
• Demmel J. The componentwise distance to the nearest singular matrix. SIAM J. Matrix Anal. Appl. (1992) 13:10–19Crossref, Google Scholar
• Dontchev A., Lewis A., Rockafellar T. The radius of metric regularity. Trans. Amer. Math. Soc. (2003) 355:493–517Crossref, Google Scholar
• Doyle J. Analysis of feedback systems with structured uncertainty. IEE Proc. (1982) 129:242–250Crossref, Google Scholar
• Eckart C., Young G. The approximation of one matrix by another of lower rank. Psychometrika (1936) 1:211–218Crossref, Google Scholar
• 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:451–485Crossref, Google Scholar
• Epelman M., Freund R. M. A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems. SIAM J. Optim. (2002) 12:627–655Crossref, 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. (1999a) 10: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 (1999b) 86:225–260Crossref, Google Scholar
• Goldman A., Tucker A., Kuhn H., Tucker A. Theory of linear programming. Linear Inequalities and Related Systems, Vol. 38. Ann. Math. Stud. (1956) (Princeton University Press, Princeton, New Jersey) 53–97Google Scholar
• Higham N.Accuracy and Stability of Numerical Algorithms (1996) (SIAM, Philadelphia PA) Google Scholar
• Lewis A. Ill-conditioned convex processes and linear inequalities. Math. Oper. Res. (1999) 24:829–834Link, Google Scholar
• Lewis A. S. Ill-conditioned inclusions. Set-Valued Anal. (2001) 9:375–381Crossref, Google Scholar
• Nunez M., Freund R. M. Condition measures and properties of the central trajectory of a linear program. Math. Programming (1998) 83:1–28Crossref, Google Scholar
• Packard A., Doyle J. The complex structured singular value. Automatica (1993) 29:71–109Crossref, Google Scholar
• Packard A., Pandey P. Continuity properties of the real/complex structured singular value. IEEE Trans. Automatic Control (1993) 38:415–428Crossref, Google Scholar
• Peña J. Understanding the geometry of infeasible perturbations of a conic linear system. SIAM J. Optim. (2000) 10:534–550Crossref, Google Scholar
• Peña J. A characterization of the distance to infeasibility under block-structured perturbations. Linear Algebra Appl. (2003) 370:193–216Crossref, Google Scholar
• Peña J., Renegar J. Computing approximate solutions for conic systems of constraints. Math. Programming (2000) 87:351–383Crossref, Google Scholar
• Renegar J. Some perturbation theory for linear programming. Math. Programming (1994) 65:73–91Crossref, Google Scholar
• Renegar J. Linear programming, complexity theory and elementary functional analysis. Math. Programming (1995) 70:279–351Crossref, Google Scholar
• Renegar J. Condition numbers, the barrier method, and the conjugate-gradient method. SIAM J. Optim. (1996) 6:879–912Crossref, Google Scholar
• Rohn J. Systems of linear interval equations. Linear Algebra Appl. (1989) 126:39–78Crossref, Google Scholar
• Rump S. Ill-conditioned matrices are componentwise near to singularity. SIAM Rev. (1999) 41:102–112Crossref, Google Scholar
• Stewart G. W. On scaled projections and pseudoinverses. Linear Algebra Its Appl. (1989) 112:189–193Crossref, Google Scholar
• Todd M. J. A Dantzig-Wolfe-like variant of Karmarkar's interior-point linear programming algorithm. Oper. Res. (1990) 38:1006–1018Link, Google Scholar
• Vavasis S. A., Ye Y. Condition numbers for polyhedra with real number data. Oper. Res. Lett. (1995) 17:209–214Crossref, Google Scholar
• Vavasis S. A., Ye Y. A primal-dual interior point method whose running time depends only on the constraint matrix. Math. Programming (1996) 74:79–120Crossref, Google Scholar
• Vera J. R. On the complexity of linear programming under finite precision arithmetic. Math. Programming (1998) 80:91–123Crossref, Google Scholar
• Ye Y. Toward probabilistic analysis of interior-point algorithms for linear programming. Math. Oper. Res. (1994) 19:38–52Link, Google Scholar
• Zhou K., Doyle J., Glover K.Robust and Optimal Control (1996) (Prentice Hall, Upper Saddle River, NJ) Google Scholar