An Efficient Rescaled Perceptron Algorithm for Conic Systems

References

• Belloni A., Freund R. M. On the second-order feasibility cone: Primal-dual representation and efficient projection. SIAM J. Optim. (2008) 19(3):1073–1092Crossref, Google Scholar
• Berman A.Cones, Matrices, and Mathematical Programming (1973) (Springer-Verlag, New York) Crossref, Google Scholar
• Bertsimas D., Vempala S. Solving convex programs by random walks. J. ACM (2004) 51(4):540–556Crossref, Google Scholar
• Blum A., Frieze A., Kannan R., Vempala S. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica (1998) 22(1):35–52Crossref, Google Scholar
• Dunagan J., Vempala S. A simple polynomial-time rescaling algorithm for solving linear programs. Math. Programming (2008) 114(1):101–114Crossref, 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. (1999) 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 (1999) 86(2):225–260Crossref, Google Scholar
• Fu M., Luo Z.-Q., Ye Y. Approximation algorithms for quadratic programming. J. Combin. Optim. (1998) 2(1):29–50Crossref, Google Scholar
• Gradshtein I. S., Ryzhik I. M.Table of Integrals, Series, and Product (2007) (Academic Press, New York) Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1994) 2nd ed.(Springer-Verlag, Berlin) Google Scholar
• Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica (1984) 4(4):373–395Crossref, Google Scholar
• Khachiyan L. G. A polynomial algorithm in linear programming. Soviet Math. Dokl. (1979) 20(1):191–194Google Scholar
• Motwani R., Raghanav P.Randomized Algorithms (1995) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Nesterov Y., Nemirovskii A.Interior-Point Polynomial Algorithms in Convex Programming (1993) (SIAM, Philadelphia) Google Scholar
• Pataki G. On the closedness of the linear image of a closed convex cone. (1992) . Technical Report TR-02-3, Department of Operations Research, University of North Carolina, Chapel HillGoogle Scholar
• Renegar J. On the worst-case arithmetic complexity of approximating zeros of polynomials. J. Complexity (1987) 3(2):90–113Crossref, Google Scholar
• Renegar J. Some perturbation theory for linear programming. Math. Programming (1994) 65(1):73–91Crossref, Google Scholar
• Renegar J. Linear programming, complexity theory, and elementary functional analysis. Math. Programming (1995) 70(3):279–351Crossref, Google Scholar
• Rockafellar R. T.Convex Analysis (1970) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Rosenblatt F.Principles of Neurodynamics (1962) (Spartan Books, Washington, DC) Google Scholar
• Vavasis S. A., Zippel R. Proving polynomial time for sphere-constrained quadratic programming. (1990) . Technical report, Department of Computer Science, Cornell University, Ithaca, NYGoogle Scholar
• Wolkowicz H., Saigal R., Vandenberghe L.Handbook of Semidefinite Programming (2000) (Kluwer Academic Publishers, Dordrecht, The Netherlands) Crossref, Google Scholar
• Ye Y. On affine scaling algorithms for nonconvex quadratic programming. Math. Programming (1992) 56(3):285–300Crossref, Google Scholar