IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2013026.html

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, January.
    2. Gautier Axel & Poudou Jean-Christophe, 2014. "Reforming the Postal Universal Service," Review of Network Economics, De Gruyter, vol. 13(4), pages 453-477, December.
    3. 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).
    4. 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.
    5. 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).
    6. 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).
    7. repec:hum:wpaper:sfb649dp2013-018 is not listed on IDEAS
    8. 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.
    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. 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.
    11. Gaertner,Wulf & Schokkaert,Erik, 2011. "Empirical Social Choice," Cambridge Books, Cambridge University Press, number 9781107013940, January.
    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. 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.
    7. 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).
    8. 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.
    9. 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.
    10. 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.
    11. 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).
    12. DEVOLDER, Olivier, 2011. "Stochastic first order methods in smooth convex optimization," LIDAM Discussion Papers CORE 2011070, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. NESTEROV, Yurii & NEMIROVSKI, Arkadi, 2012. "Finding the stationary states of Markov chains by iterative methods," LIDAM Discussion Papers CORE 2012058, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. DUFAYS, Arnaud, 2012. "Infinite-state Markov-switching for dynamic volatility and correlation models," LIDAM Discussion Papers CORE 2012043, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. CALO-BLANCO, Aitor, 2012. "The compensation problem with fresh starts," LIDAM Discussion Papers CORE 2012036, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Ana Mauleon & Vincent Vannetelbosch, 2013. "Relative Concerns and Delays in Bargaining with Private Information," Games, MDPI, vol. 4(3), pages 1-10, June.
    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. Jean-François Mertens & Anna Rubinchik, 2013. "Equilibria in an overlapping generations model with transfer policies and exogenous growth," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(3), pages 537-595, November.
    20. Pascal Mossay & Takatoshi Tabuchi, 2015. "Preferential Trade Agreements Harm Third Countries," Economic Journal, Royal Economic Society, vol. 125(589), pages 1964-1985, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.