Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

A fast semidefinite approach to solving binary quadratic problems

Peng Wang, Chunhua Shen, Anton van den Hengel

Published Jan 1, 2013• 26 citations
OpenAlex

Abstract

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.

Related papers

Large-Scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications

Peng Wang, Chunhua Shen, Anton van den Hengel +1 more

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.

arXiv:1411.7564•IEEE Transactions on Pattern Analysis and Machine Intelligence•Mar 11, 2016•59 citations

A New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph

Chuan-Hao Guo, Liping Tang

Binary quadratic programming (BQP) problem was an NP-hard problem and had a large number of applications.In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem.Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation.When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation.Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.

International Conference on Mathematics, Modelling, Simulation and Algorithms (MMSA)•Jan 1, 2018•1 citation

New methods for handling binary constraints

Abhay Yadav, Rajeev Ranjan, Upal Mahbub +1 more

We consider the problem of handling binary constraints in optimization problems. We review methods for solving binary quadratic programs (BQPs), such as the spectral method and semidefinite programming relaxations. We then discuss two new methods for handling these constraints. The first involves the introduction of an extra unconstrained variable along with the alternating direction method of multipliers (ADMM), which has now also appeared in other recent literature. This allows the effect of the binary variables to be decoupled when they are minimized over. The second involves rewarding the one-norm while restricting the infinity-norm, based on a reformulation of the original problem. The piecewise linearity of the negative penalty results in the problem being convex until it hits a critical point, at which point the parameters of this linear term can be changed. These two methods can be applied to any problems which are convex except for binary constraints. In addition to testing them on BQPs, we show the efficacy of these approaches on point segmentation and image segmentation problems.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2016•12 citations

QUBO Dual Bounds via SDP Plane Projection Method

Apostolos Chalkis, Thomas Kleinert, Boro Sofranac

In this paper, we present a new method to solve a certain type of Semidefinite Programming (SDP) problems. These types of SDPs naturally arise in the Quadratic Convex Reformulation (QCR) method and can be used to obtain dual bounds of Quadratic Unconstrained Binary Optimization (QUBO) problems. QUBO problems have recently become the focus of attention in the quantum computing and optimization communities as they are well suited to both gate-based and annealing-based quantum computers on one side, and can encompass an exceptional variety of combinatorial optimization problems on the other. Our new method can be easily warm-started, making it very effective when embedded into a branch-and-bound scheme and used to solve the QUBO problem to global optimality. We test our method in this setting and present computational results showing the effectiveness of our approach.

arXiv:2312.15026•Dec 22, 2023•1 citation

A COMPUTATIONAL STUDY ON THE GLOBAL SOLUTION OF NONCONVEX QUADRATIC CONSTRAINTS AND QUADRATIC PROGRAMMING PROBLEMS

Nirakar Sahoo, Rupaj Kumar Nayak

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.

Pesquisa Operacional•Jan 1, 2025•0 citations

A Direct SDP Approach for Constrained Quadratic Binary Optimization Problems

MilaNedic, Zvmcevap

This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.

•Aug 25, 2026•0 citations
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.
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.
Binary quadratic programming (BQP) problem was an NP-hard problem and had a large number of applications.In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem.Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation.When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation.Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.
We consider the problem of handling binary constraints in optimization problems. We review methods for solving binary quadratic programs (BQPs), such as the spectral method and semidefinite programming relaxations. We then discuss two new methods for handling these constraints. The first involves the introduction of an extra unconstrained variable along with the alternating direction method of multipliers (ADMM), which has now also appeared in other recent literature. This allows the effect of the binary variables to be decoupled when they are minimized over. The second involves rewarding the one-norm while restricting the infinity-norm, based on a reformulation of the original problem. The piecewise linearity of the negative penalty results in the problem being convex until it hits a critical point, at which point the parameters of this linear term can be changed. These two methods can be applied to any problems which are convex except for binary constraints. In addition to testing them on BQPs, we show the efficacy of these approaches on point segmentation and image segmentation problems.
In this paper, we present a new method to solve a certain type of Semidefinite Programming (SDP) problems. These types of SDPs naturally arise in the Quadratic Convex Reformulation (QCR) method and can be used to obtain dual bounds of Quadratic Unconstrained Binary Optimization (QUBO) problems. QUBO problems have recently become the focus of attention in the quantum computing and optimization communities as they are well suited to both gate-based and annealing-based quantum computers on one side, and can encompass an exceptional variety of combinatorial optimization problems on the other. Our new method can be easily warm-started, making it very effective when embedded into a branch-and-bound scheme and used to solve the QUBO problem to global optimality. We test our method in this setting and present computational results showing the effectiveness of our approach.
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.
This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.