稠密k-子图问题的双非负松弛

稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。

带凸二次约束非凸二次规划的双非负规划松弛及其解法

针对带有非负变量、线性等式和凸二次约束的非凸二次规划问题,给出了一个带有矩阵非负和半正定约束的紧双非负规划(Doubly nonnegative programming,DNP)松弛,估计了它与原问题之间的间隙,并提出了求DNP松弛最优解的交替方向乘子法。数值实验表明:交替方向乘子法能有效找到DNP松弛问题的最优解,并且计算时间优于求解器CVX。