Catálogo de publicaciones - libros

We present an overview of several different techniques available for exploiting structure in the formulation of semidefinite programs based on the sum of squares decomposition of multivariate polynomials. We identify different kinds of algebraic properties of polynomial systems that can be successfully exploited for numerical efficiency. Our results here apply to three main cases: sparse polynomials, the ideal structure present in systems with explicit equality constraints, and structural symmetries, as well as combinations thereof. The techniques notably improve the size and numerical conditioning of the resulting SDPs, and are illustrated using several control-oriented applications.

We discuss fast implementations of primal-dual interior-point methods for semidefinite programs derived from the Kalman-Yakubovich-Popov lemma, a class of problems that are widely encountered in control and signal processing applications. By exploiting problem structure we achieve a reduction of the complexity by several orders of magnitude compared to general-purpose semidefinite programming solvers.

Optimization problems over several cones of non-negative polynomials are described; we focus on linear constraints on the coefficients that represent interpolation constraints. For these problems, the complexity of solving the dual formulation is shown to be almost independent of the number of constraints, provided that an appropriate preprocessing has been performed. These results are also extended to non-negative matrix polynomials and to interpolation constraints on the derivatives.

In this chapter we present SOSTOOLS, a third-party MATLAB toolbox for formulating and solving sum of squares optimization problems. Sum of squares optimization forms a basis for formulating convex relaxations to computationally hard problems such as some that appear in systems and control. Currently, sum of squares programs are solved by casting them as semidefinite programs, which can in turn be solved using interior-point based numerical methods. SOSTOOLS helps this translation in such a way that the underlying computations are abstracted from the user. Here we give a brief description of the toolbox, its features and capabilities (with emphasis on the recently added ones), as well as show how it can be applied to solving problems of interest in systems and control.

GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality (LMI) relaxations of non-convex optimization problems with multivariate polynomial objective function and constraints, based on the theory of moments. In contrast with the dual sum-of-squares decompositions of positive polynomials, the theory of moments allows to detect global optimality of an LMI relaxation and extract globally optimal solutions. In this report, we describe and illustrate the numerical linear algebra algorithm implemented in GloptiPoly for detecting global optimality and extracting solutions. We also mention some related heuristics that could be useful to reduce the number of variables in the LMI relaxations.