Exploiting Sparsity for Semi-Algebraic Set Volume Computation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00357943" target="_blank" >RIV/68407700:21230/22:00357943 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10208-021-09508-w" target="_blank" >https://doi.org/10.1007/s10208-021-09508-w</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10208-021-09508-w" target="_blank" >10.1007/s10208-021-09508-w</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Exploiting Sparsity for Semi-Algebraic Set Volume Computation

Popis výsledku v původním jazyce

We provide a systematic deterministic numerical scheme to approximate the volume (i.e., the Lebesgue measure) of a basic semi-algebraic set whose description follows a correlative sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set. This is a particular instance of a generalized moment problem which in turn can be approximated as closely as desired by solving a hierarchy of semidefinite relaxations of increasing size. The novelty with respect to previous work is that by exploiting the sparsity pattern we can provide a sparse formulation for which the associated semidefinite relaxations are of much smaller size. In addition, we can decompose the sparse relaxations into completely decoupled subproblems of smaller size, and in some cases computations can be done in parallel. To the best of our knowledge, it is the first contribution that exploits correlative sparsity for volume computation of semi-algebraic sets which are possibly high-dimensional and/or non-convex and/or non-connected.

Název v anglickém jazyce

Exploiting Sparsity for Semi-Algebraic Set Volume Computation

Popis výsledku anglicky

We provide a systematic deterministic numerical scheme to approximate the volume (i.e., the Lebesgue measure) of a basic semi-algebraic set whose description follows a correlative sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set. This is a particular instance of a generalized moment problem which in turn can be approximated as closely as desired by solving a hierarchy of semidefinite relaxations of increasing size. The novelty with respect to previous work is that by exploiting the sparsity pattern we can provide a sparse formulation for which the associated semidefinite relaxations are of much smaller size. In addition, we can decompose the sparse relaxations into completely decoupled subproblems of smaller size, and in some cases computations can be done in parallel. To the best of our knowledge, it is the first contribution that exploits correlative sparsity for volume computation of semi-algebraic sets which are possibly high-dimensional and/or non-convex and/or non-connected.

Druh

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

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

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

Foundations of Computational Mathematics

ISSN

1615-3375

e-ISSN

1615-3383

Svazek periodika

22

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

49

Strana od-do

161-209

Kód UT WoS článku

000633264700002

EID výsledku v databázi Scopus

2-s2.0-85103350064