A multilevel analysis of the Lasserre hierarchy
A multilevel analysis of the Lasserre hierarchy
复制标题
Lasserre 层次结构的多级分析
DOI：
10.1016/j.ejor.2019.02.016
复制
发表时间：
2019
影响因子：
6.4
通讯作者：
Campos J
中科院分区：
文献类型：
--
作者：
Campos J
分析了拉瑟尔多项式优化(POP)方程的不同阶之间的关系。尽管对于某些情况，求解对应于层次的第一阶的半定规划松弛就足以解决潜在的POP，但其他问题需要顺序地求解第二阶或更高阶，直到找到解为止。对于这些情况，假设低阶半定规划松弛已解，我们开发了延拓算子，利用已计算的解来寻找高阶松弛解的初始逼近。我们可以证明使用该算子得到的点的层次在更高阶上是可行的，并且随着松弛阶数的增加而收敛到最优值。此外，对于在可行集上的投影容易计算的问题(例如，整数{0，1}和{−1，1}POP)，这些运算符是简单且廉价的。我们的数值实验表明，使用延拓算子可以提取出对实际应用有用的信息。特别是，我们说明了如何使用算子来提高不可行内点方法的效率，将它们作为初始点。我们使用这一技术来解决二次整数{0，1}问题，以及最大割和整数划分问题。
This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. For these cases, and assuming that the lower order semidefinite programming relaxation has been solved, we develop prolongation operators that exploit the solutions already calculated to find initial approximations for the solution of the higher order relaxation. We can prove feasibility in the higher order of the hierarchy of the points obtained using the operators, as well as convergence to the optimal as the relaxation order increases. Furthermore, the operators are simple and inexpensive for problems where the projection over the feasible set is “easy” to calculate (for example integer {0, 1} and {− 1, 1} POPs). Our numerical experiments show that it is possible to extract useful information for real applications using the prolongation operators. In particular, we illustrate how the operators can be used to increase the efficiency of an infeasible interior point method by using them as an initial point. We use this technique to solve quadratic integer {0, 1} problems, as well as MAX-CUT and integer partition problems.
影响因子：
2.2
作者：
Hande Y. Benson;D. Shanno
通讯作者：
Hande Y. Benson;D. Shanno
影响因子：
2.7
作者：
E. V. Dam;R. Sotirov
通讯作者：
R. Sotirov