Conditioning of Convex Programs from a Primal-Dual Perspective

References

• Epelman M., Freund R. 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
• Filipowski S. On the complexity of solving sparse symmetric linear programs specified with approximate data. SIAM J. Optim. (1999) 9:1010–1040Crossref, Google Scholar
• Freund R., Vera J. Some characterization and properties of the “distance to ill-posedness” and the condition measure of a conic linear system. Math. Programming (1999a) 86:225–260Crossref, Google Scholar
• Freund R. Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm. SIAM J. Optim. (1999b) 10:155–176Crossref, Google Scholar
• Lewis A. Ill-conditioned convex processes and linear inequalities. Math. Oper. Res. (1999) 4:829–834Link, Google Scholar
• Nunez M., Freund R. Condition measures and properties of the central trajectory of a linear program. Math. Programming (1998) 83:1–28Crossref, Google Scholar
• Nesterov Y., Nemirovskii A.Interior-Point Polynomial Algorithms in Convex Programming (1994) (SIAM, Philadelphia, PA) Crossref, Google Scholar
• Nesterov Y., Todd M. J. Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. (1997) 22:1–42Link, Google Scholar
• Nesterov Y. Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. (1998) 8:324–364Crossref, Google Scholar
• Peña J. Understanding the geometry on infeasible perturbations of a conic linear system. SIAM J. Optim. (2000) 10:534–550Crossref, 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–92Crossref, Google Scholar
• Renegar J. Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. (1995a) 5:506–524Crossref, Google Scholar
• Renegar J. Linear programming, complexity theory and elementary functional analysis. Math. Programming (1995b) 70:279–351Crossref, Google Scholar
• Renegar J. Condition numbers, the barrier method and the conjugate gradient method. SIAM J. Optim. (1996) 6(1996):879–912Crossref, Google Scholar
• Renegar J.A Mathematical View of Interior-Point Methods in Convex Optimization (2000) (SIAM, Philadelphia, PA) Google Scholar
• Stewart G., Sun J.Matrix Perturbation Theory (1990) (Academic Press Inc., San Diego, CA) Google Scholar
• Vera J. Ill-posedness and the complexity of deciding existence of solutions to linear programs. SIAM J. Optim. (1996) 6:549–569Crossref, Google Scholar
• Vera J. On the complexity of linear programming under finite precision arithmetic. Math. Programming (1998) 80:91–123Crossref, Google Scholar