TY - JOUR
T1 - Bivalent quadratic optimization with sum-of-square of quadratic penalties
AU - Zhang, Tongli
AU - Xia, Yong
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.
PY - 2025/8
Y1 - 2025/8
N2 - The problem of maximizing the sum-of-square of quadratic functions with bivalent variables, denoted by (P), arises from bivalent quadratic optimization with K quadratic disjunctive penalties. Though NP-hard in general, (P) is polynomially solvable when the input matrices can concatenate to a fixed-rank matrix. We present a nonconvex quadratic semidefinite programming (SDP) relaxation, which provides a 0.4-approximate solution for (P). We show that the quadratic SDP relaxation can be approximately and globally solved to a precision via solving at most linear SDP subproblems.
AB - The problem of maximizing the sum-of-square of quadratic functions with bivalent variables, denoted by (P), arises from bivalent quadratic optimization with K quadratic disjunctive penalties. Though NP-hard in general, (P) is polynomially solvable when the input matrices can concatenate to a fixed-rank matrix. We present a nonconvex quadratic semidefinite programming (SDP) relaxation, which provides a 0.4-approximate solution for (P). We show that the quadratic SDP relaxation can be approximately and globally solved to a precision via solving at most linear SDP subproblems.
KW - Approximation algorithm
KW - Bivalent quadratic optimization
KW - Quartic polynomial optimization
KW - Semidefinite programming
UR - https://www.scopus.com/pages/publications/105012846349
U2 - 10.1007/s10878-025-01339-7
DO - 10.1007/s10878-025-01339-7
M3 - 文章
AN - SCOPUS:105012846349
SN - 1382-6905
VL - 50
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 1
M1 - 12
ER -