Computational Complexity in Robust Controller Design Problems based on the MPEP Global Optimization

Dr. Yuji Yamada, CDS Visiting Associate, Caltech

This talk is concerned with computational problems in robust control synthesis and their computational complexity. We first consider two particular approaches for solving control synthesis problems called Linear Matrix Inequality (LMI) approach and Bilinear Matrix Inequality (BMI) approach. While the LMI problem is considered to be computationally tractable from the existence of a polynomial time algorithm using convex optimization techniques, the BMI problem is known to be much more general than the LMI framework to cast control synthesis problems. However, since the BMI problem is nonconvex and NP-hard, it is extremely difficult to solve by existing global optimization approaches. Moreover, due to the lack of computational complexity analysis for these approaches, no one can tell even how difficult the problem is.

The purpose of this work is to provide another new approach based on the Matrix Product Eigenvalue Problem (MPEP), which defines a problem between the LMI problem and the BMI problem. The MPEP addresses most typical BMI problems in control synthesis, so it does not lose the generality as far as control synthesis problems are considered. Moreover, the specialty of the problem allows us to give a computational complexity analysis. In this work, we estimate the worst case computational complexity of our global algorithm for the MPEP, and investigate the actual case computational cost in terms of numerical experiments. These numerical experiments also illustrate that the computational effort for the MPEP is much less than that for the BMI approach.