Title :
From coefficients to samples: a new approach to SOS optimization
Author :
Lofberg, J. ; Parrilo, P.A.
Author_Institution :
Automatic Control Laboratory, Swiss Federal Institute of Technology, Physikstrasse 3 - ETL - ETH Zurich, CH-8092 Zurich - Switzerland
Abstract :
We introduce a new methodology for the numerical solution of semidefinite relaxations arising from the sum of squares (SOS) decomposition of multivariate polynomials. The method is based on a novel SOS representation, where polynomials are represented by a finite set of values at discrete sampling points. The techniques have very appealing theoretical and numerical properties; the associated semidefinite programs are better conditioned, and have a rank one property that enables a fast computation of the search directions in interior point methods. The results are illustrated with examples, and a preliminary implementation is compared with previous techniques.
Keywords :
Autocorrelation; Automatic control; Constraint optimization; Control theory; Equations; Laboratories; Optimization methods; Polynomials; Sampling methods; Subspace constraints;
Conference_Titel :
Decision and Control, 2004. CDC. 43rd IEEE Conference on
Conference_Location :
Nassau
Print_ISBN :
0-7803-8682-5
DOI :
10.1109/CDC.2004.1428957