Polynomial Optimization Based Approaches to System Design, Analysis and Identification

Open Access
Feng, Chao
Graduate Program:
Electrical Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
June 21, 2013
Committee Members:
  • Constantino Manuel Lagoa, Dissertation Advisor
  • David Jonathan Miller, Committee Member
  • Ji Woong Lee, Committee Member
  • Qian Wang, Committee Member
  • Robust Control
  • Probabilistic Control
  • Distributional Robustness
  • Switched System
  • Identification
  • Interpolation
In recent developments of system and control theory, a large effort has been devoted to finding equivalent convex formulation of the problems of interest. A successful example is the wide application of linear matrix inequalities (LMIs) in formulating system design and analysis problems. From a theoretic point of view, such problems can be considered solved, as convex optimization can be solved reliably and efficient using interior-point methods or other methods available in the literature and/or commercial software. On the other hand, however, many challenging problems in system and control theory have been proven to be NP-Complete or NP-hard. Therefore, unless proven P=NP the best way to tackle these problems is to find approximate solutions using limited computational resources. Recent developments in polynomial optimization, which include moment-based approach and its dual sum-of-square method, sheds some light on solving some of those challenging problems, as it provides systematic approaches to build asymptotically convergent convex relaxations to a general polynomial optimization problem. In this dissertation, we use this as the main optimization tool to address various important yet difficult problems in system and control theory. The problems addressed are categorized into four topics: 1) chance-constraint optimization, 2) distributional robustness, 3) hybrid system identification, and 4) generalized fixed order interpolation. The first two topics is closely related to the probabilistic framework developed in recent years. In the first topic, we design special polynomial functions and use them to develop deterministic approaches to address the probabilistic constraints. Comparing the scenario approach in the literature of probabilistic control, which give soft bounds on probability, our approaches provide hard bounds. The second topic is connected to system analysis with uncertainty under probabilistic framework, in a distributional-free manner. Instead of assuming some fixed distribution on the uncertainty, it aims at finding the worst-case expected performance of the system, assuming the distribution of uncertainty is unknown but obey some loose conditions. The last two topics addressed concern hybrid system identification and generalized interpolation. We first show that these problems can be equivalently reformulated as polynomial optimization problems. While the recent developed polynomial optimization tools can construct convex relaxations to these problems, the required computational cost is prohibitively large. It is not surprising as a polynomial problem is NP-hard in general. In this dissertation, we exploit the very specific structure of these problems and provide numerically efficient algorithms to solve these problems.