论文标题
基于同等直流惩罚分解矩阵程序的UBPPS的放松方法
A relaxation approach to UBPPs based on equivalent DC penalized factorized matrix programs
论文作者
论文摘要
本文与无约束的二进制多项式计划（UBPP）有关，该计划在许多科学和工程领域都有许多应用程序。通过利用其DC受限的SDP重新印度的全球确切惩罚，我们实现了同等的DC惩罚性SDP，并通过寻求有限数量的DC惩罚SDP的临界点来提出一种持续的放松方法，并提出了较高的惩罚因素。还开发了一种具有外推的全球收敛性最小化方法（MM）方法以捕获此类关键点。在温和的条件下，我们表明，弛豫方法的输出的排名是一个投影，是UBPP的近似可行解决方案，并从最佳值中量化其目标值的上限。与SDP松弛方法进行的数值比较，该方法采用特殊随机圆形技术和基于线性SDP的解决方案的DC松弛方法进行了比较\ textbf {1.824 \％}和\ textbf {2.870 \％}。
This paper is concerned with the unconstrained binary polynomial program (UBPP), which has a host of applications in many science and engineering fields. By leveraging the global exact penalty for its DC constrained SDP reformulation, we achieve an equivalent DC penalized SDP, and propose a continuous relaxation approach by seeking the critical point of the Burer-Monteiro factorization for a finite number of DC penalized SDPs with increasing penalty factors. A globally convergent majorization-minimization (MM) method with extrapolation is also developed to capture such critical points. Under a mild condition, we show that the rank-one projection of the output for the relaxation approach is an approximate feasible solution of the UBPP and quantify the upper bound of its objective value from the optimal value. Numerical comparisons with the SDP relaxation method armed with a special random rounding technique and the DC relaxation approach based on the solution of linear SDPs confirm the efficiency of the proposed relaxation approach, which can solve the instance of \textbf{20000} variables in \textbf{15} minutes and yield an upper bound to the optimal value and the known best value with a relative error at most \textbf{1.824\%} and \textbf{2.870\%}, respectively.
