IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2013026.html
   My bibliography  Save this paper

Universal gradient methods for convex optimization problems

Author

Listed:
  • NESTEROV, Yurii

    (Université catholique de Louvain, CORE, Belgium)

Abstract

In this paper, we present new methods for black-box convex minimization. They do not need to know in advance the actual level of smoothness of the objective function. The only essential input parameter is the required accuracy of the solution. At the same time, for each particular problem class they automatically ensure the best possible rate of convergence. We confirm our theoretical results by encouraging numerical experiments, which demonstrate that the fast rate of convergence, typical for the smooth optimization problems, sometimes can be achieved even on nonsmooth problem instances.

Suggested Citation

  • NESTEROV, Yurii, 2013. "Universal gradient methods for convex optimization problems," LIDAM Discussion Papers CORE 2013026, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2013026
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2013.html
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Fleurbaey,Marc & Maniquet,François, 2011. "A Theory of Fairness and Social Welfare," Cambridge Books, Cambridge University Press, number 9780521715348, October.
    2. Hafner, Christian M. & Linton, Oliver, 2017. "An Almost Closed Form Estimator For The Egarch Model," Econometric Theory, Cambridge University Press, vol. 33(4), pages 1013-1038, August.
    3. Gautier Axel & Poudou Jean-Christophe, 2014. "Reforming the Postal Universal Service," Review of Network Economics, De Gruyter, vol. 13(4), pages 453-477, December.
    4. BAUWENS, Luc & otranto, EDOARDO, 2013. "Modeling the dependence of conditional correlations on volatility," LIDAM Discussion Papers CORE 2013014, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Duranton, Gilles & Martin, Philippe & Mayer, Thierry & Mayneris, Florian, 2010. "The Economics of Clusters: Lessons from the French Experience," OUP Catalogue, Oxford University Press, number 9780199592203.
    6. DEVOLDER, Olivier & GLINEUR, François & NESTEROV, Yurii, 2011. "First-order methods of smooth convex optimization with inexact oracle," LIDAM Discussion Papers CORE 2011002, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. GOERTZ, Johanna & MANIQUET, François, 2013. "Large elections with multiple alternatives: a Condorcet Jury Theorem and inefficient equilibria," LIDAM Discussion Papers CORE 2013023, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Bocart, Fabian Y.R.P. & Hafner, Christian M., 2015. "Fair Revaluation of Wine as an Investment," Journal of Wine Economics, Cambridge University Press, vol. 10(2), pages 190-203, November.
    9. Hafner C. & Linton, O., 2013. "An Almost Closed Form Estimator for the EGARCH," LIDAM Discussion Papers ISBA 2013010, Université catholique de Louvain, Institute of Statistics, Biostatistics and Actuarial Sciences (ISBA).
    10. Gaertner,Wulf & Schokkaert,Erik, 2011. "Empirical Social Choice," Cambridge Books, Cambridge University Press, number 9781107013940, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. CORNUEJOLS, Gérard & WOLSEY, Laurence & YILDIZ, Sercan, 2013. "Sufficiency of cut-generating functions," LIDAM Discussion Papers CORE 2013027, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. MLINAR, Tanja B. & CHEVALIER, Philippe, 2013. "Pooling in manufacturing: do opposites attract?," LIDAM Discussion Papers CORE 2013040, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. CORNUEJOLS, Gérard & WOLSEY, Laurence & YILDIZ, Sercan, 2013. "Sufficiency of cut-generating functions," LIDAM Discussion Papers CORE 2013027, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Bocart, Fabian Y.R.P. & Hafner, Christian M., 2015. "Fair Revaluation of Wine as an Investment," Journal of Wine Economics, Cambridge University Press, vol. 10(2), pages 190-203, November.
    3. MLINAR, Tanja B. & CHEVALIER, Philippe, 2013. "Pooling in manufacturing: do opposites attract?," LIDAM Discussion Papers CORE 2013040, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. GOERTZ, Johanna & MANIQUET, François, 2013. "Large elections with multiple alternatives: a Condorcet Jury Theorem and inefficient equilibria," LIDAM Discussion Papers CORE 2013023, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. DEVOLDER, Olivier & GLINEUR, François & NESTEROV, Yurii, 2013. "First-order methods with inexact oracle: the strongly convex case," LIDAM Discussion Papers CORE 2013016, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Chiara Canta & Marie-Louise Leroux, 2016. "Public and Private Hospitals, Congestion, and Redistribution," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 18(1), pages 42-66, February.
    7. Hafner, Christian M. & Linton, Oliver, 2017. "An Almost Closed Form Estimator For The Egarch Model," Econometric Theory, Cambridge University Press, vol. 33(4), pages 1013-1038, August.
    8. DEVOLDER, Olivier & GLINEUR, François & NESTEROV, Yurii, 2013. "Intermediate gradient methods for smooth convex problems with inexact oracle," LIDAM Discussion Papers CORE 2013017, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Caulier, Jean-François & Mauleon, Ana & Vannetelbosch, Vincent, 2015. "Allocation rules for coalitional network games," Mathematical Social Sciences, Elsevier, vol. 78(C), pages 80-88.
    10. Thomas Baudin & David de la Croix & Paula E. Gobbi, 2015. "Fertility and Childlessness in the United States," American Economic Review, American Economic Association, vol. 105(6), pages 1852-1882, June.
    11. Kirchsteiger, Georg & Mantovani, Marco & Mauleon, Ana & Vannetelbosch, Vincent, 2016. "Limited farsightedness in network formation," Journal of Economic Behavior & Organization, Elsevier, vol. 128(C), pages 97-120.
    12. Dirk Van de gaer & Joost Vandenbossche & José Luis Figueroa, 2014. "Children's Health Opportunities and Project Evaluation: Mexico's Oportunidades Program," The World Bank Economic Review, World Bank, vol. 28(2), pages 282-310.
    13. Mendolicchio Concetta & Paolini Dimitri & Pietra Tito, 2012. "Asymmetric Information And Overeducation," The B.E. Journal of Economic Analysis & Policy, De Gruyter, vol. 12(1), pages 1-29, October.
    14. Claude, DASPREMONT & Rodolphe, DOS SANTOS FERREIRA & Jacques, THEPOT, 2007. "Hawks and doves in segmented markets : a formal approach to competitive aggressiveness," Discussion Papers (ECON - Département des Sciences Economiques) 2007039, Université catholique de Louvain, Département des Sciences Economiques.
    15. Nora, Vladyslav & Uno, Hiroshi, 2014. "Saddle functions and robust sets of equilibria," Journal of Economic Theory, Elsevier, vol. 150(C), pages 866-877.
    16. Dehez, Pierre & Ferey, Samuel, 2013. "How to share joint liability: A cooperative game approach," Mathematical Social Sciences, Elsevier, vol. 66(1), pages 44-50.
    17. Sudipto Bhattacharya & Claude d’Aspremont & Sergei Guriev & Debapriya Sen & Yair Tauman, 2014. "Cooperation in R&D: Patenting, Licensing, and Contracting," International Series in Operations Research & Management Science, in: Kalyan Chatterjee & William Samuelson (ed.), Game Theory and Business Applications, edition 2, chapter 0, pages 265-286, Springer.
    18. Christophe Bravard & Sudipta Sarangi & ANA MAULEON & JOSE J. SEMPERE-MONERRIS & VINCENT VANNETELBOSCH, 2016. "Contractually Stable Alliances," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 18(2), pages 212-225, April.
    19. HOSSEINZADEH LOTFI, Farhad & HATAMI-MARBINI, Adel & AGRELL, Per & GHOLAMI, Kobra, 2013. "Centralized resource reduction and target setting under DEA control," LIDAM Discussion Papers CORE 2013005, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Thierry Bréchet & Carmen Camacho & Vladimir M. Veliov, 2012. "Adaptive Model-Predictive Climate Policies in a Multi-Country Setting," Documents de travail du Centre d'Economie de la Sorbonne 12029, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2013026. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.