Minimizing Convex Functions with Integral Minimizers
Minimizing Convex Functions with Integral Minimizers
复制标题
使用积分极小化器最小化凸函数
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Haotian Jiang
中科院分区：
文献类型：
--
作者：
Haotian Jiang
给定一个分离的Oracle $ Mathsf {so} $用于凸函数$ f $，它在带有半径$ r $的盒子内有一个不可或缺的最小化器，我们显示如何有效地找到最小的$ f $的最小化器，最多使用$ o（n （n + log（r）））$调用$ Mathsf {so} $。当$ f $的最小化器集具有不可或缺的极端点时，我们的算法输出了$ f $不可或缺的最小化器。通过优雅的同时应用双苯胺近似值，由于[Grotschel，lovasz和Schrijver，Prog，通过同时使用同时的双苯胺近似值而获得的$ O（n^2（n + log（r）））$（n^2（n + log（r）））的甲骨文复杂性得到改善。梳子。选择。 1984年，施普林格（Springer）1988年]三十年前。我们猜想我们的甲骨文复杂性紧绷到恒定因素。
我们的结果立即暗示着一种强烈的多项式算法，用于最小$ o（n^3）$调用评估Oracle的函数最小化问题。这可以改善以前最好的$ O（n^3 log^2（n））$ oracle复杂性，用于[Lee，Sidford and Wong和Wong，focs 2015]和[Dadush，Vegh and Zambelli，Soda and Soda，2018]中给出的强烈多项式算法的复杂性。以及带有Oracle复杂性$ O（n^3 log（n））$的指数时间算法。
我们的结果是通过应用LLL算法的[Lenstra，Lenstra和Lovasz的数学而实现的。安。 [1982]对于最短的晶格矢量问题。我们展示了如何使用某些晶格的大约最短载体来减少问题的维度，以及与使用同时使用双磷灰碱近似值的Grotschel-Lovasz-Schrijver方法相比，这种过程的甲骨文复杂性如何有利。我们对甲骨文复杂性的分析基于一个潜在函数，该功能同时捕获搜索集的大小和晶格的密度。为了实现Oracle复杂性中的$ O（N^2）$项，应用了凸几何的技术成分。
Given a separation oracle $mathsf{SO}$ for a convex function $f$ that has an integral minimizer inside a box with radius $R$, we show how to efficiently find a minimizer of $f$ using at most $O(n (n + log(R)))$ calls to $mathsf{SO}$. 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)))$ obtained by an elegant application of simultaneous diophantine approximation due to [Grotschel, Lovasz and Schrijver, Prog. Comb. Opt. 1984, Springer 1988] over thirty years ago. We conjecture that our oracle complexity is tight up to constant factors.
Our result immediately implies a strongly polynomial algorithm for the Submodular Function Minimization problem that makes at most $O(n^3)$ calls to an evaluation oracle. This improves 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, Vegh 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 by an application of the LLL algorithm [Lenstra, Lenstra and Lovasz, Math. Ann. 1982] for the shortest lattice vector problem. We show how an approximately shortest vector of certain lattice can be used to reduce the dimension of the problem, and how the oracle complexity of such a procedure is advantageous compared with the Grotschel-Lovasz-Schrijver approach that uses simultaneous diophantine approximation. Our analysis of the oracle complexity is based on a potential function that captures simultaneously the size of the search set and the density of the lattice. To achieve the $O(n^2)$ term in the oracle complexity, technical ingredients from convex geometry are applied.
DOI：
10.1145/3313276.3316340
发表时间：
2018-09
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
J. Garg;László A. Végh
通讯作者：
J. Garg;László A. Végh
DOI：
10.1287/moor.2019.1011
发表时间：
2016-11
期刊：
Math. Oper. Res.
影响因子：
--
作者：
D. Dadush;László A. Végh;G. Zambelli
通讯作者：
D. Dadush;László A. Végh;G. Zambelli
影响因子：
1.7
作者：
Dadush D
通讯作者：
Dadush D