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

Soodeh Habibi (), Michal Kočvara () and Michael Stingl ()
Additional contact information
Soodeh Habibi: University of Liverpool
Michal Kočvara: University of Birmingham
Michael Stingl: Friedrich-Alexander-Universität Erlangen-Nürnberg

Journal of Global Optimization, 2025, vol. 93, issue 1, No 3, 63-85

Abstract: 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.

Keywords: Binary quadratic optimization; Lasserre hierarchy; Semidefinite optimization; Interior-point methods; Preconditioned conjugate gradients; MAXCUT problem; 90C22; 90C51; 65F08; 74P05 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01523-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:93:y:2025:i:1:d:10.1007_s10898-025-01523-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01523-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().