A Caltech Library Service

Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization


Parrilo, Pablo A. (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/2K6Y-CH43.


In the first part of this thesis, we introduce a specific class of Linear Matrix Inequalities (LMI) whose optimal solution can be characterized exactly. This family corresponds to the case where the associated linear operator maps the cone of positive semidefinite matrices onto itself. In this case, the optimal value equals the spectral radius of the operator. It is shown that some rank minimization problems, as well as generalizations of the structured singular value ($mu$) LMIs, have exactly this property.

In the same spirit of exploiting structure to achieve computational efficiency, an algorithm for the numerical solution of a special class of frequency-dependent LMIs is presented. These optimization problems arise from robustness analysis questions, via the Kalman-Yakubovich-Popov lemma. The procedure is an outer approximation method based on the algorithms used in the computation of hinf norms for linear, time invariant systems. The result is especially useful for systems with large state dimension.

The other main contribution in this thesis is the formulation of a convex optimization framework for semialgebraic problems, i.e., those that can be expressed by polynomial equalities and inequalities. The key element is the interaction of concepts in real algebraic geometry (Positivstellensatz) and semidefinite programming.

To this end, an LMI formulation for the sums of squares decomposition for multivariable polynomials is presented. Based on this, it is shown how to construct sufficient Positivstellensatz-based convex tests to prove that certain sets are empty. Among other applications, this leads to a nonlinear extension of many LMI based results in uncertain linear system analysis.

Within the same framework, we develop stronger criteria for matrix copositivity, and generalizations of the well-known standard semidefinite relaxations for quadratic programming.

Some applications to new and previously studied problems are presented. A few examples are Lyapunov function computation, robust bifurcation analysis, structured singular values, etc. It is shown that the proposed methods allow for improved solutions for very diverse questions in continuous and combinatorial optimization.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:convexity; frequency domain inequalities; Positivstellensatz; relaxations; semidefinite programming; structured singular value
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Control and Dynamical Systems
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Doyle, John Comstock
Thesis Committee:
  • Doyle, John Comstock (chair)
  • Marsden, Jerrold E.
  • Chandy, K. Mani
  • Murray, Richard M.
Defense Date:18 May 2000
Record Number:CaltechETD:etd-05062004-055516
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1647
Deposited By: Imported from ETD-db
Deposited On:07 May 2004
Last Modified:21 Dec 2019 02:08

Thesis Files

PDF (Parrilo-Thesis.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page