A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
Yitian Qian (),
Shaohua Pan () and
Shujun Bi ()
Additional contact information
Yitian Qian: South China University of Technology
Shaohua Pan: South China University of Technology
Shujun Bi: South China University of Technology
Computational Optimization and Applications, 2023, vol. 84, issue 3, No 7, 875-919
Abstract 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.
Keywords: UBPP; Matrix nonconvex relaxation approach; Global DC exact penalty; Burer–Monteiro factorization; 90C27; 90C22; 90C26 (search for similar items in EconPapers)
References: Add references at CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
http://link.springer.com/10.1007/s10589-022-00443-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:84:y:2023:i:3:d:10.1007_s10589-022-00443-2
Ordering information: This journal article can be ordered from
Access Statistics for this article
Computational Optimization and Applications is currently edited by William W. Hager
More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().