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

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. [ABSTRACT FROM AUTHOR]