Robust Distributed Linear Programming

DOI10.1109/TAC.2015.2404451MaRDI QIDQ2982539zbMATH OpenOpenAlexFDO

Authors D. Richert, J. Cortés

Publication date 16 May 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.7140

Mathematics Subject Classification ID

Distributed algorithms (68W15) Linear programming (90C05)

Abstract: This paper presents a robust, distributed algorithm to solve general linear programs. The algorithm design builds on the characterization of the solutions of the linear program as saddle points of a modified Lagrangian function. We show that the resulting continuous-time saddle-point algorithm is provably correct but, in general, not distributed because of a global parameter associated with the nonsmooth exact penalty function employed to encode the inequality constraints of the linear program. This motivates the design of a discontinuous saddle-point dynamics that, while enjoying the same convergence guarantees, is fully distributed and scalable with the dimension of the solution vector. We also characterize the robustness against disturbances and link failures of the proposed dynamics. Specifically, we show that it is integral-input-to-state stable but not input-to-state stable. The latter fact is a consequence of a more general result, that we also establish, which states that no algorithmic solution for linear programming is input-to-state stable when uncertainty in the problem data affects the dynamics as a disturbance. Our results allow us to establish the resilience of the proposed distributed dynamics to disturbances of finite variation and recurrently disconnected communication among the agents. Simulations in an optimal control application illustrate the results.

Cited in

(6)

• Passivity-based generalization of primal-dual dynamics for non-strictly convex cost functions
• Distributed coordination for nonsmooth convex optimization via saddle-point dynamics
• Saddle-point dynamics: conditions for asymptotic stability of saddle points
• Distributed linear programming with event-triggered communication
• Solving Linear Programs Using Multiparty Computation
• Equilibrium optimiser tuned frequency-shifted internal model control proportional-derivative decoupled dual-loop design for industrial plants followed by experimental validation

This page was built for publication: Robust Distributed Linear Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2982539)