[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i4p1934-1958.html
   My bibliography  Save this article

An Accelerated Newton–Dinkelbach Method and Its Application to Two Variables per Inequality Systems

Author

Listed:
  • Daniel Dadush

    (Centrum Wiskunde & Informatica, Amsterdam 1098 XG, Netherlands)

  • Zhuan Khye Koh

    (Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, United Kingdom)

  • Bento Natura

    (Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, United Kingdom)

  • László A. Végh

    (Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, United Kingdom)

Abstract
We present an accelerated or “look-ahead” version of the Newton–Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceleration halves the Bregman divergence between the current iterate and the optimal solution within every two iterations. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain strongly polynomial algorithms in three applications domains. (i) For linear fractional combinatorial optimization, we show a convergence bound of O ( m log m ) iterations; the previous best bound was O ( m 2 log m ) by Wang, Yang, and Zhang from 2006. (ii) We obtain a strongly polynomial label-correcting algorithm for solving linear feasibility systems with two variables per inequality (2VPI). For a 2VPI system with n variables and m constraints, our algorithm runs in O ( mn ) iterations. Every iteration takes O ( mn ) time for general 2VPI systems and O ( m + n log n ) time for the special case of deterministic Markov decision processes (DMDPs). This extends and strengthens a previous result by Madani from 2002 that showed a weakly polynomial bound for a variant of the Newton–Dinkelbach method for solving DMDPs. (iii) We give a simplified variant of the parametric submodular function minimization result from 2017 by Goemans, Gupta, and Jaillet.

Suggested Citation

  • Daniel Dadush & Zhuan Khye Koh & Bento Natura & László A. Végh, 2023. "An Accelerated Newton–Dinkelbach Method and Its Application to Two Variables per Inequality Systems," Mathematics of Operations Research, INFORMS, vol. 48(4), pages 1934-1958, November.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:4:p:1934-1958
    DOI: 10.1287/moor.2022.1326
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1326
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1326?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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:inm:ormoor:v:48:y:2023:i:4:p:1934-1958. 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.

    We have no bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.