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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21110%2F25%3A00386760" target="_blank" >RIV/68407700:21110/25:00386760 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/s10898-025-01523-3" target="_blank" >https://doi.org/10.1007/s10898-025-01523-3</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10898-025-01523-3" target="_blank" >10.1007/s10898-025-01523-3</a>

Result language
angličtina
Original language name
On the numerical solution of Lasserre relaxations of unconstrained binary quadratic optimization problem
Original language description
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-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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10102 - Applied mathematics

Project
<a href="/en/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotics and advanced industrial production</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)