Projection methods for finding the greatest element of the intersection of max-closed convex sets

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00376325" target="_blank" >RIV/68407700:21230/24:00376325 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10479-024-05980-z" target="_blank" >https://doi.org/10.1007/s10479-024-05980-z</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10479-024-05980-z" target="_blank" >10.1007/s10479-024-05980-z</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Projection methods for finding the greatest element of the intersection of max-closed convex sets

Popis výsledku v původním jazyce

We focus on the problem of finding the greatest element of the intersection of max-closed convex sets. For this purpose, we analyze the famous method of cyclic projections and show that, if this method is suitably initialized and applied to max-closed convex sets, it converges to the greatest element of their intersection. Moreover, we propose another projection method, called the decreasing projection, which turns out both theoretically and practically preferable to Euclidean projections in this particular case. Next, we argue that several known algorithms, such as Bellman-Ford and Floyd-Warshall algorithms for shortest paths or Gauss-Seidel variant of value iteration in Markov decision processes, can be interpreted as special cases of iteratively applying decreasing projections onto certain max-closed convex sets. Finally, we link decreasing projections (and thus also the aforementioned algorithms) to bounds consistency in constraint programming.

Název v anglickém jazyce

Projection methods for finding the greatest element of the intersection of max-closed convex sets

Popis výsledku anglicky

We focus on the problem of finding the greatest element of the intersection of max-closed convex sets. For this purpose, we analyze the famous method of cyclic projections and show that, if this method is suitably initialized and applied to max-closed convex sets, it converges to the greatest element of their intersection. Moreover, we propose another projection method, called the decreasing projection, which turns out both theoretically and practically preferable to Euclidean projections in this particular case. Next, we argue that several known algorithms, such as Bellman-Ford and Floyd-Warshall algorithms for shortest paths or Gauss-Seidel variant of value iteration in Markov decision processes, can be interpreted as special cases of iteratively applying decreasing projections onto certain max-closed convex sets. Finally, we link decreasing projections (and thus also the aforementioned algorithms) to bounds consistency in constraint programming.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

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

Rok uplatnění

2024

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

Annals of Operations Research

ISSN

0254-5330

e-ISSN

1572-9338

Svazek periodika

340

Číslo periodika v rámci svazku

2-3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

26

Strana od-do

811-836

Kód UT WoS článku

001272296700002

EID výsledku v databázi Scopus

2-s2.0-85199008812