Classes of linear programs solvable by coordinate-wise minimization

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="https://doi.org/10.1007/s10472-021-09731-9" target="_blank" >https://doi.org/10.1007/s10472-021-09731-9</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10472-021-09731-9" target="_blank" >10.1007/s10472-021-09731-9</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Classes of linear programs solvable by coordinate-wise minimization

Popis výsledku v původním jazyce

Coordinate-wise minimization is a simple popular method for large-scale optimization. Unfortunately, for general (non-differentiable and/or constrained) convex problems, its fixed points may not be global minima. We present two classes of linear programs (LPs) that coordinate-wise minimization solves exactly. We show that these classes subsume the dual LP relaxations of several well-known combinatorial optimization problems and the method finds a global minimum with sufficient accuracy in reasonable runtimes. Moreover, we experimentally show that the method frequently yields good suboptima or even optima for sparse LPs where optimality is not guaranteed in theory. Though the presented problems can be solved by more efficient methods, our results are theoretically non-trivial and can lead to new large-scale optimization algorithms in the future.

Název v anglickém jazyce

Classes of linear programs solvable by coordinate-wise minimization

Popis výsledku anglicky

Coordinate-wise minimization is a simple popular method for large-scale optimization. Unfortunately, for general (non-differentiable and/or constrained) convex problems, its fixed points may not be global minima. We present two classes of linear programs (LPs) that coordinate-wise minimization solves exactly. We show that these classes subsume the dual LP relaxations of several well-known combinatorial optimization problems and the method finds a global minimum with sufficient accuracy in reasonable runtimes. Moreover, we experimentally show that the method frequently yields good suboptima or even optima for sparse LPs where optimality is not guaranteed in theory. Though the presented problems can be solved by more efficient methods, our results are theoretically non-trivial and can lead to new large-scale optimization algorithms in the future.

Druh

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

CEP obor

—

OECD FORD obor

10100 - Mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

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

Annals of Mathematics and Artificial Intelligence

ISSN

1012-2443

e-ISSN

1573-7470

Svazek periodika

90

Číslo periodika v rámci svazku

7-9

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

31

Strana od-do

777-807

Kód UT WoS článku

000640161200001

EID výsledku v databázi Scopus

2-s2.0-85104612998