Advanced

Distributed Semidefinite Programming with Application to Large-scale System Analysis

Khoshfetrat Pakazad, Sina; Hansson, Anders; Andersen, Martin S. and Rantzer, Anders LU (2017) In IEEE Transactions on Automatic Control
Abstract

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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Algorithm design and analysis, Convergence, Couplings, Distributed algorithms, distributed algorithms, interconnected uncertain systems, Linear matrix inequalities, primal-dual methods, robustness analysis, SDPs, Symmetric matrices, Uncertain systems
in
IEEE Transactions on Automatic Control
issue
99
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85028461780
ISSN
0018-9286
DOI
10.1109/TAC.2017.2739644
language
English
LU publication?
yes
id
40fe6a92-a325-46b2-8506-aa0728b8e189
date added to LUP
2017-09-07 11:57:58
date last changed
2018-03-02 10:12:23
@article{40fe6a92-a325-46b2-8506-aa0728b8e189,
  abstract     = {<p>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.</p>},
  author       = {Khoshfetrat Pakazad, Sina and Hansson, Anders and Andersen, Martin S. and Rantzer, Anders},
  issn         = {0018-9286},
  keyword      = {Algorithm design and analysis,Convergence,Couplings,Distributed algorithms,distributed algorithms,interconnected uncertain systems,Linear matrix inequalities,primal-dual methods,robustness analysis,SDPs,Symmetric matrices,Uncertain systems},
  language     = {eng},
  month        = {08},
  number       = {99},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Automatic Control},
  title        = {Distributed Semidefinite Programming with Application to Large-scale System Analysis},
  url          = {http://dx.doi.org/10.1109/TAC.2017.2739644},
  year         = {2017},
}