Classes of linear programs solvable by coordinate-wise minimization
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Classes 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, 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10100 - Mathematics
Result continuities
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)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Annals of Mathematics and Artificial Intelligence
ISSN
1012-2443
e-ISSN
1573-7470
Volume of the periodical
90
Issue of the periodical within the volume
7-9
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
31
Pages from-to
777-807
UT code for WoS article
000640161200001
EID of the result in the Scopus database
2-s2.0-85104612998