Accuracy Certificates for Computational Problems with Convex Structure

References

• Auslender A. Resolution numerique d'inegalites variationnelles. RAIRO—Oper. Res. (1973) 7:67–72Google Scholar
• Ben-Tal A., Nemirovski A.Lectures on Modern Convex Optimization (2001) (SIAM, Philadelphia) Crossref, Google Scholar
• Ben-Tal A., Nemirovski A. Non-Euclidean restricted memory level method for large-scale convex optimization. Math. Programming (2005) 102:407–456Crossref, Google Scholar
• Boyd S., Vandenberghe L.Convex Optimization (2004) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Bulatov V. P., Shepot'ko L. O. Method of centers of orthogonal simplexes for solving convex programming problems (in Russian). Methods of Optimization and Their Application (1982) (Nauka, Novosibirsk) Google Scholar
• Burrell B. P., Todd M. J. Ellipsoid method generates dual variables. Math. Oper. Res. (1985) 10:688–700Link, Google Scholar
• Facchinei F., Pang J.-S.Finite-Dimensional Variational Inequalities and Complementarity Problems (2003) (Springer-Verlag, New York) Google Scholar
• Gabelev D. Polynomial time cutting plane algorithms associated with symmetric cones. (2003) . M.Sc. thesis in OR and Systems Analysis, Faculty of Industrial Engineering and Management, Technion—Israel Institute of Technology, Technion City, Haifa, Israel, http://www2.isye.gatech.edu/∼nemirovs/Dima.pdfGoogle Scholar
• Grötschel M., Lovasz L., Schrijver A.The Ellipsoid Method and Combinatorial Optimization (1986) (Springer-Verlag, New York) Google Scholar
• Harker P. T., Pang J.-S. Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Math. Programming (1990) 48:161–220Crossref, Google Scholar
• John F.Extremum Problems with Inequalities as Subsidiary Conditions (1948) (Interscience Publishers, Inc., New York) 187–204(Studies and essays presented to R. Courant on his 60th birthday, January 8)Google Scholar
• Khachiyan L. G. A polynomial algorithm in linear programming. Soviet Math. Doklady (1979) 20:191–194Google Scholar
• Lemarechal C., Nemirovski A., Nesterov Yu. New variants of bundle methods. Math. Programming (1995) 69:111–148Crossref, Google Scholar
• Levin A. Yu. On an algorithm for the minimization of convex functions (in Russian). Doklady Akad. Nauk SSSR (1965) 160:1244–1247(English translation: Soviet Math. Doklady 6 286–290.)Google Scholar
• Minty G. J. Monotone non-linear operators in Hilbert space. Duke Math. J. (1962) 29:341–346Crossref, Google Scholar
• Nemirovski A., Renegar J., Shub M., Smale S. Polynomial time methods in convex programming. The Mathematics of Numerical Analysis, AMS-SIAM Summer Seminar on Mathematics in Applied Mathematics (1996) 32(AMS, Providence, RI) 543–589Lectures in Applied MathematicsGoogle Scholar
• Nemirovski A. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. (2004) 15:229–251Crossref, Google Scholar
• Nemirovski A., Yudin D.Problem Complexity and Method Efficiency in Optimization (1979) (Nauka Publishers, Moscow (in Russian)) . (English translation: John Wiley & Sons, 1983.)Google Scholar
• Nemirovskii A. Efficient iterative algorithms for variational inequalities with monotone operators (in Russian). Ekonomika i Matematicheskie Metody (1981) 17:344–359Google Scholar
• Nesterov Y. U. Smooth minimization of non-smooth functions. Math. Programming (2005) 103:127–152Crossref, Google Scholar
• Nesterov Y. U., Nemirovskii A.Interior-Point Polynomial Algorithms in Convex Programming (1994) (SIAM, Philadelphia) Crossref, Google Scholar
• Newman D. J. Location of maximum on unimodal surfaces. J. Assoc. Comput. Machinery (1965) 12:11–23Crossref, Google Scholar
• Nikaido H., Isoda K. Note on noncooperative convex games. Pacific J. Math. (1955) 5:807–815Crossref, Google Scholar
• Shor N. Z. Cutting plane method with space dilation for the solution of convex programming problems (in Russian). Kibernetika (1977) 1:94–95Google Scholar
• Tarasov S. P., Khachiyan L. G., Erlikh I. I. The method of inscribed ellipsoids. Soviet Math. Doklady (1988) 37:226–230Google Scholar
• Yamnitsky B., Levin L. An old linear programming algorithm runs in polynomoial time. Proc. 23rd Annual Sympos. Foundations Comput. Sci. (1982) (IEEE, New York) 327–328Google Scholar
• Yudin D., Nemirovskii A. Informational complexity and effective methods of solution for convex extremal problems (in Russian). Ekonomika i Matematicheskie Metody (1976) 12:357–369(English translation: Matekon: Transl. Russian East European Math. Economics 13 (1977), 25–45.)Google Scholar