A graph-based decomposition method for convex quadratic optimization with indicators
A graph-based decomposition method for convex quadratic optimization with indicators
复制标题
DOI：
10.1007/s10107-022-01845-0
复制
发表时间：
2021-10
影响因子：
2.7
通讯作者：
Peijing Liu;S. Fattahi;Andr'es G'omez;Simge Küçükyavuz
中科院分区：
文献类型：
--
作者：
Peijing Liu;S. Fattahi;Andr'es G'omez;Simge Küçükyavuz
本文考虑了目标函数中定义二次项的矩阵Q稀疏时的带指示变量的凸二次优化问题。我们使用一个图形表示的支持ofQ，并表明，如果这个图是一个路径，那么我们可以解决相关的问题在多项式时间。这使得我们能够构造一个紧凑的扩展配方的混合整数凸问题的上图的凸船体的封闭。此外，出于与图形模型的推理问题，我们提出了一种新的分解方法，一类一般（稀疏）严格对角dominantQ，它利用了路径的情况下的有效算法。我们的计算实验表明，所提出的方法相比，最先进的混合整数优化求解器的有效性。
In this paper, we consider convex quadratic optimization problems with indicator variables when the matrixQdefining the quadratic term in the objective is sparse. We use a graphical representation of the support ofQ, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This enables us to construct a compact extended formulation for the closure of the convex hull of the epigraph of the mixed-integer convex problem. Furthermore, motivated by inference problems with graphical models, we propose a novel decomposition method for a class of general (sparse) strictly diagonally dominantQ, which leverages the efficient algorithm for the path case. Our computational experiments demonstrate the effectiveness of the proposed method compared to state-of-the-art mixed-integer optimization solvers.