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

Local quadratic convergence of polynomial-time interior-point methods for conic optimization problems

Author

Listed:
  • NESTEROV, Yu.

    () (Université catholique de Louvain, CORE, B-1348 Louvain-la-Neuve, Belgium)

  • TUNCEL, Levent

    () (Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Canada)

Abstract

In this paper, we establish a local quadratic convergence of polynomial-time interior-point methods for general conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier functions. We propose new path-following predictor-corrector schemes which work only in the dual space. They are based on an easily computable gradient proximity measure, which ensures an automatic transformation of the global linear rate of convergence to the local quadratic one under some mild assumptions. Our step-size procedure for the predictor step is related to the maximum step size (the one that takes us to the boundary). It appears that in order to obtain local superlinear convergence, we need to tighten the neighborhood of the central path proportionally to the current duality gap

Suggested Citation

  • NESTEROV, Yu. & TUNCEL, Levent, 2009. "Local quadratic convergence of polynomial-time interior-point methods for conic optimization problems," CORE Discussion Papers 2009072, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
  • Handle: RePEc:cor:louvco:2009072
    as

    Download full text from publisher

    File URL: http://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2009_72web.pdf
    Download Restriction: no

    References listed on IDEAS

    as
    1. Henrik Jacobsen Kleven & Claus Thustrup Kreiner & Emmanuel Saez, 2009. "The Optimal Income Taxation of Couples," Econometrica, Econometric Society, vol. 77(2), pages 537-560, March.
    2. Richard Blundell & Martin Browning & Costas Meghir, 1994. "Consumer Demand and the Life-Cycle Allocation of Household Expenditures," Review of Economic Studies, Oxford University Press, vol. 61(1), pages 57-80.
    3. Oswald, Andrew J. & Powdthavee, Nattavudh, 2008. "Does happiness adapt? A longitudinal study of disability with implications for economists and judges," Journal of Public Economics, Elsevier, vol. 92(5-6), pages 1061-1077, June.
    4. Claude d’Aspremont & Rodolphe Dos Santos Ferreira, 2009. "Household behavior and individual autonomy," Working Papers of BETA 2009-17, Bureau d'Economie Théorique et Appliquée, UDS, Strasbourg.
    5. Nils Braakmann, 2009. "Other-Regarding Preferences, Spousal Disability and Happiness: Evidence from German Couples," SOEPpapers on Multidisciplinary Panel Data Research 194, DIW Berlin, The German Socio-Economic Panel (SOEP).
    6. Patricia Apps & Ray Rees, 2007. "The Taxation of Couples," Discussion Papers 07/21, Department of Economics, University of York.
    7. Helmuth Cremer & Jean-Marie Lozachmeur & Pierre Pestieau, 2012. "Income taxation of couples and the tax unit choice," Journal of Population Economics, Springer;European Society for Population Economics, vol. 25(2), pages 763-778, January.
    8. Boskin, Michael J. & Sheshinski, Eytan, 1983. "Optimal tax treatment of the family: Married couples," Journal of Public Economics, Elsevier, pages 281-297.
    9. LEROUX, Marie-Louise & PESTIEAU, Pierre & PONTHIÈRE, Grégory, 2008. "Should we subsidize longevity?," CORE Discussion Papers 2008058, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. Ada Ferrer-i-Carbonell & Bernard M.S. van Praag, 2002. "The subjective costs of health losses due to chronic diseases. An alternative model for monetary appraisal," Health Economics, John Wiley & Sons, Ltd., vol. 11(8), pages 709-722.
    11. Bommier, Antoine & Leroux, Marie-Louise & Lozachmeur, Jean-Marie, 2011. "On the public economics of annuities with differential mortality," Journal of Public Economics, Elsevier, pages 612-623.
    12. LEROUX, Marie-Louise & PONTHIERE, Grégory, 2008. "Optimal tax policy and expected longevity: a mean and variance approach," CORE Discussion Papers 2008039, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Patricia F. Apps & Ray Rees, 1999. "Individual versus Joint Taxation in Models with Household Production," Journal of Political Economy, University of Chicago Press, vol. 107(2), pages 393-403, April.
    14. Duée, Michel & Rebillard, Cyril & Pennec, Sophie, 2005. "Les personnes dépendantes en France : Evolution et prise en charge
      [Old-age disability in France: Long-term evolution, private caregiving and public expenditure]
      ," MPRA Paper 69877, University Library of Munich, Germany.
    15. Marie-Louise Leroux & Gregory Ponthiere, 2009. "Optimal tax policy and expected longevity: a mean and variance utility approach," International Tax and Public Finance, Springer;International Institute of Public Finance, pages 514-537.
    16. Apps, Patricia F. & Rees, Ray, 1988. "Taxation and the household," Journal of Public Economics, Elsevier, vol. 35(3), pages 355-369, April.
    17. Rees, Ray, 1988. "Taxation and the Household," Munich Reprints in Economics 3411, University of Munich, Department of Economics.
    18. Alain Jousten & Barbara Lipszyc & Maurice Marchand & Pierre Pestieau, 2005. "Long-term Care Insurance and Optimal Taxation for Altruistic Children," FinanzArchiv: Public Finance Analysis, Mohr Siebeck, Tübingen, vol. 61(1), pages 1-1, March.
    19. Pierre Pestieau & Motohiro Sato, 2008. "Long-Term Care: the State, the Market and the Family," Economica, London School of Economics and Political Science, vol. 75(299), pages 435-454, August.
    20. Gregory Ponthiere, 2007. "Measuring longevity achievements under welfare interdependencies: a case for joint life expectancy indicators," Social Indicators Research: An International and Interdisciplinary Journal for Quality-of-Life Measurement, Springer, vol. 84(2), pages 203-230, November.
    21. repec:pse:psecon:2008-46 is not listed on IDEAS
    Full references (including those not matched with items on IDEAS)

    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:2009072. See general information about how to correct material in RePEc.

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

    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.

    We have no references for this item. You can help adding them by using 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.