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

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

Luigi Grippo, Laura Palagi, Mauro Piacentini, Veronica Piccialli

Published Sep 1, 2009• 0 citations
OpenAlex

Abstract

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.

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

Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems

Liu Hongwei*, Xinhui Wang, Liu Sanyang

In this article, we propose a feasible direction algorithm for solving the semidefinite programming (SDP) relaxations of quadratic {−1, 1} programming problems. This algorithm's distinguishing features are that it uses a low rank factorization and searches with a constant step-size. Its convergence is also proven. Finally, we report some numerical examples to compare our method with the low rank factorization method of Burer and Monteiro on the SDP relaxation of the max-cut problem. *E-mail: xdliuhongwei@hotmail.com

Optimization methods & software•Apr 1, 2004•13 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•3 citations

On the numerical solution of Lasserre relaxations of unconstrained binary quadratic optimization problem

Soodeh Habibi, Michal Kočvara, Michael Stingl

Abstract The aim of this paper is to solve linear semidefinite programs arising from higher-order Lasserre relaxations of unconstrained binary quadratic optimization problems. For this we use an interior point method with a preconditioned conjugate gradient method solving the linear systems. The preconditioner utilizes the low-rank structure of the solution of the relaxations. In order to fully exploit this, we need to re-write the moment relaxations. To treat the arising linear equality constraints we use an $$\ell _1$$ ℓ 1 -penalty approach within the interior-point solver. The efficiency of this approach is demonstrated by numerical experiments with the MAXCUT and other randomly generated problems and a comparison with a state-of-the-art semidefinite solver and the ADMM method. We further propose a hybrid ADMM-interior-point method that proves to be efficient for certain problem classes. As a by-product, we observe that the second-order relaxation is often high enough to deliver a globally optimal solution of the original problem.

arXiv:2412.19776•Journal of Global Optimization•Jul 1, 2025•0 citations

Solving Lasserre relaxations of unconstrained binary quadratic optimization problems by an interior-point method

Soodeh Habibi, Michal Kočvara, Michael Stingl

The aim of this paper is to solve linear semidefinite programs arising from higher-order Lasserre relaxations of unconstrained binary quadratic optimization problems. For this we use an interior point method with a preconditioned conjugate gradient method solving the linear systems. The preconditioner utilizes the low-rank structure of the solution of the relaxations. In order to fully exploit this, we need to rewrite the moment relaxations. To treat the arising linear equality constraints we use an 1-penalty approach within the interior-point solver. The efficiency of this approach is demonstrated by numerical experiments with the MAXCUT and other randomly generated problems and a comparison with a state-of-the-art semidefinite solver and the ADMM method. As a by-product, we observe that the second-order relaxation is often high enough to deliver a globally optimal solution of the original problem.

•Jan 1, 2023•0 citations

A Rank-Two Feasible Direction Algorithm for the Binary Quadratic Programming

Xuewen Mu, Yaling Zhang

Based on the semidefinite programming relaxation of the binary quadratic programming, a rank-two feasible direction algorithm is presented. The proposed algorithm restricts the rank of matrix variable to be two in the semidefinite programming relaxation and yields a quadratic objective function with simple quadratic constraints. A feasible direction algorithm is used to solve the nonlinear programming. The convergent analysis and time complexity of the method is given. Coupled with randomized algorithm, a suboptimal solution is obtained for the binary quadratic programming. At last, we report some numerical examples to compare our algorithm with randomized algorithm based on the interior point method and the feasible direction algorithm on max-cut problem. Simulation results have shown that our method is faster than the other two methods.

Journal of Applied Mathematics•Jan 1, 2013•1 citation
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.
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.
In this article, we propose a feasible direction algorithm for solving the semidefinite programming (SDP) relaxations of quadratic {−1, 1} programming problems. This algorithm's distinguishing features are that it uses a low rank factorization and searches with a constant step-size. Its convergence is also proven. Finally, we report some numerical examples to compare our method with the low rank factorization method of Burer and Monteiro on the SDP relaxation of the max-cut problem. *E-mail: xdliuhongwei@hotmail.com
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.
Abstract The aim of this paper is to solve linear semidefinite programs arising from higher-order Lasserre relaxations of unconstrained binary quadratic optimization problems. For this we use an interior point method with a preconditioned conjugate gradient method solving the linear systems. The preconditioner utilizes the low-rank structure of the solution of the relaxations. In order to fully exploit this, we need to re-write the moment relaxations. To treat the arising linear equality constraints we use an ℓ1\ell _1ℓ1​ ℓ 1 -penalty approach within the interior-point solver. The efficiency of this approach is demonstrated by numerical experiments with the MAXCUT and other randomly generated problems and a comparison with a state-of-the-art semidefinite solver and the ADMM method. We further propose a hybrid ADMM-interior-point method that proves to be efficient for certain problem classes. As a by-product, we observe that the second-order relaxation is often high enough to deliver a globally optimal solution of the original problem.
The aim of this paper is to solve linear semidefinite programs arising from higher-order Lasserre relaxations of unconstrained binary quadratic optimization problems. For this we use an interior point method with a preconditioned conjugate gradient method solving the linear systems. The preconditioner utilizes the low-rank structure of the solution of the relaxations. In order to fully exploit this, we need to rewrite the moment relaxations. To treat the arising linear equality constraints we use an 1-penalty approach within the interior-point solver. The efficiency of this approach is demonstrated by numerical experiments with the MAXCUT and other randomly generated problems and a comparison with a state-of-the-art semidefinite solver and the ADMM method. As a by-product, we observe that the second-order relaxation is often high enough to deliver a globally optimal solution of the original problem.
Based on the semidefinite programming relaxation of the binary quadratic programming, a rank-two feasible direction algorithm is presented. The proposed algorithm restricts the rank of matrix variable to be two in the semidefinite programming relaxation and yields a quadratic objective function with simple quadratic constraints. A feasible direction algorithm is used to solve the nonlinear programming. The convergent analysis and time complexity of the method is given. Coupled with randomized algorithm, a suboptimal solution is obtained for the binary quadratic programming. At last, we report some numerical examples to compare our algorithm with randomized algorithm based on the interior point method and the feasible direction algorithm on max-cut problem. Simulation results have shown that our method is faster than the other two methods.