Distributed Semidefinite Programming with Application to Large-scale System Analysis
(English)Manuscript (preprint) (Other academic)
Distributed algorithms for solving coupled semidefinite programs (SDPs) commonly require manyiterations to converge. They also put high computational demand on the computational agents. In thispaper we show that in case the coupled problem has an inherent tree structure, it is possible to devisean efficient distributed algorithm for solving such problems. This algorithm can potentially enjoy thesame efficiency as centralized solvers that exploit sparsity. The proposed algorithm relies on predictorcorrectorprimal-dual interior-point methods, where we use a message-passing algorithm to compute thesearch directions distributedly. Message-passing here is closely related to dynamic programming overtrees. This allows us to compute the exact search directions in a finite number of steps. Furthermorethis number can be computed a priori and only depends on the coupling structure of the problem. Weuse the proposed algorithm for analyzing robustness of large-scale uncertain systems distributedly. Wetest the performance of this algorithm using numerical examples.
IdentifiersURN: urn:nbn:se:liu:diva-117496OAI: oai:DiVA.org:liu-117496DiVA: diva2:808669