Search

Given a semialgebraic set $K \subseteq \mathbb{R}^{N}$ determined by a finite set of polynomial inequalities {g1 ≥ 0, ..., gk ≥ 0} , we want to characterize a polynomial f which is positive (or non-negative) on K in terms of sums of squares and the polynomials g i used to describe K. Such a representation of f is an immediate witness to the positivity condition. Theorems about the existence of such representations also have various applications, notably in problems of optimizing polynomial functions on semialgebraic sets. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Stability of two-dimensional polynomials arises in fields as diverse as 2D digital signal and image processing ([11], [7], [18]), time-delay systems [14], repettitive, or multipass, processes [24], and target tracking in radar systems. For this reason, there have been a large number of stability criteria for 2D polynomials, which have been surveyed and discussed in a number of papers ([13], [22], [9], [4], [5], [21]). In achieving the maximal efficiency of 2D stability tests, the reduction of algebraic complexity offered by the stability criteria in [26] has been useful. Apart from some minor conditions, the criteria convert stability testing of a 2D polynomial to testing of only two 1D polynomials, one for stability and the other for positivity. [ABSTRACT FROM AUTHOR]

Consider an ideal $I := \langle g•{1} , . . . ,g•{n}\rangle \subset \mathbb{R}[x•{1}, ..., x•{n}]$ generated by polynomials $\{g•{i}\}^{n}•{i=1} \mathbb{R}[x•{1}, ..., x•{n}]$. Let us call G := {g1, ... , gn} a polynomial set and let a term ordering of monomials with x1 < x2 ... < xn be given. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing a form on the standard simplex [equivalently, the problem of minimizing an even form on the unit sphere]. Two converging hierarchies of approximations for this problem can be constructed, that are based, respectively, on results by Schmüdgen-Putinar and by Pólya about representations of positive polynomials in terms of sums of squares. We show that the two approaches yield, in fact, the same approximations. [ABSTRACT FROM AUTHOR]

A general H∞ controller design technique is proposed for scalar linear systems, based on properties of positive polynomial matrices. The order of the controller is fixed from the outset, independently of the order of the plant and weighting functions. A sufficient LMI condition is used to overcome nonconvexity of the original design problem. The key design step, as well as the whole degrees of freedom are in the choice of a central polynomial, or desired closed-loop characteristic polynomial. [ABSTRACT FROM AUTHOR]

We study here the static state-feedback stabilization of linear finite dimensional systems depending polynomially upon a finite set of real, bounded, parameters. These parameters are a priori unknown, but available in realtime for control. In consequence, it is natural to allow possible dependence of the gain with respect to the parameters (gain-scheduling). [ABSTRACT FROM AUTHOR]

Robust stability analysis of state space models with respect to real parametric uncertainty is a widely studied challenging problem. In this paper, a quite general uncertainty model is considered, which allows one to consider polynomial nonlinearities in the uncertain parameters. A class of parameter-dependent Lyapunov functions is used to establish stability of a matrix depending polynomially on a vector of parameters constrained in a polytope. Such class, denoted as Homogeneous Polynomially Parameter-Dependent Quadratic Lyapunov Functions (HPD-QLFs), contains quadratic Lyapunov functions whose dependence on the parameters is expressed as a polynomial homogeneous form. Its use is motivated by the property that the considered matricial uncertainty set is stable if and only there exists a HPD-QLF. The paper shows that a sufficient condition for the existence of a HPD-QLF can be derived in terms of Linear Matrix Inequalities (LMIs). [ABSTRACT FROM AUTHOR]

Recent improvements of semi-definite programming solvers and developments on polynomial optimization have resulted in a large increase of the research activity on the application of the so-called sum-of-squares (SOS) technique in control. In this approach non-convex polynomial optimization programs are approximated by a family of convex problems that are relaxations of the original program [4, 22]. These relaxations are based on decompositions of certain polynomials into a sum of squares. Using a theorem of Putinar [28] it can be shown (under suitable constraint qualifications) that the optimal values of these relaxed problems converge to the optimal value of the original problem. These relaxation schemes have recently been applied to various nonconvex problems in control such as Lyapunov stability of nonlinear dynamic systems [25, 5] and robust stability analysis [15]. [ABSTRACT FROM AUTHOR]

We consider nonlinear systems with polynomial vector fields and pose two classes of system theoretic problems that may be solved by sum of squares programming. The first is disturbance analysis using three different norms to bound the reachable set. The second is the synthesis of a polynomial state feedback controller to enlarge the provable region of attraction. We also outline a variant of the state feedback synthesis for handling systems with input saturation. Both classes of problems are demonstrated using two-state nonlinear systems. [ABSTRACT FROM AUTHOR]

Recent advances in semidefinite programming along with use of the sum of squares decomposition to check nonnegativity have paved the way for efficient and algorithmic analysis of systems with polynomial vector fields. In this paper we present a systematic methodology for analyzing the more general class of non-polynomial vector fields, by recasting them into rational vector fields. The sum of squares decomposition techniques can then be applied in conjunction with an extension of the Lyapunov stability theorem to investigate the stability and other properties of the recasted systems, from which properties of the original, non-polynomial systems can be inferred. This will be illustrated by some examples from the mechanical and chemical engineering domains. [ABSTRACT FROM AUTHOR]

When the problem of restricted complexity identification is addressed in a set membership setting, the selection of the worst-case optimal model requires the solution of complex optimization problems. This paper studies different classes of suboptimal estimators and provides tight upper bounds on their identification error, in order to assess the reliability level of the identified models. Results are derived for fairly general classes of sets and norms, in the framework of Information Based Complexity theory. [ABSTRACT FROM AUTHOR]