OPTIMIZING THE PERRON EIGENVALUE WITH APPLICATIONS TO DYNAMICAL SYSTEMS AND GRAPHS - ALEKSANDAR CVETKOVIC
Optimizing spectral radius on a family of non-negative matrices is, in general, a very hard problem, since the spectral radius is a neither convex, nor concave function, nor is it Lipschitz. However, on matrix families having a special product (uncertainty) structure, efficient algorithms can be utilized to find the maximal/minimal spectral radius for a given family. Dr. Cvetkovic will present a novel selective greedy algorithm with a quadratic local convergence, which is able to find an optimal solution for non-negative product families of matrices quite fast and can handle very sparse matrices as well. Further, this method will be generalized for the optimization of spectral abscissa on Metzler matrices. These algorithms can then be applied to construct procedures for finding the closest (un)stable non-negative/Metzler matrix, in Schur/Hurwitz sense.
Dr. Cvetkovic will continue on to discuss the applications of the proposed procedures. Some of the most interesting applications are to the dynamical systems and graph theory. Interconnecting the presented methods with the theory of linear switching systems (LSS) and sign-stability of sign-Metzler matrices, he will propose a procedure for constructing an asymptotically stable LSS of any dimension (under an arbitrary switching signal) from an unstable one, while keeping close to its original structure. As for the applications to graph theory, an algorithm for approximating the maximal acyclic subgraph (MAS) will then be shown. Approximating MAS is a well-known NP-hard problem, with many applications (real and virtual social networks, biology, network flows, etc). The presented algorithm is as efficient as those presented in the literature while offering a completely innovative approach to the problem.
Dr. Cvetkovic also briefly discuss possible further research paths and application of presented algorithms to the machine and deep learning, which is currently one of the most attractive research topics.
(1 MB)