Papers › A relaxation approach to UBPPs based on equivalent DC penalized factorized matrix programs
A relaxation approach to UBPPs based on equivalent DC penalized factorized matrix programs
Yitian Qian, Shaohua Pan
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections