论文标题
加速的牛顿 - 丁基巴赫方法及其应用于每个不平等系统的两个变量
An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
论文作者
论文摘要
我们提出了牛顿 - 丁基巴赫方法的加速或“浏览”版本，这是一种众所周知的解决分数和参数优化问题的技术。这种加速度将每两个迭代中的当前迭代和最佳解决方案之间的差异减半。将Bregman差异作为与组合参数结合使用的潜力，我们在三个应用域中获得了强烈的多项式算法：（i）对于线性分数组合优化，我们显示了$ O（M \ log M）$ tererations $ tererations $ o（m \ log m）$迭代；以前的最佳界限是Wang等人的$ O（M^2 \ log M）$。 （2006）。 （ii）我们获得了一种强烈多项式标记校正算法，用于求解每个不等式两个变量的线性可行性系统（2VPI）。对于具有$ N $变量和$ M $约束的2VPI系统，我们的算法以$ O（MN）$迭代运行。每次迭代都需要$ O（MN）$时间用于一般2VPI系统，而确定性马尔可夫决策过程（DMDPS）的特殊情况（M + N \ log N）$时间。这扩展并加强了Madani（2002）的先前结果，该结果显示了用于求解DMDPS的牛顿 - 丁基巴赫方法的变体的弱多项式结合。 （iii）我们给出了Goemans等人的参数下函数最小化结果的简化变体。 （2017）。
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 et al. (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 (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 by Goemans et al. (2017).
