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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

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

2023

Confidentiality

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

Name of the periodical

CONSTRAINTS

ISSN

1383-7133

e-ISSN

1572-9354

Volume of the periodical

28

Issue of the periodical within the volume

June

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

33

Pages from-to

244-276

UT code for WoS article

001035511000001

EID of the result in the Scopus database

2-s2.0-85165707206