论文标题
在受约束的混合DR-subodular最小化上
On Constrained Mixed-Integer DR-Submodular Minimization
论文作者
论文摘要
DR-Subomodular函数包含一类广泛的函数，这些功能通常是非凸和非concave。我们研究了在框限制下以及可能的其他单调性约束下，具有连续和整数变量的任何DR-submodular函数的最小化问题。我们提出了在约束下任何DR-Submodular函数的题材的有效线性不平等现象。我们进一步提供了这种题材的完整凸面，令人惊讶的是，它是多面体的。我们为我们提出的有效不平等提出了多项式时间精确分离算法，我们首先通过该算法建立了此类混合构成非线性非线性优化问题的多项式时间可溶性。
DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide the complete convex hull of such an epigraph, which, surprisingly, turns out to be polyhedral. We propose a polynomial-time exact separation algorithm for our proposed valid inequalities, with which we first establish the polynomial-time solvability of this class of mixed-integer nonlinear optimization problems.
