On the convergence of discrete-time linear systems: A linear time-varying Mann iteration converges iff the operator is strictly pseudocontractive

Giuseppe Belgioioso, Filippo Fabiani, Franco Blanchini, Sergio Grammatico

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Citaties (Scopus)

Uittreksel

We adopt an operator-theoretic perspective to study convergence of linear fixed-point iterations and discrete- time linear systems. We mainly focus on the so-called Krasnoselskij-Mann iteration x(k+1) = ( 1 - \alpha(k) ) x(k) + \alpha(k) A x(k), which is relevant for distributed computation in optimization and game theory, when A is not available in a centralized way. We show that convergence to a vector in the kernel of (I-A) is equivalent to strict pseudocontractiveness of the linear operator x -> Ax. We also characterize some relevant operator-theoretic properties of linear operators via eigenvalue location and linear matrix inequalities. We apply the convergence conditions to multi-agent linear systems with vanishing step sizes, in particular, to linear consensus dynamics and equilibrium seeking in monotone linear-quadratic games.
TaalEngels
Pagina's453-458
TijdschriftIEEE Control Systems Letters
Volume2
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 3 jul 2018

Vingerafdruk

Mann Iteration
Discrete-time Linear Systems
Linear Time
Time-varying
Strictly
Converge
Linear Operator
Operator
Fixed Point Iteration
Distributed Computation
Optimization Theory
Convergence Condition
Game Theory
Multi-agent Systems
Matrix Inequality
Linear Inequalities
Monotone
Linear Systems
Game
kernel

Trefwoorden

  • math.OC
  • cs.GT
  • cs.SY

Citeer dit

@article{278d0064494444398720f0170869b9cb,
title = "On the convergence of discrete-time linear systems: A linear time-varying Mann iteration converges iff the operator is strictly pseudocontractive",
abstract = "We adopt an operator-theoretic perspective to study convergence of linear fixed-point iterations and discrete- time linear systems. We mainly focus on the so-called Krasnoselskij-Mann iteration x(k+1) = ( 1 - \alpha(k) ) x(k) + \alpha(k) A x(k), which is relevant for distributed computation in optimization and game theory, when A is not available in a centralized way. We show that convergence to a vector in the kernel of (I-A) is equivalent to strict pseudocontractiveness of the linear operator x -> Ax. We also characterize some relevant operator-theoretic properties of linear operators via eigenvalue location and linear matrix inequalities. We apply the convergence conditions to multi-agent linear systems with vanishing step sizes, in particular, to linear consensus dynamics and equilibrium seeking in monotone linear-quadratic games.",
keywords = "math.OC, cs.GT, cs.SY",
author = "Giuseppe Belgioioso and Filippo Fabiani and Franco Blanchini and Sergio Grammatico",
year = "2018",
month = "7",
day = "3",
doi = "10.1109/LCSYS.2018.2840882",
language = "English",
volume = "2",
pages = "453--458",
journal = "IEEE Control Systems Letters",
issn = "2475-1456",
publisher = "Institute of Electrical and Electronics Engineers",
number = "3",

}

On the convergence of discrete-time linear systems : A linear time-varying Mann iteration converges iff the operator is strictly pseudocontractive. / Belgioioso, Giuseppe; Fabiani, Filippo; Blanchini, Franco; Grammatico, Sergio.

In: IEEE Control Systems Letters, Vol. 2, Nr. 3, 03.07.2018, blz. 453-458.

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

TY - JOUR

T1 - On the convergence of discrete-time linear systems

T2 - IEEE Control Systems Letters

AU - Belgioioso,Giuseppe

AU - Fabiani,Filippo

AU - Blanchini,Franco

AU - Grammatico,Sergio

PY - 2018/7/3

Y1 - 2018/7/3

N2 - We adopt an operator-theoretic perspective to study convergence of linear fixed-point iterations and discrete- time linear systems. We mainly focus on the so-called Krasnoselskij-Mann iteration x(k+1) = ( 1 - \alpha(k) ) x(k) + \alpha(k) A x(k), which is relevant for distributed computation in optimization and game theory, when A is not available in a centralized way. We show that convergence to a vector in the kernel of (I-A) is equivalent to strict pseudocontractiveness of the linear operator x -> Ax. We also characterize some relevant operator-theoretic properties of linear operators via eigenvalue location and linear matrix inequalities. We apply the convergence conditions to multi-agent linear systems with vanishing step sizes, in particular, to linear consensus dynamics and equilibrium seeking in monotone linear-quadratic games.

AB - We adopt an operator-theoretic perspective to study convergence of linear fixed-point iterations and discrete- time linear systems. We mainly focus on the so-called Krasnoselskij-Mann iteration x(k+1) = ( 1 - \alpha(k) ) x(k) + \alpha(k) A x(k), which is relevant for distributed computation in optimization and game theory, when A is not available in a centralized way. We show that convergence to a vector in the kernel of (I-A) is equivalent to strict pseudocontractiveness of the linear operator x -> Ax. We also characterize some relevant operator-theoretic properties of linear operators via eigenvalue location and linear matrix inequalities. We apply the convergence conditions to multi-agent linear systems with vanishing step sizes, in particular, to linear consensus dynamics and equilibrium seeking in monotone linear-quadratic games.

KW - math.OC

KW - cs.GT

KW - cs.SY

U2 - 10.1109/LCSYS.2018.2840882

DO - 10.1109/LCSYS.2018.2840882

M3 - Article

VL - 2

SP - 453

EP - 458

JO - IEEE Control Systems Letters

JF - IEEE Control Systems Letters

SN - 2475-1456

IS - 3

ER -