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

 

Abstract:
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" [...]

 

  Florida Loans Online can help you in trying times, but be sure to know the laws necessary for your loan application. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.