On Relation Between Constraint Propagation and Block-Coordinate Descent in Linear Programs
| Autor: | Tomáš Werner, Tomáš Dlask |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
050101 languages & linguistics
Mathematical optimization Linear programming Computer science 05 social sciences MathematicsofComputing_NUMERICALANALYSIS Regular polygon 02 engineering and technology Fixed point Computer Science::Hardware Architecture Linear inequality 0202 electrical engineering electronic engineering information engineering Local consistency 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Special case Coordinate descent Descent (mathematics) |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030584740 CP |
| DOI: | 10.1007/978-3-030-58475-7_12 |
| Popis: | Block-coordinate descent (BCD) is a popular method in large-scale optimization. Unfortunately, its fixed points are not global optima even for convex problems. A succinct characterization of convex problems optimally solvable by BCD is unknown. Focusing on linear programs, we show that BCD fixed points are identical to fixed points of another method, which uses constraint propagation to detect infeasibility of a system of linear inequalities in a primal-dual loop (a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al.). This implies that BCD fixed points are global optima iff a certain propagation rule decides feasibility of a certain class of systems of linear inequalities. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|