Generalized S‐procedure

The generalized S-procedure gives sufficient conditions for a polynomial to be nonnegative on a semialgebraic set using sum‐of‐squares polynomials. The generalized S-procedure has appeared frequently in applications of sum‐of‐squares optimization to analysis and control synthesis for dynamical systems, in particular for nonglobal results, and often leads to bilinear or nonlinear constraints. Its name is a reference to the classical S-procedure for quadratic inequalities (see, e.g., Wikipedia).

The generalized S-procedure makes a statement over the semi-algebraic set

$$K = \bigcap_{i=1}^N \{ x \in \mathbb R^n \mid g_i(x) \geq 0 \}$$

where $g_1, \ldots, g_N \in \mathbb R[n]$ are polynomials with indeterminate variables $x = (x_1, \ldots, x_n)$. These polynomials can be given (e.g., as state and/or input constraints) or be decision variables of a sum-of-squares optimization problem.

Statement

Let $p \in \mathbb R[x]$ be another polynomial in $x$; if there exists sum-of-squares polynomials $s_0, s_1, \ldots, s_N \in \Sigma[x]$ such that $p$ can be written as

$$p = s_0 + \sum_{i=1}^N s_i g_i$$

then

$$K \subseteq \{ x \in \mathbb R^n \mid p(x) \geq 0 \}$$

or, equivalently, $p$ is nonnegative over the set $K$.

The sufficient condition can equivalently be stated as $p - \sum_{i=1}^N s_i g_i \in \Sigma[x]$. In this form, the statement of the generalized S-procedure appeared in [Tan2006] with its name coined prior to that.^[JFT+2003] A similar, reverse statement is exploited for optimization of a polynomial cost function over (compact) semialgebraic sets.^{[Las2001],[Sch2005]}

Proof by inequalities

Consider any point $y \in K$, that is, $g_1(y) \geq 0, \ldots, g_N(y) \geq 0$. If $p$ admits the representation $p = s_0 + \sum_{i=1}^N s_i g_i$ with $s_0, s_1, \ldots, s_N \in \Sigma[x]$, then

$$p(y) = s_0(y) + \sum_{i=1}^N s_i(y) p_i(y) \geq 0$$

and hence, $y \in p^{-1}(\mathbb R_{\geq 0})$.

Proof by Positivstellensatz

The generalized S-procedure can be obtained as sufficient condition in the Positivstellensatz of the reals.^[Tan2006] Define:

• The multiplicative monoid of $f_1, \ldots, f_L \in \mathbb R[x]$ is the set

$$\mathcal M(f_1, \ldots, f_L) = \{ f_1^{r_1} \cdots f_L^{r_L} \mid r_1, \ldots, r_L \in \mathbb N_0 \}$$

• The polynomial cone of $g_1, \ldots, g_N \in \mathbb R[x]$ is the set

$$\mathcal P(g_1, \ldots, g_N) = \{ \sum_{i=1}^l s_i p_i \mid l \in \mathbb N_0, s_1,\ldots,s_l \in \Sigma[x], p_1,\ldots,p_l \in \mathcal M(g_1,\ldots,g_N) \}$$

• The ring ideal of $h_1, \ldots, h_M \in \mathbb R[x]$ is the set

$$\mathcal I(h_1, \ldots, h_M) = \{ \sum_{i=1}^M t_i h_i \mid t_1,\ldots,t_M \in \mathbb R[x] \}$$

If $p$ admits the representation $p = s_0 + \sum_{i=1}^N s_i g_i$ with $s_0, s_1, \ldots, s_N \in \Sigma[x]$, then

$$0 = -p \big(s_0 + \sum_{i=1}^N s_i g_i - p \big) = \underbrace{s_0(-p) + \sum_{i=1}^N s_i (-p)g_i}_{= f} + p^2 = f + p^2$$

with $f \in \mathcal P(-p,g_1,\ldots,g_N)$ and $p \in \mathcal M(p)$. Hence, by virtue of the Positivstellensatz, we conclude that

$$\varnothing = \{ x \in \mathbb R^n \mid p(x) \neq 0, -p(x) \geq 0, g_1(x) \geq 0, \ldots, g_N(x) \geq 0 \}$$

which is equivalent to

$$K \subseteq \{ x \in \mathbb R^n \mid p(x) \geq 0 \}$$

the desired result.

Interpretations

Overapproximation of semialgebraic set

Dissipativity in dynamical systems

Karush–Kuhn–Tucker conditions

Reverse statements

Code example

References

[Las2001]: J. B. Lasserre, ‘Global Optimization with Polynomials and the Problem of Moments’, SIAM Journal on Optimization, vol. 11, no. 3, pp. 796–817, 2001.

[Ste1974]: G. Stengle, ‘A Nullstellensatz and a Positivstellensatz in Semialgebraic Geometry’, Mathematische Annalen, vol. 207, no. 2, pp. 87–97, 1974, doi: 10.1007/BF01362149.

[JFT+2003]: Z. Jarvis-Wloszek, R. Feeley, W. Tan, K. Sun, and A. Packard, ‘Some Controls Applications of Sum of Squares Programming’, in Proceedings of the IEEE Conference on Decision and Control, Maui, US-HI, 2003, pp. 4676–4681. doi: 10.1109/CDC.2003.1272309.

[Sch2005]: M. Schweighofer, ‘Optimization of Polynomials on Compact Semialgebraic Sets’, SIAM J. Optim., vol. 15, no. 3, pp. 805–825, 2005, doi: 10.1137/S1052623403431779.

[Tan2006]: W. Tan, ‘Nonlinear Control Analysis and Synthesis using Sum-of-Squares Programming’, University of California, Berkeley, Berkeley, US-CA, 2006.