A Class 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%2F20%3A00342310" target="_blank" >RIV/68407700:21230/20:00342310 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-53552-0_8" target="_blank" >https://doi.org/10.1007/978-3-030-53552-0_8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-53552-0_8" target="_blank" >10.1007/978-3-030-53552-0_8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Class 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 it may not find global minima. We present a class of linear programs that coordinate-wise minimization solves exactly. We show that dual LP relaxations of several well-known combinatorial optimization problems are in this class and the method finds a global minimum with sufficient accuracy in reasonable runtimes. Moreover, for extensions of these problems that no longer are in this class the method yields reasonably good suboptima. Though the presented LP relaxations can be solved by more efficient methods (such as max-flow), our results are theoretically non-trivial and can lead to new large-scale optimization algorithms in the future.

Název v anglickém jazyce

A Class 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 it may not find global minima. We present a class of linear programs that coordinate-wise minimization solves exactly. We show that dual LP relaxations of several well-known combinatorial optimization problems are in this class and the method finds a global minimum with sufficient accuracy in reasonable runtimes. Moreover, for extensions of these problems that no longer are in this class the method yields reasonably good suboptima. Though the presented LP relaxations can be solved by more efficient methods (such as max-flow), our results are theoretically non-trivial and can lead to new large-scale optimization algorithms in the future.

Druh

D - Stať ve sborníku

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í

2020

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 statě ve sborníku

Learning and Intelligent Optimization

ISBN

978-3-030-53551-3

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

16

Strana od-do

52-67

Název nakladatele

Springer Nature Switzerland AG

Místo vydání

Basel

Místo konání akce

Athens

Datum konání akce

24. 5. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—