SDP-based branch-and-bound for non-convex quadratic integer optimization
SDP-based branch-and-bound for non-convex quadratic integer optimization
复制标题
基于 SDP 的分支定界非凸二次整数优化
DOI：
10.1007/s10898-018-0717-z
复制
发表时间：
2019
影响因子：
1.8
通讯作者：
Angelika
中科院分区：
文献类型：
--
作者：
Buchheim;Christoph;Montenegro;Maribel;Wiegele;Angelika
半定规划(SDP)松弛法已被广泛用于求解离散二次优化问题，特别是在二元情况下。对于具有盒约束的一般非凸整数情形，Buchheim和Wiegele(Math Program 141(1-2)：435-452,2013)提出了分枝定界算法Q-MIST，该算法基于著名的最大割SDP松弛算法的推广。对于得到的SDP，Q-MIST使用了一种现成的内点算法。在本文中，我们提出了一种定制的坐标上升算法来解决这些SDP的对偶问题。在董伟相关思想的基础上(SIAM J OpTim 26(3)：1962-1985,2016)，它利用了SDP的特殊结构，最重要的是约束矩阵的小排名。后者允许精确的线搜索和所涉及的逆矩阵的快速增量更新，从而整个算法可以在每次迭代的二次时间内运行。此外，我们还描述了如何将该方法扩展到特定的二维坐标更新。最后，我们解释了如何在该框架中包含任意线性约束，并通过实验对我们的算法进行了评估。
Semidefinite programming (SDP) relaxations have been intensively used for solving discrete quadratic optimization problems, in particular in the binary case. For the general non-convex integer case with box constraints, the branch-and-bound algorithm Q-MIST has been proposed by Buchheim and Wiegele (Math Program 141(1–2):435–452, 2013), which is based on an extension of the well-known SDP-relaxation for max-cut. For solving the resulting SDPs, Q-MIST uses an off-the-shelf interior point algorithm. In this paper, we present a tailored coordinate ascent algorithm for solving the dual problems of these SDPs. Building on related ideas of Dong (SIAM J Optim 26(3):1962–1985, 2016), it exploits the particular structure of the SDPs, most importantly a small rank of the constraint matrices. The latter allows both an exact line search and a fast incremental update of the inverse matrices involved, so that the entire algorithm can be implemented to run in quadratic time per iteration. Moreover, we describe how to extend this approach to a certain two-dimensional coordinate update. Finally, we explain how to include arbitrary linear constraints into this framework, and evaluate our algorithm experimentally.
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Pierre Bonami;O. Günlük;Jeff T. Linderoth
通讯作者：
Jeff T. Linderoth
影响因子：
3.1
作者：
Burer S
通讯作者：
Burer S