A matrix nonconvex relaxation approach to unconstrained binary polynomial programs

作者：Qian, Yitian; Pan, Shaohua^*; Bi, Shujun

来源：Computational Optimization and Applications, 2023, 84(3): 875-919.

DOI：10.1007/s10589-022-00443-2

• UBPP
• Matrix nonconvex relaxation approach
• Global DC exact penalty
• Burer-Monteiro factorization

This paper is concerned with a class of unconstrained binary polynomial programs (UBPPs), which covers the classical binary quadratic program and has a host of applications in many science and engineering fields. We start with the global exact penalty of its DC constrained SDP reformulation, and propose a continuous relaxation approach by seeking a finite number of approximate stationary points for the factorized form of the global exact penalty with increasing penalty parameters. A globally convergent majorization-minimization method with extrapolation is developed to capture such stationary 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 lower bound of its minus objective value from the optimal value. Numerical comparisons with the SDP relaxation method armed with a special random rounding technique and the DC relaxation approaches armed with the solvers for linear and quadratic SDPs confirm the efficiency of the proposed relaxation approach, which can solve the instance of 20,000 variables in 15 min and yield a lower bound for the optimal value and the known best value with a relative error at most 1.824 and 2.870%, respectively.