Solving Large-Scale Robust Stability Problems by Exploiting the Parallel Structure of Polya's Theorem

Abstract

In this paper, we propose a distributed computing approach to solving large-scale robust stability problems on the simplex. Our approach is to formulate the robust stability problem as an optimization problem with polynomial variables and polynomial inequality constraints. We use Polya's theorem to convert the polynomial optimization problem to a set of highly structured Linear Matrix Inequalities (LMIs). We then use a slight modification of a common interior-point primal-dual algorithm to solve the structured LMI constraints. This yields a set of extremely large yet structured computations. We then map the structure of the computations to a decentralized computing environment consisting of independent processing nodes with a structured adjacency matrix. The result is an algorithm which can solve the robust stability problem with the same per-core complexity as the deterministic stability problem with a conservatism which is only a function of the number of processors available. Numerical tests on cluster computers and supercomputers demonstrate the ability of the algorithm to efficiently utilize hundreds and potentially thousands of processors and analyze systems with 100+ dimensional state-space. The proposed algorithms can be extended to perform stability analysis of nonlinear systems and robust controller synthesis.

References in corpus (1)

• Symmetry groups, semidefinite programs, and sums of squares

Cited by in corpus (4)

• Polynomial Optimization with Applications to Stability Analysis and Control - Alternatives to Sum of Squares
• Constructing Piecewise Polynomial Lyapunov Functions for Local Stability of Nonlinear Systems Using Handelman's Theorem
• Parallel Optimization of Polynomials for Large-scale Problems in Stability and Control
• A Cyber-Physical Perspective to Pinning-Decision for Distributed Multi-Agent Control in Microgrid against Stochastic Communication Disruptions