论文标题
二次优化的紧凑型混合整数编程放松
Compact mixed-integer programming relaxations in quadratic optimization
论文作者
论文摘要
我们提出了一种用于生产有效双重界限的技术，用于非凸二次优化问题。该方法利用优雅的分段线性近似来实现由于Yarotsky而引起的单变量二次函数，并使用混合成员编程（MIP）制定了此（简单）近似。值得注意的是，在此公式中使用的约束数量，二进制变量和辅助连续变量在近似误差中对数增长。将其与对角线扰动技术结合使用，将不可分割的二次函数转换为可分离的函数，我们提出了混合构成凸的二次放松，以解决非凸二次二次优化问题。我们研究我们的配方的强度（或清晰度）及其近似的紧密度。此外，我们表明我们的公式通过灰色代码表示可行的点。我们从二次目标和/或约束的问题上取得了计算结果，这表明我们提出的方法i）整个台面的表现优于文献中现有的MIP放松，而ii）在固定时间预算中，硬实例比确切的求解器更高的界限。
We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky, formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in the approximation error. Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. Further, we show that our formulation represents feasible points via a Gray code. We close with computational results on problems with quadratic objectives and/or constraints, showing that our proposed method i) across the board outperforms existing MIP relaxations from the literature, and ii) on hard instances produces better bounds than exact solvers within a fixed time budget.
