Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00367294" target="_blank" >RIV/68407700:21230/23:00367294 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10601-023-09349-0" target="_blank" >https://doi.org/10.1007/s10601-023-09349-0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10601-023-09349-0" target="_blank" >10.1007/s10601-023-09349-0</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs

Popis výsledku v původním jazyce

We study a constraint propagation algorithm to detect infeasibility of a system of linear inequalities over continuous variables, which we call activity propagation. Each iteration of this algorithm chooses a subset of the inequalities and if it infers that some of them are always active (i.e., always hold with equality), it turns them into equalities. We show that this algorithm can be described as chaotic iterations and its fixed points can be characterized by a local consistency, in a similar way to traditional local consistency methods in CSP such as arc consistency. Via complementary slackness, activity propagation can be employed to iteratively improve a dual-feasible solution of large-scale linear programs in a primal-dual loop – a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al. As our second contribution, we show that this method has the same set of fixed points as block-coordinate descent (BCD) applied to the dual linear program. While BCD is popular in large-scale optimization, its fixed points need not be global optima even for convex problems and a succinct characterization of convex problems optimally solvable by BCD remains elusive. Our result may open the way for such a characterization since it allows us to characterize BCD fixed points in terms of local consistencies.

Název v anglickém jazyce

Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs

Popis výsledku anglicky

We study a constraint propagation algorithm to detect infeasibility of a system of linear inequalities over continuous variables, which we call activity propagation. Each iteration of this algorithm chooses a subset of the inequalities and if it infers that some of them are always active (i.e., always hold with equality), it turns them into equalities. We show that this algorithm can be described as chaotic iterations and its fixed points can be characterized by a local consistency, in a similar way to traditional local consistency methods in CSP such as arc consistency. Via complementary slackness, activity propagation can be employed to iteratively improve a dual-feasible solution of large-scale linear programs in a primal-dual loop – a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al. As our second contribution, we show that this method has the same set of fixed points as block-coordinate descent (BCD) applied to the dual linear program. While BCD is popular in large-scale optimization, its fixed points need not be global optima even for convex problems and a succinct characterization of convex problems optimally solvable by BCD remains elusive. Our result may open the way for such a characterization since it allows us to characterize BCD fixed points in terms of local consistencies.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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í

2023

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

CONSTRAINTS

ISSN

1383-7133

e-ISSN

1572-9354

Svazek periodika

28

Číslo periodika v rámci svazku

June

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

33

Strana od-do

244-276

Kód UT WoS článku

001035511000001

EID výsledku v databázi Scopus

2-s2.0-85165707206