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

• 成果类型: Article
• 署名作者: Dadush, Daniel; Koh, Zhuan Khye; Natura, Bento; Vegh, Laszlo A.
• 署名单位: University of London; London School Economics & Political Science
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1326
• 发表日期: 2023
• 页码: 1934-1958
• 关键词: linear inequalities; polynomial algorithm; submodular function; integer programs; tight bounds

摘要

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(m2logm) 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.