A Class of Linear Programs Solvable by Coordinate-Wise Minimization

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
A Class of Linear Programs Solvable by Coordinate-Wise Minimization
Original language description
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.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)