Tuesday, 13:15 - 13:40 h, Room: H 2038


Amir Ali Ahmadi
Joint spectral radius, path-complete graphs, and semidefinite programming

Coauthors: Raphaƫl Jungers, Pablo A. Parrilo, Mardavij Roozbehani


The joint spectral radius (JSR) of a finite set of square matrices - a natural generalization of the notion of the spectral radius of a single matrix - characterizes the maximal growth rate that can be obtained by taking products, of arbitrary length, of all possible permutations of the matrices. Despite several undecidability and NP-hardness results related to computation (or approximation) of the JSR, the topic continues to attract attention because of a wide range of applications, including computation of the capacity of codes, robust stability of uncertain linear systems, Leontief input-output model of the economy with uncertain data, convergence of consensus algorithms, and many others. In this talk, we present our novel framework of path-complete graph Lyapunov functions which produces several hierarchies of asymptotically exact semidefinite programming relaxations with provable approximation guarantees. Our algorithms are based on new connections between ideas from control theory and the theory of finite automata.


Talk 1 of the invited session Tue.2.H 2038
"Applications of semidefinite programming" [...]
Cluster 4
"Conic programming" [...]


  . If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.