Invited Session Tue.2.H 2038

Tuesday, 13:15 - 14:45 h, Room: H 2038

Cluster 4: Conic programming [...]

Applications of semidefinite programming


Chair: Etienne de Klerk



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

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.



Tuesday, 13:45 - 14:10 h, Room: H 2038, Talk 2

Uwe Truetsch
A "smart'' choice of a relaxation for the quadratic assignment problem within a branch-and-bound framework

Coauthors: Etienne de Klerk, Renata Sotirov


The practical approach to calculate an exact solution for a quadratic assignment problem (QAP) via a branch-and-bound framework depends strongly on a "smart'' choice of different strategies within the framework, for example the branching strategy, heuristics for the upper bound or relaxations for the lower bound. In this work, we compare different relaxations from the literature, in particular two promising semidefinite programming relaxations introduced by Zhao, Karisch, Rendl and Wolkowicz, and by Peng, Zhu, Luo and Toh respectively. The aim of our work is to generate and present a size-dependent choice of an appropriate relaxation that can be successfully used at a given node within a branch-and-bound framework.



Tuesday, 14:15 - 14:40 h, Room: H 2038, Talk 3

Xuan Vinh Doan
Feature extraction and data clustering with SDP-representable norms

Coauthor: Stephen Vavasis


We propose a convex optimization formulation with some SDP-representable norms to find approximately rank-one submatrices of a given nonnegative matrix. It has several applications in data mining, which includes feature extraction and data clustering. We develop a first-order method to solve the proposed optimization problem and report some promising numerical results.


  Payday Loans Wisconsin. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Levitra Online, but also as part of its analogs.