论文标题
使用理性最小化器最小化凸功能
Minimizing Convex Functions with Rational Minimizers
论文作者
论文摘要
给定一个分离的Oracle $ \ Mathsf {so} $，用于convex函数$ f $在$ \ mathbb {r}^n $上定义的，它在带有半径$ r $的盒子内有一个积分的最小化器，我们显示如何在最多使用$ f $的确切最小化器（n \ log log log（n） + log（n） + f $ f $ f $ $ \ Mathsf {so} $和$ \ Mathsf {poly}（n，\ log（r））$ arithmetic操作，或（b）$ o（n \ log（nr））$调用$ \ mathsf {so} $} $和$ \ \ \ \ \ exp（o（n））\ cdot \ cdot \ cdot \ mathsf {polod and arith（arith arith arith arith（nr））（s so} $} $（arith）当$ f $的最小化器集具有不可或缺的极端点时，我们的算法输出了$ f $不可或缺的最小化器。对于多项式时间算法的$ O（N^2（n + \ log（r）））的先前最佳甲骨文复杂性和$ o（n^2 \ log（nr））$的指数时间算法$（n^2 \ log（nr））$改善了这一点。梳子。选择。 1984年，施普林格（Springer）1988年]三十年前。我们对Grötschel，Lovász和Schrijver的结果的改进概括为$ f $的最小化器集合是具有有界顶点复杂性的理性多面体。 对于次管函数最小化问题，我们的结果立即暗示着一种强烈的多项式算法，最多可以使$ O（n^3 \ log \ log \ log \ log \ log（n）/\ log（n））$调用评估甲骨文，而指数时间算法则最多使$ o（n^2 \ log log（n）$ call to评估。这些改进了以前最好的$ O（N^3 \ log^2（n））$ Oracle复杂性，用于[Lee，Sidford and Wong and Wong，Focs 2015]中给出的强烈多项式算法，以及[Dadush，Végh和Zambelli，Soda，Soda 2018]，以及与Oracle Complectity $ O（n^n^3 3 3 3 3 3 3 3 \ ingultightient Time Algorithm一起使用）。 我们的结果是通过减少晶格中最短的向量问题来实现的。我们使用潜在功能分析其甲骨文复杂性，该功能同时捕获搜索集的大小和晶格的密度。
Given a separation oracle $\mathsf{SO}$ for a convex function $f$ defined on $\mathbb{R}^n$ that has an integral minimizer inside a box with radius $R$, we show how to find an exact minimizer of $f$ using at most (a) $O(n (n \log \log (n)/\log (n) + \log(R)))$ calls to $\mathsf{SO}$ and $\mathsf{poly}(n, \log(R))$ arithmetic operations, or (b) $O(n \log(nR))$ calls to $\mathsf{SO}$ and $\exp(O(n)) \cdot \mathsf{poly}(\log(R))$ arithmetic operations. When the set of minimizers of $f$ has integral extreme points, our algorithm outputs an integral minimizer of $f$. This improves upon the previously best oracle complexity of $O(n^2 (n + \log(R)))$ for polynomial time algorithms and $O(n^2\log(nR))$ for exponential time algorithms obtained by [Grötschel, Lovász and Schrijver, Prog. Comb. Opt. 1984, Springer 1988] over thirty years ago. Our improvement on Grötschel, Lovász and Schrijver's result generalizes to the setting where the set of minimizers of $f$ is a rational polyhedron with bounded vertex complexity. For the Submodular Function Minimization problem, our result immediately implies a strongly polynomial algorithm that makes at most $O(n^3 \log \log (n)/\log (n))$ calls to an evaluation oracle, and an exponential time algorithm that makes at most $O(n^2 \log(n))$ calls to an evaluation oracle. These improve upon the previously best $O(n^3 \log^2(n))$ oracle complexity for strongly polynomial algorithms given in [Lee, Sidford and Wong, FOCS 2015] and [Dadush, Végh and Zambelli, SODA 2018], and an exponential time algorithm with oracle complexity $O(n^3 \log(n))$ given in the former work. Our result is achieved via a reduction to the Shortest Vector Problem in lattices. We analyze its oracle complexity using a potential function that simultaneously captures the size of the search set and the density of the lattice.
