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

Convergent subgradient methods for nonsmooth convex minimization

Author

Listed:
  • NESTEROV, Yu.

    (Université catholique de Louvain, CORE, Belgium)

  • SHIKHMAN, Vladimir

    (Université catholique de Louvain, CORE, Belgium)

Abstract

In this paper, we develop new subgradient methods for solving nonsmooth convex optimization problems. These methods are the first ones, for which the whole sequence of test points is endowed with the worst-case performance guarantees. The new methods are derived from a relaxed estimating sequences condition, which allows reconstruction of the approximate primal-dual optimal solutions. Our methods are applicable as efficient real-time stabilization tools for potential systems with infinite horizon. As an example, we consider a model of privacy-respecting taxation, where the center has no information on the utility functions of the agents. Nevertheless, we show that by a proper taxation policy, the agents can be forced to apply in average the socially optimal strategies. Preliminary numerical experiments confirm a high efficiency of the new methods.

Suggested Citation

  • NESTEROV, Yu. & SHIKHMAN, Vladimir, 2014. "Convergent subgradient methods for nonsmooth convex minimization," LIDAM Discussion Papers CORE 2014005, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2014005
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Hindriks, Jean & Myles, Gareth D., 2013. "Intermediate Public Economics," MIT Press Books, The MIT Press, edition 2, volume 1, number 0262018691, April.
    2. Philippe De Donder & Pierre Pestieau, 2015. "Lobbying, Family Concerns, and the Lack of Political Support for Estate Taxation," Economics and Politics, Wiley Blackwell, vol. 27(3), pages 389-403, November.
    3. Fujita,Masahisa & Thisse,Jacques-François, 2013. "Economics of Agglomeration," Cambridge Books, Cambridge University Press, number 9780521171960, September.
    4. RUSSO, Federica & MOUCHART, Michel & WUNSCH, Guillaume, 2013. "Confounding and control in a multivariate system. An issue in causal attribution," LIDAM Discussion Papers CORE 2013068, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Nigar Hashimzade & Jean Hindriks & Gareth D. Myles, 2006. "Solutions Manual to Accompany Intermediate Public Economics," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262582694, April.
    6. Russo, F. & Mouchart, M. & Wunsch, G., 2013. "Confounding and Control in a Multivariate System An issue in causal attribution," LIDAM Discussion Papers ISBA 2013043, Université catholique de Louvain, Institute of Statistics, Biostatistics and Actuarial Sciences (ISBA).
    7. NESTEROV, Yurii, 2013. "Gradient methods for minimizing composite functions," LIDAM Reprints CORE 2510, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. DI SUMMA, Marco, 2013. "The convex hull of the all-different system with the inclusion property: a simple proof," LIDAM Discussion Papers CORE 2013069, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. PAPAVASILIOU, Anthony & HE, Yi & SVOBODA, Alva, 2013. "Self-commitment of combined cycle units under electricity price uncertainty," LIDAM Discussion Papers CORE 2013051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    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. KORNEK, Urik & LESSMANN, Kai & TULKENS, Henry, 2014. "Transferable and non transferable utility implementations of coalitional stability in integrated assessment models," LIDAM Discussion Papers CORE 2014035, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. DASH, Sanjeeb & GÜNLÜK, Oktay & WOLSEY, Laurence A., 2014. "The continuous knapsack set," LIDAM Discussion Papers CORE 2014007, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. YATSENKO, Yuri & HRITONENKO, Natali & BRECHET, Thierry, 2014. "Modeling of environmental adaptation versus pollution mitigation," LIDAM Discussion Papers CORE 2014006, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. GRIGIS DE STEFANO, Federico, 2014. "Strategic stability of equilibria: the missing paragraph," LIDAM Discussion Papers CORE 2014015, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Cremer Helmuth & Pestieau Pierre, 2018. "Means-Tested Long-Term Care and Family Transfers," German Economic Review, De Gruyter, vol. 19(3), pages 351-364, August.
    6. Bauwens, Luc & Grigoryeva, Lyudmila & Ortega, Juan-Pablo, 2016. "Estimation and empirical performance of non-scalar dynamic conditional correlation models," Computational Statistics & Data Analysis, Elsevier, vol. 100(C), pages 17-36.
    7. François Maniquet & Massimo Morelli, 2015. "Approval quorums dominate participation quorums," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(1), pages 1-27, June.
    8. Hafner, Christian M. & Preminger, Arie, 2015. "A note on the Tobit model in the presence of a duration variable," Economics Letters, Elsevier, vol. 126(C), pages 47-50.
    9. Paul Belleflamme & Paul Bloch, 2013. "Dynamic Protection of Innovations through Patents and Trade Secrets," CESifo Working Paper Series 4486, CESifo.
    10. Jean J. Gabszewicz & Skerdilajda Zanaj, 2015. "(Un)stable vertical collusive agreements," Canadian Journal of Economics/Revue canadienne d'économique, John Wiley & Sons, vol. 48(3), pages 924-939, August.
    11. LAMAS, ALEJANDRO & CHEVALIER, Philippe, 2013. "Jumping the hurdles for collaboration: fairness in operations pooling in the absence of transfer payments," LIDAM Discussion Papers CORE 2013073, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. Cristina Pardo-Garcia & Jose Sempere-Monerris, 2015. "Equilibrium mergers in a composite good industry with efficiencies," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 6(1), pages 101-127, March.
    13. DI SUMMA, Marco, 2013. "The convex hull of the all-different system with the inclusion property: a simple proof," LIDAM Discussion Papers CORE 2013069, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. VARDAR, N. Baris, 2013. "Imperfect resource substitution and optimal transition to clean technologies," LIDAM Discussion Papers CORE 2013072, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. WOLSEY, Laurence & YAMAN , Hand & ,, 2013. "Continuous knapsack sets with divisible capacities," LIDAM Discussion Papers CORE 2013063, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Ana Mauleon & Elena Molis & Vincent Vannetelbosch & Wouter Vergote, 2014. "Dominance invariant one-to-one matching problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 925-943, November.
    17. TELHA, Claudio & VAN VYVE, Matthieu, 2014. "Efficient approximation algorithms for the economic lot-sizing in continuous time," LIDAM Discussion Papers CORE 2014016, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    18. RUSSO, Federica & MOUCHART, Michel & WUNSCH, Guillaume, 2013. "Confounding and control in a multivariate system. An issue in causal attribution," LIDAM Discussion Papers CORE 2013068, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. MADANI, Mehdi & VAN VYVE, Mathieu, 2013. "A new formulation of the European day-ahead electricity market problem and its algorithmic consequences," LIDAM Discussion Papers CORE 2013074, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Britz, Volker & Herings, P. Jean-Jacques & Predtetchinski, Arkadi, 2014. "On the convergence to the Nash bargaining solution for action-dependent bargaining protocols," Games and Economic Behavior, Elsevier, vol. 86(C), pages 178-183.

    More about this item

    Keywords

    convex optimization; nonsmooth optimization; subgradient methods; rate of convergence; primal-dual methods; privacy-respecting tax policy;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:2014005. 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.