ABSTRACT This paper studies semidefinite programming (SDP) relaxations for the Boolean Quadratic Programming problem with Generalized Upper Bound constraints (BQP-GUB), which arises in several application domains. We show that conventional semidefinite relaxation (SDR) does not yield tight bounds for this problem. We then analyze strengthened SDP relaxations and identify formulations that produce tight or near-tight bounds, particularly those based on reduced reformulation-linearization techniques (SDR+RRLT and SSDR+RRLT. Numerical experiments demonstrate that these approaches significantly reduce the relaxation gap compared to SDR, while highlighting the trade-off between bound quality and computational scalability.
ABSTRACT This paper studies semidefinite programming (SDP) relaxations for the Boolean Quadratic Programming problem with Generalized Upper Bound constraints (BQP-GUB), which arises in several application domains. We show that conventional semidefinite relaxation (SDR) does not yield tight bounds for this problem. We then analyze strengthened SDP relaxations and identify formulations that produce tight or near-tight bounds, particularly those based on reduced reformulation-linearization techniques (SDR+RRLT and SSDR+RRLT. Numerical experiments demonstrate that these approaches significantly reduce the relaxation gap compared to SDR, while highlighting the trade-off between bound quality and computational scalability.
In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.
Many computer vision problems can be formulated as binary quadratic programs (BQPs). Two classic relaxation methods are widely used for solving BQPs, namely, spec-tral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semidefinite relaxation has a tighter bound, but its computational complexity is high for large scale prob-lems. We present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, com-pared with conventional SDP methods, the new SDP for-mulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. Extensive experiments on various applications including clustering, image segmen-tation, co-segmentation and registration demonstrate the usefulness of our SDP formulation for solving large-scale BQPs. 1.
On the Ω(n) SDP relaxation gap for Submodular Box-Constrained Quadratic Programming
Continuous submodular optimization is an important class of nonconvex problems with global guarantees, for which the submodular box-constrained quadratic programming (BCQP) forms a fundamental subclass. It arises naturally as quadratic subproblems of general twice-differentiable submodular problems and also has direct business and management applications such as pricing. This paper studies the worst-case relaxation gap of semidefinite programming (SDP) relaxations with a finite family of valid linear cuts for submodular BCQP. We show that in dimension n≥4, for any SDP relaxation formulated with a finite family of linear cuts, there always exists a submodular BCQP instance with a strictly positive relaxation gap. By restricting to the normalized BCQP instances that remove the problem's scaling factor, we further quantify this limitation with explicit lower bounds. In general dimension n≥4, when the SDP relaxation is formulated with only Boolean-quadric-polytope (BQP) valid cuts, including the commonly used McCormick and triangle inequalities, we establish an Ω(n) relaxation gap lower bound. For an arbitrary family of m valid linear cuts, we establish an Ω(n/m2) lower bound. These results capture the fundamental limitations of SDP relaxations, especially SDP with BQP valid cuts, and provide guidance on what additional constraints may be needed for more effective convex approximations of submodular BCQP.
We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.
ABSTRACT Quadratically constrained quadratic programming (QCQP) problems appear in a wide range of engineering fields, including computer science, communication engineering, and finance. A key difficulty in solving these problems lies in efficiently finding global solutions, especially for large-scale and nonconvex instances. To address this, Wen & Yin (2013) proposed a method that reformulates semidefinite programming (SDP) relaxations of QCQPs into a nonlinear and nonconvex low-rank problem. This reformulated problem can be efficiently solved using a curvilinear search method combined with Barzilai-Borwein (BB) steps, known as the CSBB algorithm. In this study, we compare two approaches for solving QCQPs: the conventional convex SDP relaxation and the nonconvex low-rank reformulation introduced by Wen and Yin. We propose a set of general QCQP models that are compatible with the low-rank framework and conduct a series of numerical experiments to evaluate their performance. This study evaluates performance using several classes of NP-hard problems, including Binary Integer Quadratic (BIQ) problems, Max-Cut problems, Boolean Least Squares (BLS) problems, and 0-1 Quadratic Knapsack Problems (QKP). The results demonstrate that the low-rank approach offers competitive performance and shows strong potential for solving large-scale QCQPs more efficiently than traditional convex methods.