Ahead of Print article · Journal article
Distributed Semidefinite Programming with Application to Large-scale System Analysis
Distributed algorithms for solving coupled semidefinite programs (SDPs) commonly require many iterations to converge. They also put high computational demand on the computational agents. In this paper we show that in case the coupled problem has an inherent tree structure, it is possible to devise an efficient distributed algorithm for solving such problems.
The proposed algorithm relies on predictor-corrector primal-dual interior-point methods, where we use a message-passing algorithm to compute the search directions distributedly. Message-passing here is closely related to dynamic programming over trees. This allows us to compute the exact search directions in a finite number of steps.
This is because, computing the search directions requires a recursion over the tree structure and hence, terminates after an upward and downward pass through the tree. Furthermore this number can be computed apriori and only depends on the coupling structure of the problem. We use the proposed algorithm for analyzing robustness of large-scale uncertain systems distributedly.
We test the performance of this algorithm using numerical examples.
Language: | English |
---|---|
Publisher: | IEEE |
Year: | 2017 |
Pages: | 1045-1058 |
ISSN: | 23343303 , 00189286 and 15582523 |
Types: | Ahead of Print article and Journal article |
DOI: | 10.1109/TAC.2017.2739644 |
ORCIDs: | Andersen, Martin S. |
Distributed algorithms Interconnected uncertain systems Primal-dual methods Robustness analysis Semidefinite programs (SDPs)
Algorithm design and analysis Convergence Couplings Linear matrix inequalities Symmetric matrices Uncertain systems computational agents computational complexity convex programming coupling structure distributed algorithms distributed semidefinite programming dynamic programming efficient distributed algorithm exact search directions finite number high computational demand inherent tree structure interconnected uncertain systems iterative methods large-scale system large-scale systems large-scale uncertain systems message passing message-passing algorithm nonlinear programming predictor-corrector primal-dual interior-point methods primal-dual methods robust control robustness analysis semidefinite programs semidefinite programs (SDPs) trees (mathematics) uncertain systems