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

Pesquisa Operacional

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

Nirakar Sahoo, Rupaj Kumar Nayak

Published Jan 1, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1590/0101-7438.2025.045.00294445

Related papers

An unconstrained approach for solving low rank SDP relaxations of {-1, 1} quadratic problems

Luigi Grippo, Laura Palagi, Mauro Piacentini +1 more

We consider low-rank semidefinite programming (LRSDP) relaxations of ±1 quadratic problems that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an effcient and globally convergent algorithm for finding critical points of the LRSDP problem. Finally, we test our code on an extended set of instances of the Max-Cut problem and we report comparisons with other existing codes.

•Sep 1, 2009•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

DECOMPOSITION AND RELAXATION ALGORITHMS FOR NONCONVEX MIXED INTEGER QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING PROBLEMS

TIAGO COUTINHO CARNEIRO DE ANDRADE

This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming.First, relaxations for quadratic programming and related problem classes are reviewed.Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables.Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations.This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances.The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36.Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1% in all instances, while Baron achieved relative gaps between 10% and 30% in most of them.

•Dec 13, 2018•0 citations

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

Dedeoglu, Muge, Ozen, Buket, Burak Kocuk

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.

arXiv:2501.03954•Jan 7, 2025•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

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
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.
We consider low-rank semidefinite programming (LRSDP) relaxations of ±1 quadratic problems that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an effcient and globally convergent algorithm for finding critical points of the LRSDP problem. Finally, we test our code on an extended set of instances of the Max-Cut problem and we report comparisons with other existing codes.
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 thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming.First, relaxations for quadratic programming and related problem classes are reviewed.Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables.Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations.This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances.The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36.Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1% in all instances, while Baron achieved relative gaps between 10% and 30% in most of them.
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.
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.
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.