Citation
Parrilo, Pablo A. (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd05062004055516
Abstract
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 frequencydependent LMIs is presented. These optimization problems arise from robustness analysis questions, via the KalmanYakubovichPopov 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 Positivstellensatzbased 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 wellknown 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): 

Thesis Committee: 

Defense Date:  18 May 2000 
Record Number:  CaltechETD:etd05062004055516 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd05062004055516 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  1647 
Collection:  CaltechTHESIS 
Deposited By:  Imported from ETDdb 
Deposited On:  07 May 2004 
Last Modified:  26 Dec 2012 02:40 
Thesis Files

PDF (ParriloThesis.pdf)
 Final Version
See Usage Policy. 889Kb 
Repository Staff Only: item control page