Input-Output Performance of Linear-Quadratic Saddle-Point Algorithms With Application to Distributed Resource Allocation Problems

John W. Simpson-Porco*, Bala Kameshwar Poolla, Nima Monshizadeh, Florian Dorfler

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)
70 Downloads (Pure)

Abstract

Saddle-point or primal-dual methods have recently attracted renewed interest as a systematic technique to design distributed algorithms, which solve convex optimization problems. When implemented online for streaming data or as dynamic feedback controllers, these algorithms become subject to disturbances and noise; convergence rates provide incomplete performance information, and quantifying input-output performance becomes more important. We analyze the input-output performance of the continuous-time saddle-point method applied to linearly constrained quadratic programs, providing explicit expressions for the saddle-point $\mathcal {H}_2$ norm under a relevant input-output configuration. We then proceed to derive analogous results for regularized and augmented versions of the saddle-point algorithm. We observe some rather peculiar effects-a modest amount of regularization significantly improves the transient performance, while augmentation does not necessarily offer improvement. We then propose a distributed dual version of the algorithm, which overcomes some of the performance limitations imposed by augmentation. Finally, we apply our results to a resource allocation problem to compare the input-output performance of various centralized and distributed saddle-point implementations and show that distributed algorithms may perform as well as their centralized counterparts.

Original languageEnglish
Pages (from-to)2032-2045
Number of pages14
JournalIEEE Transactions on Automatic Control
Volume65
Issue number5
DOIs
Publication statusPublished - May-2020

Keywords

  • Optimization
  • Heuristic algorithms
  • Convergence
  • Resource management
  • Standards
  • Distributed algorithms
  • Transient analysis
  • input-output performance
  • primal-dual dynamics
  • resource allocation
  • saddle-point methods
  • system norms
  • ECONOMIC-DISPATCH
  • OPTIMIZATION
  • STABILITY
  • DYNAMICS

Cite this