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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

<a href="/cs/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotika a pokročilá průmyslová výroba</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název periodika

Journal of Global Optimization

ISSN

0925-5001

e-ISSN

1573-2916

Svazek periodika

93

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

23

Strana od-do

63-85

Kód UT WoS článku

001520712000001

EID výsledku v databázi Scopus

2-s2.0-105009525357