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

arXiv:2501.03954

Learning to Select Between LP and SDP Relaxations for Nonconvex Quadratically Constrained Quadratic Programs

Dedeoglu, Muge, Ozen, Buket, Burak Kocuk

Published Jan 7, 2025• 1 citation
arXivHTMLPDF

Abstract

Quadratically constrained quadratic programs (QCQPs) are ubiquitous in optimization: Such problems arise in applications from operations research, power systems, signal processing, chemical engineering, and portfolio theory, among others. Despite their flexibility in modeling real-life situations and the recent effort to understand their properties, nonconvex QCQPs are hard to solve in practice. Most of the approaches in the literature are based on either Linear Programming (LP) or Semidefinite Programming (SDP) relaxations, each of which works very well for some problem subclasses but perform poorly on others. In this paper, we develop a relaxation selection procedure for nonconvex QCQPs that can adaptively decide whether an LP- or SDP-based approach is expected to be more beneficial by considering the instance structure. The proposed methodology relies on utilizing machine learning methods that involve features derived from spectral properties and sparsity patterns of data matrices, and once trained appropriately within a dimension-independent setup, the prediction model applies to any instance with an arbitrary number of variables and constraints. We develop classification and regression models under different feature-design setups, including a dimension-independent representation, and evaluate them on synthetically generated instances and a combined benchmark dataset consisting of MINLPLib and QPLIB instances. We further investigate relaxation selection within a spatial branch-and-bound framework, evaluating the trade-off between lower bound quality and computational time.

DOI
10.48550/arxiv.2501.03954

Related papers

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

Enhancing convexification techniques for solving nonconvex quadratic programming problems

Xiaofei Qi

At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .

•Jan 1, 2017•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

Concave Quadratic Cuts for Mixed-Integer Quadratic Problems

Jaehyun Park, Stephen Boyd

The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice ${\bf Z}^n$, and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.

arXiv:1510.06421•Oct 21, 2015•5 citations

Separable QCQPs and Their Exact SDP Relaxations

Masakazu Kojima, Sunyoung Kim, Naohiko Arima

This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters of the constraints. The proposed framework provides a simple sufficient condition for exactness of the resulting SDPR. We then identify notable classes of QCQPs for which this condition holds, including convex QCQPs, QCQPs defined by sign-pattern and graph-structural conditions, and separable homogeneous QCQPs with a limited number of constraints. Two examples illustrate the constructive nature of the proposed framework, showing how heterogeneous QCQPs can be combined to yield new instances with exact SDP relaxations.

arXiv:2604.02968•Apr 3, 2026•1 citation

Global solution of non-convex quadratically constrained quadratic programs

Sourour Elloumi, Amélie Lambert

The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.

Optimization methods & software•Jul 28, 2017•26 citations
Quadratically constrained quadratic programs (QCQPs) are ubiquitous in optimization: Such problems arise in applications from operations research, power systems, signal processing, chemical engineering, and portfolio theory, among others. Despite their flexibility in modeling real-life situations and the recent effort to understand their properties, nonconvex QCQPs are hard to solve in practice. Most of the approaches in the literature are based on either Linear Programming (LP) or Semidefinite Programming (SDP) relaxations, each of which works very well for some problem subclasses but perform poorly on others. In this paper, we develop a relaxation selection procedure for nonconvex QCQPs that can adaptively decide whether an LP- or SDP-based approach is expected to be more beneficial by considering the instance structure. The proposed methodology relies on utilizing machine learning methods that involve features derived from spectral properties and sparsity patterns of data matrices, and once trained appropriately within a dimension-independent setup, the prediction model applies to any instance with an arbitrary number of variables and constraints. We develop classification and regression models under different feature-design setups, including a dimension-independent representation, and evaluate them on synthetically generated instances and a combined benchmark dataset consisting of MINLPLib and QPLIB instances. We further investigate relaxation selection within a spatial branch-and-bound framework, evaluating the trade-off between lower bound quality and computational time.
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.
At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .
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.
The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice Zn{\bf Z}^nZn, and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.
This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters of the constraints. The proposed framework provides a simple sufficient condition for exactness of the resulting SDPR. We then identify notable classes of QCQPs for which this condition holds, including convex QCQPs, QCQPs defined by sign-pattern and graph-structural conditions, and separable homogeneous QCQPs with a limited number of constraints. Two examples illustrate the constructive nature of the proposed framework, showing how heterogeneous QCQPs can be combined to yield new instances with exact SDP relaxations.
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.