Convergence rates for sums-of-squares hierarchies with correlative sparsity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00374755" target="_blank" >RIV/68407700:21230/25:00374755 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10107-024-02071-6" target="_blank" >https://doi.org/10.1007/s10107-024-02071-6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10107-024-02071-6" target="_blank" >10.1007/s10107-024-02071-6</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Convergence rates for sums-of-squares hierarchies with correlative sparsity

Popis výsledku v původním jazyce

This work derives upper bounds on the convergence rate of the moment-sum-of-squares hierarchy with correlative sparsity for global minimization of polynomials on compact basic semialgebraic sets. The main conclusion is that both sparse hierarchies based on the Schmudgen and Putinar Positivstellensatze enjoy a polynomial rate of convergence that depends on the size of the largest clique in the sparsity graph but not on the ambient dimension. Interestingly, the sparse bounds outperform the best currently available bounds for the dense hierarchy when the maximum clique size is sufficiently small compared to the ambient dimension and the performance is measured by the running time of an interior point method required to obtain a bound on the global minimum of a given accuracy.

Název v anglickém jazyce

Convergence rates for sums-of-squares hierarchies with correlative sparsity

Popis výsledku anglicky

This work derives upper bounds on the convergence rate of the moment-sum-of-squares hierarchy with correlative sparsity for global minimization of polynomials on compact basic semialgebraic sets. The main conclusion is that both sparse hierarchies based on the Schmudgen and Putinar Positivstellensatze enjoy a polynomial rate of convergence that depends on the size of the largest clique in the sparsity graph but not on the ambient dimension. Interestingly, the sparse bounds outperform the best currently available bounds for the dense hierarchy when the maximum clique size is sufficiently small compared to the ambient dimension and the performance is measured by the running time of an interior point method required to obtain a bound on the global minimum of a given accuracy.

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

Mathematical Programming

ISSN

0025-5610

e-ISSN

1436-4646

Svazek periodika

209

Číslo periodika v rámci svazku

1-2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

39

Strana od-do

435-473

Kód UT WoS článku

001190454600001

EID výsledku v databázi Scopus

2-s2.0-85183794961