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

Doubly non-negative programming relaxation for non-convex quadratic programming with convex quadratic constraint and its solution

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

A tight doubly non-negative programming(DNP)relaxation with non-negative and positive semi-definite matrix constraints is developed for non-convex quadratic programming problems with non-negative variables,linear equations,and convex quadratic constraints.The gap between it and the original problem is estimated,and an alternating direction multiplier method is proposed to find an optimal solution of DNP relaxation.The numerical experiments show that the optimal solution of DNP relaxation can be found effectively by applying the alternating direction multiplier method,and the calculation time is better than the solver CVX.