Orateur
Description
Abstract: McEneaney’s max-plus basis method allows one to approximate the value function of a deterministic optimal control problem by a supremum of elementary functions like quadratic forms. Recently, Ahmadi et al. developed an approximation method for Barabanov norms of switched linear systems, relying also on the approximation by suprema of quadratic forms. Related methods were developed in computer science, they allow one to compute program invariants, represented as intersections or unions or ellipsoids. In all these approaches, the solution of large scale linear matrix inequalities by semidefinite programming methods is the computational bottleneck. We will show that the recourse to semidefinite programming can be avoided by expressing piecewise quadratic invariant generation and value function approximation as a fixed point problem in the space of positive semidefinite matrices.
To do so, we introduce “noncommutative” analogues of Bellman operators, acting on spaces of matrices, instead of spaces of functions. The minima and maxima of functions are now replaced by selections of minimal upper bounds and maximal upper bounds, with respect to the Loewner order. By a theorem of Kadison, such selections are not unique. They are also not order preserving. However, the Bellman type operators which arise in this way retain a remarkable structure. Indeed, they appear as the tropicalizations of the completely positive maps representing quantum channels, and the convergence of numerical schemes can be established by exploiting metric properties of the cone of positive definite matrices. This allows us to obtain relaxed solutions for very large scale instances (e.g., approximations of the joint spectra radius in dimension 500). We finally refine this approach in the special case of positive switched linear systems; then, the tropical Kraus map is replaced by a risk sensitive ergodic operator, whose eigenvalue bounds the joint spectral radius.
This is a joint work with Nikolas Stott.
