---
abstract: 'We describe algebraic certificates of positivity for functions belonging to a finitely generated algebra of Borel measurable functions, with particular emphasis to algebras generated by semi-algebraic functions.  In which case the standard global optimization problem with constraints given by elements of the same algebra is reduced via a natural change of variables to the better understood case of polynomial optimization.  A collection of simple examples and numerical experiments complement the theoretical parts of the article.' 
address:
- |
    LAAS-CNRS and Institute of Mathematics\
    University of Toulouse, France
- |
     Department of Mathematics\
    University of California at Santa Barbara\
    Santa Barbara, California\
    93106-3080
author:
- 'Jean B. Lasserre'
- Mihai Putinar
title: 'Positivity and optimization for semi-algebraic functions'
---

[^1]

[^2]

Introduction
============

Key sums of squares representation results from real algebraic geometry have been successfully applied during the last decade to polynomial optimization.  Indeed, for instance, by combining such results with semidefinite programing (a powerful tool of convex optimization), one may approximate as closely as desired (or sometimes compute exactly) the global minimum of a polynomial over a compact basic semi-algebraic set.  Several other extensions have also been proposed for finding real zeros of polynomials equations, minimizing a rational function, and solving the [*generalized problem of moments*]{} with polynomial data.  For more details on this so-called [*moment-sos*]{} approach the interested reader is referred to e.g. [@lasserrebook] and the many references therein. 

Even though questions involving polynomial data represent a sufficiently large framework, one may wonder whether this approach can be extended to a more general class of problems that involve some larger algebra than the polynomial ring.  Typical examples are algebras generated by the polynomials and some elementary functions like the absolute value, trigonometric polynomials, exponentials, splines or discontinuous step functions. 

To mention only one classical source of such natural generalizations we invoke the original works of Tchebysheff and Markov concerning the limiting values of integrals of specific measures with a finite number of prescribed moments against non-polynomial functions.  A variety of remarkable results: first on the theoretical side [@Krein; @KN], then in statistics [@Isii1; @Isii2; @KS1; @KS2], numerical integration [@BP] and not last in the theory of best approximation [@Z; @KS2] have resulted from Tchebysheff-Markov work.  All these researches, plus quite recent contingent works, such as wavelet decomposition of functions, involve non-polynomial moment problems.  In this respect, our essay provides an algebraic analysis of positivity in the “pre-dual’ of concrete distribution/measure spaces.  The importance of non-polynomial solutions to classical problems in the polynomial algebra, such as Hilbert’s 17-th Problem, was early recognized, see for instance [@Delzell1; @Delzell2] and also [@BCR]. 

[**Contribution.**]{}  The purpose of this paper is to povide a first step in the understanding of Positivestellensätze in algebras generated by non-polynomials functions, and to provide a robust relaxation method for the numerical verification of the constrained positivity of such functions as well as for optimization purposes. 

\(a) First we consider the case of an algebra ${\mathcal{A}}$ of functions generated by a finite family of functions that contains the polynomials.  In this context we prove a Positivstellensatz for a function positive on a compact set ${\mathbf{K}}\subset{\mathbb{R}}^n$ defined by finitely many inequality constraints involving functions of this algebra.  When ${\mathcal{A}}$ is the polynomial ring the set ${\mathbf{K}}$ is a basic semi-algebraic set and one retrieves a Positivstellensatz due the second author [@Put]. 

\(b) Further on we consider a slightly different framework.  The algebra ${\mathcal{A}}$ now consists of functions generated by basic monadic and dyadic relations on polynomials.  The monadic operations are $\vert\cdot\vert$ and $(\cdot)^{1/p}$, $p=1,2,\ldots$, while the dyadic operations are $(+,\times,/,\wedge,\vee)$. Notice that this algebra contains highly nonlinear and nondifferentiable functions!  We then show that this algebra is a subclass of semi-algebraic functions and every element of ${\mathcal{A}}$ has the very nice property that it has a [*lifted basic semi-algebraic representation*]{}.  As in (a) we provide an extension to this algebra of the Positivstellensatz due the second author for polynomials [@Put]. 

\(c) Finally, in both cases (a) and (b) we also provide a converging hierarchy of semidefinite relaxations for optimization.  Actually, the original problem in the algebra reduces to an equivalent [*polynomial*]{} optimization problem in a lifted space.  The dimension of the lifting (i.e. the number of additional variables) is directly related to the number of elementary operations on polynomials needed to define the functions in the description of the original problem.  Moreover, the resulting polynomial optimization problem exhibits a natural sparsity pattern with respect to the lifted variables for which the important [*running intersection property*]{} holds true.  Therefore, if on the one hand one has to handle additional variables, on the other hand this increase in dimension is partly compensated by this sparsity patterns that permits to apply the sparse semidefinite relaxations defined in [@Waki] and whose convergence was proved in [@lasserresparse].  To the best of our knowledge, the present article outlines a first systematic generalization of the moment-sos approach initiated in [@Lasserre0; @Lasserre1; @Parrilo] for polynomial optimization to algebras of non-polynomial functions and to (global) semi-algebraic optimization.\
[*Acknowledgement.*]{}  The authors thank Tim Netzer and Murray Marshall for a careful reading of the article and for their constructive comments.\

Preliminaries and main result
=============================

Although a more general abstract measure space or probability space framework is very natural for the main results of the present article, due to the optimization theory applications, we confine ourselves to an algebra of Borel measurable functions defined on a set of the Euclidean space. 

We start by recalling a few standard definitions from real algebra, [@PD].  Specifically, let $X \subset {\mathbb{R}}^d$ be a Borel measurable set and let ${\mathcal{A}}$ be a unital algebra of real valued Borel measurable functions defined on $X$. We denote by $\Sigma {\mathcal{A}}^2$ the convex cone of squares of elements of ${\mathcal{A}}$. A [*quadratic module*]{} $Q \subset {\mathcal{A}}$ is a convex cone containing $1$, such that $$(\Sigma {\mathcal{A}}^2) \cdot Q \subset Q.$$ In practice we deal with [*finitely generated quadratic modules*]{}, of the form $$Q = \Sigma {\mathcal{A}}^2 + \Sigma {\mathcal{A}}^2 \cdot h_1 + ...+ \Sigma {\mathcal{A}}^2 \cdot h_m,$$ where $h_1,...,h_m \in {\mathcal{A}}$. The [*positivity set*]{} of a quadratic module $Q$ is by definition $$P(Q) = \{ x \in X\,:\: f(x) \geq 0, \ \forall f \in Q \}.$$

Similarly to complex algebraic geometry, the duality between a quadratic module and its positivity set lies at the heart of real algebraic geometry [@BCR; @PD].  An useful tool for implementing this duality is provided by the abstract moment problem on the algebra ${\mathcal{A}}$, from where we import a simple definition: we say that the quadratic module $Q \subset {\mathcal{A}}$ possesses the [*moment property*]{} if every linear functional $L \in {\mathcal{A}}'$ which is non-negative on $Q$ is represented by a positive Borel measure $\mu$ supported by $P(Q)$.

Also, for duality type arguments, we recall the following concept: an element $f$ of a convex cone $C \subset {\mathcal{A}}$ lies in the [*algebraic interior*]{} of $C$, if for every $h \in {\mathcal{A}}$ there exists $\epsilon>0$ with the property $f + t h \in C$ for all $t, 0 \leq t <\epsilon$.

The starting point of all representation theorems below is the following simple but crucial observation.  Unless otherwise stated, all measurable functions and sets below are meant to be Borel mesurable. 

Let ${\mathcal{A}}$ be a unital algebra of measurable functions defined on the measurable subset $X \subset {\mathbb{R}}^d$. Let $Q \subset {\mathcal{A}}$ be a quadratic module with an algebraic interior point and possessing the moment property. 

If a function $f \in {\mathcal{A}}$ is positive on $P(Q)$, then $f \in Q$.

Assume by contradiction that $f \notin Q$, and let $\xi$ be an interior point of $Q$. By the separation theorem for convex sets, see [@Ko], or for a historical perspective [@Kakutani; @KR], there exists a linear functional $L \in {\mathcal{A}}$ satisfying $$L(f) \leq 0 \leq L(h), \ \ h \in Q, \ \ L(\xi)>0.$$ By assumption there exists a positive Borel measure $\mu$, such that $$L(a) = \int_{P(Q)}  d\mu, \ \  a \in {\mathcal{A}}.$$ Since $L(\xi) >0$ we infer that the measure $\mu$ is non-zero.  On the other hand, $f|_{P(Q)} >0$ and $L(p) \leq 0$, a contradiction. 

The converse is also notable:

Assume $X$ compact and ${\mathcal{A}}\subset C(X)$ is a subalgebra of continuous functions which separates the points of $X$. Let $Q \subset {\mathcal{A}}$ be a quadratic module with the constant function $1$ in its algebraic interior and suppose that every $f \in {\mathcal{A}}$ which is positive on $P(Q)$ belongs to $Q$. Then $Q$ has the moment property. 

Let $L \in {\mathcal{A}}'$ be a linear functional satisfying $L|_Q \geq 0, \ L(1) >0$. Due to the compactness assumption all continuous functions are comparable to the constant function $\xi =1$ in the following precise sense: for every $F \in C(X)$, there is a positive constant $C$ with the property $ -C \xi({\mathbf{x}}) \leq F({\mathbf{x}}) \leq  C \xi({\mathbf{x}})$. Then Marcel Riesz extension theorem [@MRiesz] provides a linear functional $\Lambda \in C(X)'$ which extends $L.$ Hence $\Lambda$ is represented by a signed measure $\mu$; since the algebra ${\mathcal{A}}$ is dense in $C(X)$ by Stone-Weierstrass theorem, and $\Lambda(a^2) \geq 0$ for all $a\in {\mathcal{A}}$, we infer that $\mu$ is a positive measure. 

In addition, we know by assumption that for every point $x \notin P(Q)$ there exists $h \in Q$ such that $h(x)<0$ and $h|_{P(Q)} \geq 0$. Hence $$\int_X h a^2 d\mu \geq 0, \ \ \ a \in A.$$ Again Stone -Weierstrass Theorem implies that $x \notin {\rm supp}(\mu)$, that is the representing measure $\mu$ is supported by the closed set $P(Q)$.

Thus the main questions we are faced with at this first stage of inquiry are: under which conditions a quadratic module $Q$ has an interior point and/or possesses the moment property.  While the first question has a simple solution, having to do with the boundedness of the positivity set $P(Q)$, the second one involves solving an abstract moment problem, it is more delicate, but on the other hand has a long and glorious past, with a wealth of partial results and side remarks [@KN; @KS1; @KS2]. 

Towards finding solutions to the above two questions we consider only a finitely generated algebra $ {\mathcal{A}}= {\mathbb{R}}[h_1,...,h_n]$, where $h=(h_1,...,h_n)$ is an n-tuple of measurable functions on the set $X \subset {\mathbb{R}}^d$. Let ${\mathbf{y}}=(y_1,...,y_n)$ be variables, so that, by noetherianity $${\mathcal{A}}\cong {\mathbb{R}}[{\mathbf{y}}]/I,$$ where $I$ is a finitely generated ideal of ${\mathbb{R}}[{\mathbf{y}}]$. The ideal $I$ describes all the algebraic relations between generators of the algebra.  This ideal is in addition [*radical*]{}, in the following sense: if $p_1^2 +...+ p_k^2 \in I$, where $p_1,...,p_k \in {\mathbb{R}}[{\mathbf{y}}]$, then $p_1,...,p_k \in I$, [@BCR].  Indeed, if $p_1(h)^2 +...+ p_k(h)^2 =0$ as functions defined on $X$, then $p_1 \circ h=0, ..., p_k \circ h =0$ in the algebra ${\mathcal{A}}$. Denote by “$\circ$” the usual composition of functions, i.e., with $g:{\mathbb{R}}^n\to{\mathbb{R}}$ and $f:{\mathbb{R}}\to{\mathbb{R}}$, ${\mathbf{x}}\mapsto (f\circ g)({\mathbf{x}}):=f(g({\mathbf{x}}))$.

Assume that $ {\mathcal{A}}= {\mathbb{R}}[h_1,...,h_n]$ is a finitely generated algebra of measurable functions and let $Q \subset {\mathcal{A}}$ be a quadratic module.  If $1-(h_1^2 +...+h_n^2) \in Q$, then the constant function $1$ belongs to the algebraic interior of $Q$.

For a simple algebraic proof we refer to [@PD].  Already a first approximative solution to the moment problem associated to $Q$ is available. 

Let $ {\mathcal{A}}= {\mathbb{R}}[h_1,...,h_n]$ be an algebra of measurable functions defined on the set $X \subset {\mathbb{R}}^d$ and let $L \in {\mathcal{A}}'$ be a linear functional which is non-negative on the quadratic module $\Sigma {\mathcal{A}}^2 + (1-(h_1^2 +...+h_n^2) )\Sigma {\mathcal{A}}^2$. Then there exists a positive measure $\nu$, supported by the unit ball in ${\mathbb{R}}^n$, with the property $$L(p(h_1,...,h_n)) = \int_{\| {\mathbf{y}}\| \leq 1} p({\mathbf{y}}) d\nu({\mathbf{y}}), \ \  p \in {\mathbb{R}}[{\mathbf{y}}].$$

The familiar Gelfand-Naimark-Segal construction can be invoked at this moment.  In short, define an inner product on the polynomial algebra ${\mathbb{R}}[{\mathbf{y}}]$ by $$\langle p, q \rangle = L( p(h) q(h)), \ \ p,q \in {\mathbb{R}}[y].$$ Denote by $J$ the set of null-vectors $ p \in J$ if and only if $\langle p, p \rangle = 0.$ It is an ideal of ${\mathbb{R}}[{\mathbf{y}}]$ by Cauchy-Schwarz inequality.  The quotient space ${\mathbb{R}}[{\mathbf{y}}]/J$ is endowed then with a non-degenerate inner product structure.  Let $H$ be its Hilbert space completion.  The multiplication operators with the variables $M_i p ({\mathbf{y}}) = y_i p({\mathbf{y}})$ are self-adjoint and bounded, due to the positivity assumption imposed on $L$: $$\langle M_i  p , M_i p \rangle = L( h_i^2 p(h)^2) \leq L(p(h)^2) = \langle p, p \rangle.$$ In addition, the operators $M_i$ mutually commute on the Hilbert space $H$. Thus the spectral theorem gives a positive Borel measure $\nu$, with the property $$L(p(h)) = \langle p, 1 \rangle = \langle p(M_1,...,M_n)1, 1 \rangle = \int p d\nu, \ \ p \in {\mathbb{R}}[{\mathbf{y}}].$$ In addition, the support of the measure $\nu$ is contained in the unit ball, as a consequence of the spherical contraction assumption $M_1^\ast M_1 +...+M_n^\ast M_n \leq I.$

Thus, a quadratic module $Q \subset {\mathcal{A}}= {\mathbb{R}}[h_1,...,h_n]$ with $(1-(h_1^2 +...+h_n^2) )\in Q$ satisfies the moment property if the measure $\nu$ appearing in the above proposition is the push-forward via the map $h : X \longrightarrow {\mathbb{R}}^d$ of a positive measure $\mu$ supported by $P(Q)$, that is: $$\int_{\| {\mathbf{y}}\| \leq 1} p({\mathbf{y}}) d\nu({\mathbf{y}}) =\,\int_{P(Q)} p(h({\mathbf{x}})) d\mu({\mathbf{x}}), \ \  p \in {\mathbb{R}}[{\mathbf{y}}]\,.$$ A series of sufficient conditions assuring $\nu = h_\ast \mu$ in the above sense are discussed next. 

Again for ${\mathcal{A}}= {\mathbb{R}}[h_1,...,h_n]$ consider a finitely generated quadratic module $Q = \Sigma {\mathcal{A}}^2 + g_0(h) \Sigma {\mathcal{A}}^2+ g_1(h) \Sigma {\mathcal{A}}^2+...+ g_m(h) \Sigma {\mathcal{A}}^2$, where $g_0,...,g_m \in {\mathbb{R}}[{\mathbf{y}}]$ and $g_0({\mathbf{y}}) = 1-y_1^2-...-y_n^2.$ Let also the radical ideal $I = (p_1({\mathbf{y}}),...,p_k({\mathbf{y}}))$. Then $$\tilde{Q} = \Sigma {\mathbb{R}}[{\mathbf{y}}]^2 + g_0({\mathbf{y}}) \Sigma {\mathbb{R}}[{\mathbf{y}}]^2  + ...+ g_m({\mathbf{y}}) \Sigma {\mathbb{R}}[{\mathbf{y}}]^2 
\pm p_1  \Sigma {\mathbb{R}}[{\mathbf{y}}]^2 \pm ...\pm p_k  \Sigma {\mathbb{R}}[{\mathbf{y}}]^2$$ is a quadratic module in the polynomial algebra ${\mathbb{R}}[{\mathbf{y}}]$. Its positivity set $P(\tilde{Q})$ is contained in the closed unit ball intersection with the zero set $V(I)$ of the ideal $I$. Note that we have a natural pull-back (substitution) map $$h^\ast : {\mathbb{R}}[{\mathbf{y}}] \longrightarrow {\mathcal{A}}, \ \ h^\ast (p) = p\circ h, \ \ p \in {\mathbb{R}}[{\mathbf{y}}],$$ and $h^\ast(\tilde{Q}) = Q$. At the level of positivity sets we obtain $$h (P(Q)) \subset P(\tilde{Q}),$$ but the inclusion might be strict.  Indeed, we derive the following direct observation. 

With the above notation, assume that $f = p\circ h \in Q$, where $p \in {\mathbb{R}}[{\mathbf{y}}]$. Then $p$ is non-negative on $P(\tilde{Q})$.

The assumption $f \in Q$ amounts to the algebraic identity $$f\circ h = \sigma\circ h + (g_0\circ h)\,( \sigma_0\circ h)  + \cdots+ (g_m\circ h )\,(\sigma_m\circ h),$$ where $\sigma, \sigma_0,...,\sigma_m \in \Sigma {\mathbb{R}}[{\mathbf{y}}]^2.$ In its turn, this identity becomes $$f({\mathbf{y}}) =  \sigma({\mathbf{y}}) + g_0({\mathbf{y}}) \sigma_0({\mathbf{y}})  + ...+ g_m({\mathbf{y}}) \sigma_m({\mathbf{y}}) + r({\mathbf{y}}),$$ where $r \in I$. By evaluating at a point ${\mathbf{a}}\in P(\tilde{Q}) \subset V(I)$ we infer $$f({\mathbf{a}}) =  \sigma({\mathbf{a}}) + g_0({\mathbf{a}}) \sigma_0({\mathbf{a}})  + ...+ g_m({\mathbf{a}}) \sigma_m({\mathbf{a}}) \geq 0.$$

We will see in the next section simple examples showing that the positivity of a function $f$ on $P(Q)$ does not guarantee in general a decomposition of the form $f \in Q$. The gap between the two statements is explained in the following general result. 

\[thmain\] Let ${\mathcal{A}}= {\mathbb{R}}[h_1,...,h_n]$ be a finitely generated algebra of measurable functions defined on a measurable set $X \subset {\mathbb{R}}^d$ and let $Q$ be a quadratic module with the function $1$ in its algebraic interior.  Assume that $f \in {\mathcal{A}}$ is positive on $P(Q)$. Then $f \in \hat{Q}$, where $\hat{Q}$ is the pullback by the map $h : X \longrightarrow {\mathbb{R}}^d$ of a quadratic module which serves as a positivity certificate for the set $h(P(Q))$.

Of course the choice of $\hat{Q}$ is not unique, and it may not be a finitely generated quadratic module.  For instance, as a first rough approximation, one can choose $$Q' = \{ p\circ h; \ p|_{h(X) \cap P(\tilde{Q})} \geq 0 \},$$ where $\tilde{Q}$ is the pull-back of $Q$ via the projection map $\pi : {\mathbb{R}}[{\mathbf{y}}] \longrightarrow {\mathcal{A}}.$

\[coro1\]Assume, in the conditions of Theorem \[thmain\], that the set $h(X)$ is closed in ${\mathbb{R}}[y]$. Choose an at most countable set of polynomials $v_i \in {\mathbb{R}}[{\mathbf{y}}], \ i \in J, \ | J | \leq \infty,$ with the property $$\{ {\mathbf{y}}\in {\mathbb{R}}^n\,: \ v_i({\mathbf{y}}) \geq 0, \ i \in J \} = h(X) \cap P(\tilde{Q}).$$ Then every element $f\circ h \in {\mathcal{A}}$ which is positive on the set $P(Q)$ can be written as $$f\circ h = \sigma \circ h + (M- h_1^2-...-h_n^2)\,(\sigma_0\circ h)  + 
\sum_{i \in J_0} (v_i\circ h) (\sigma_i\circ h),$$ where $M>0$, the subset $J_0 \subset J$ is finite and $\sigma, \sigma_0, \sigma_i \in \Sigma {\mathbb{R}}[{\mathbf{y}}]^2,
\ i \in J_0.$

The remaining of this section is concerned with particular choices of the “saturation” process $Q \mapsto \hat{Q}$ and the resulting effective sums of squares representations. 

Examples in algebras of semi-algebraic functions
------------------------------------------------

Let $X={\mathbb{R}}^n$ and let ${\mathcal{A}}= {\mathbb{R}}[{\mathbf{x}},h_1({\mathbf{x}}), ..., h_t({\mathbf{x}})]$ for some functions $h_i:{\mathbb{R}}^n\to{\mathbb{R}}$, $i=1,\ldots,t$. Consider the set ${\mathbf{K}}\subset{\mathbb{R}}^n$ defined by: $$\label{setk}
{\mathbf{K}}\,:=\,\{{\mathbf{x}}\in{\mathbb{R}}^n\::\: g_j({\mathbf{x}},h_1({\mathbf{x}}),\ldots,h_t({\mathbf{x}}))\geq 0,\:j=1,\ldots,m\},$$ and suppose that ${\mathbf{K}}$ is compact and $${\mathbf{x}}\mapsto M-\Vert {\mathbf{x}}\Vert^2-\sum_{i=1}^t \vert h_i({\mathbf{x}})\vert^2\,>0\,\quad\mbox{on }{\mathbf{K}}.$$

\[ex1\] Here $h_i({\mathbf{x}})=\vert x_i\vert$, $i=1,\ldots,n$ (so let $\vert{\mathbf{x}}\vert=(\vert x_i\vert)$. In this case ${\mathbf{y}}=(y_1,\ldots,y_{2n})$ and one has the algebraic relation $y^2_{n+i}=y^2_i$, $i=1,\ldots,n$, between the generators, hence ${\mathcal{A}}\cong {\mathbb{R}}[{\mathbf{y}}]/I$, with $I:=\langle y^2_{n+1}-y^2_1,\ldots,y^2_{2n}-y^2_{n}\rangle$. Let’s choose the quadratic module with the constant $1$ in its algebraic interior: $$\begin{aligned}
Q &=& \Sigma {\mathcal{A}}^2 
+ (M-(\sum_{i=1}^nx_i^2 +|x_i|^2))\Sigma {\mathcal{A}}^2  +\sum_{j=1}^m\Sigma {\mathcal{A}}^2 g_j({\mathbf{x}},\vert{\mathbf{x}}\vert)\\
&=&  \Sigma {\mathcal{A}}^2 + (M-2\Vert{\mathbf{x}}\Vert^2) \Sigma {\mathcal{A}}^2+\sum_{j=1}^m\Sigma {\mathcal{A}}^2 g_j({\mathbf{x}},\vert{\mathbf{x}}\vert)\end{aligned}$$ The lifted quadratic module is $$\tilde{Q} = \Sigma {\mathbb{R}}[{\mathbf{y}}]^2 + (M-\Vert{\mathbf{y}}\Vert^2) \Sigma {\mathbb{R}}[{\mathbf{y}}]^2+
\sum_{j=1}^m\Sigma {\mathbb{R}}[{\mathbf{y}}]2 g_j({\mathbf{y}}),$$ whose positivity support set is the set $$\{{\mathbf{y}}\in{\mathbb{R}}^{2n}\::\:M-\Vert{\mathbf{y}}\Vert^2\geq 0;\quad g_j({\mathbf{y}})\geq0,\:j=1\ldots,m\}.$$ On the other hand, $ P(Q)$ lives in ${\mathbf{K}}\subset{\mathbb{R}}^n$. For instance if ${\mathbf{K}}=[-1,1]^n$ and $t=n$ with $g_j({\mathbf{x}})=1-x_j^2$, $j=1,\ldots,t$, a function such as $|x_1|^3 + 1/2$ belongs to the algebra ${\mathcal{A}}$, is positive on $P(Q)$, but it cannot be written as $$|x_1|^3 + 1/2 = \sigma ({\mathbf{x}},|{\mathbf{x}}|) + (2n-2\Vert{\mathbf{x}}\Vert^2)\sigma_0({\mathbf{x}},|{\mathbf{x}}|)
+\sum_{j=1}^n\sigma_j({\mathbf{x}},\vert{\mathbf{x}}\vert)g_j({\mathbf{x}}),$$ with $\sigma, \sigma_j\in \Sigma {\mathbb{R}}[{\mathbf{y}}]^2$. Indeed, such a representation would lift to $$y_{n+1}^3 + 1/2 = \sigma ({\mathbf{y}}) + (2n-\Vert {\mathbf{y}}\Vert^2)\sigma_0({\mathbf{y}})+
\sum_{j=1}^n\sigma_j({\mathbf{y}})g_j({\mathbf{y}}),$$ and this is obviously impossible by choosing for example $y_i=0$ for all $i\neq n+1$ and $y_{n+1}=-1$.

In order to obtain the correct representation we invoke the main result of the previous section, and first consider the image set $$h(X)\,=\,\{ ({\mathbf{x}},|{\mathbf{x}}|); \ {\mathbf{x}}\in {\mathbb{R}}^n \} \subset {\mathbb{R}}^{2n}.$$ This set can be exactly described by the inequalities $$y_{n+i}^2 - y_i^2 \geq 0, \ y_{n+i}^2 - y_i^2 \geq 0, \ y_{n+i} \geq 0;\quad i=1,\ldots,n.$$ Therefore, $$\begin{aligned}
h(X)\cap P(\tilde{Q})\,=\,\{{\mathbf{y}}\in{\mathbb{R}}^{2n}&:&2n-\Vert {\mathbf{y}}\Vert^2\geq 0;\:g_j({\mathbf{x}})\geq0,\:j=1,\ldots,t;\\
&&y_{n+i}^2-y_i^2=0,\:y_{n+i}\geq0,\:i=1,\ldots, n\},\end{aligned}$$ and by Corollary \[coro1\], the quadratic module in ${\mathbb{R}}[{\mathbf{y}}]$ generated by the polynomials that describe the above semi-algebraic set $h(X)\cap P(\tilde{Q})$, provide the desired certificate of positivity.  And so we have:

Let ${\mathbf{K}}$ be as in (\[setk\]).  An element $f$ of the algebra ${\mathbb{R}}[{\mathbf{x}},|{\mathbf{x}}|]$ which is positive on ${\mathbf{K}}$ can be written as $$\begin{aligned}
 {\mathbf{x}}\mapsto f({\mathbf{x}},\vert {\mathbf{x}}\vert) &=&\sigma({\mathbf{x}},|{\mathbf{x}}|) + (n-\Vert{\mathbf{x}}\Vert^2)\sigma_0({\mathbf{x}},|{\mathbf{x}}|) \\
&&+ \sum_{i=1}^n\vert x_i\vert \, \sigma_i({\mathbf{x}},|{\mathbf{x}}|)
+\sum_{j=1}^tg_j({\mathbf{x}},\vert{\mathbf{x}}\vert) \, \psi_j({\mathbf{x}},|{\mathbf{x}}|)\end{aligned}$$ where $\sigma, \sigma_i, \psi_j \in \Sigma {\mathbb{R}}[{\mathbf{y}}]^2$.

\[ex2\] Given two polynomials $p,q\in{\mathbb{R}}[{\mathbf{x}}]$, let ${\mathcal{A}}:={\mathbb{R}}[{\mathbf{x}},p({\mathbf{x}})\vee q({\mathbf{x}})]$ where $a\vee b:=\max[a,b]$, and let ${\mathbf{K}}$ be as in (\[setk\]) with $t=1$ and $h_1=p({\mathbf{x}})\vee q({\mathbf{x}})$. Recall that $2 (a\vee b)=\vert a-b\vert+(a+b)$, and so one may consider the new algebra ${\mathcal{A}}'={\mathbb{R}}[{\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert]$ since a polynomial in the variables ${\mathbf{x}}$ and $p({\mathbf{x}})\vee q({\mathbf{x}})]$ is a particular polynomial in ${\mathbf{x}}$ and $\vert p({\mathbf{x}})-q({\mathbf{x}})\vert$. In this case ${\mathbf{y}}=(y_1,\ldots,y_{n+1})$ and one has the algebraic dependency $$y_{n+1}^2\,=\,(p({\mathbf{x}})-q({\mathbf{x}})) ^2$$ and the additional constraint $y_{n+1}\geq0$.

Let ${\mathbf{K}}$ be as in (\[setk\]) and let $f$ be an element of the algebra $\mathcal{A}:={\mathbb{R}}[{\mathbf{x}},p({\mathbf{x}})\vee q({\mathbf{x}})]]$ which is positive on ${\mathbf{K}}$. Equivalently $${\mathbf{x}}\mapsto f({\mathbf{x}},p({\mathbf{x}})\vee q({\mathbf{x}})])\,=\,\tilde{f}({\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert),$$ for some $\tilde{f}\in\mathcal{A}':={\mathbb{R}}[{\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert]$, positive on ${\mathbf{K}}$. Then $\tilde{f}$ can be written $$\begin{aligned}
\tilde{f}({\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert)&=&\sigma({\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert)\\
&&+(M-\Vert {\mathbf{x}}\Vert^2-\vert p({\mathbf{x}})-q({\mathbf{x}})\vert^2)\sigma_0({\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert)\\
&& + \vert p({\mathbf{x}})-q({\mathbf{x}})\vert \sigma_1({\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert)\\
&& + \sum_{j=1}^m\psi_j({\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert)g_j({\mathbf{x}},\vert p({\mathbf{x}})-q({\mathbf{x}})\vert)\end{aligned}$$ where $\sigma, \sigma_i, \psi_j \in \Sigma {\mathbb{R}}[y_1,\ldots,y_{n+1}]^2$.

Of course a similar thing can be done with $p({\mathbf{x}})\wedge q({\mathbf{x}}):=\min[p({\mathbf{x}}),q({\mathbf{x}})]$ using $2(a\wedge b)=(a+b)-\vert a-b\vert$.

\[ex3\] Let ${\mathbf{u}}=(u_i)_{i=1}^n\in{\mathbb{R}}[{\mathbf{x}}]^n$ and let $f$ be an element of the algebra $\mathcal{A}:={\mathbb{R}}[{\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p]]$ which is positive on ${\mathbf{K}}$, where $\Vert {\mathbf{x}}\Vert_p=(\sum_{i=1}^n\vert x_i\vert^p)^{1/p}$, with either $p\in{\mathbb{N}}$ or $p^{-1}\in{\mathbb{N}}$.

If $p/2\in{\mathbb{N}}$ one uses the algebraic lifting ${\mathbf{y}}\in{\mathbb{R}}^{n+1}$ with: $$y_{n+1}^p=\sum_{i=1}^nu_i({\mathbf{x}})^p;\quad  y_{n+1}\geq 0.$$ If $p=2q+1$ with $q\in{\mathbb{N}}$, one uses the algebraic lifting ${\mathbf{y}}\in{\mathbb{R}}^{2n+1}$, with: $$y_{n+i}^2=u_i({\mathbf{x}})^2;\quad y_{2n+1}^p=\sum_{i=1}^ny_{n+i}^p;\quad y_{n+i}\geq 0,
\:i=1,\ldots,n+1.$$ If $1/p\in{\mathbb{N}}$ one uses the algebraic lifting: $$y_{n+i}^{2/p}=u_i({\mathbf{x}})^2;\quad y_{2n+1}=\left(\sum_{i=1}^ny_{n+i}\right)^{1/p};\quad y_{n+i}\geq 0,\:i=1,\ldots,n+1.$$

Let ${\mathbf{K}}$ be as in (\[setk\]) and let $f$ be an element of the algebra $\mathcal{A}:={\mathbb{R}}[{\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p]$ which is positive on ${\mathbf{K}}$.

[(a)]{} If $p/2\in{\mathbb{N}}$ then $f$ can be written $$\begin{aligned}
f({\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)&=&\sigma({\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&&+(M-\Vert {\mathbf{x}}\Vert^2-\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p^2)\,\sigma_0({\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&& + \Vert {\mathbf{u}}({\mathbf{x}})\Vert_p\,\sigma_1({\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p) + \sum_{j=1}^mg_j({\mathbf{x}})\,\psi_j({\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\end{aligned}$$ where $\sigma, \sigma_i, \psi_j \in \Sigma {\mathbb{R}}[y_1,\ldots,y_{n+1}]^2$.

[(b)]{} If $p=2q+1$ with $q\in{\mathbb{N}}$ then $f$ can be written $$\begin{aligned}
f({\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)&=&\sigma({\mathbf{x}},\vert {\mathbf{u}}(x)\vert,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&&+(M-\Vert {\mathbf{x}}\Vert^2-\Vert {\mathbf{u}}({\mathbf{x}})\Vert^2-\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p^2)\,\sigma_0({\mathbf{x}},\vert {\mathbf{u}}({\mathbf{x}})\vert,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&& + \sum_{i=1}^n\vert u_i({\mathbf{x}})\vert\,\sigma_i({\mathbf{x}},\vert {\mathbf{u}}({\mathbf{x}})\vert,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&&+ \Vert {\mathbf{u}}({\mathbf{x}})\Vert_p\,{\varphi}({\mathbf{x}},\vert {\mathbf{u}}({\mathbf{x}})\vert,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&& + \sum_{j=1}^mg_j({\mathbf{x}})\,\psi_j({\mathbf{x}},\vert {\mathbf{u}}({\mathbf{x}})\vert,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\end{aligned}$$ where $\sigma, \sigma_i, \psi_j,{\varphi}\in \Sigma {\mathbb{R}}[y_1,\ldots,y_{2n+1}]^2$.

[(c)]{} If $1<p^{-1}\in{\mathbb{N}}$ then $f$ can be written $$\begin{aligned}
f({\mathbf{x}},\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)&=&
\sigma({\mathbf{x}},\vert u_1(x)\vert^p,\ldots,\vert u_n(x)\vert^p,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&&+(M-\Vert {\mathbf{x}}\Vert^2-\sum_{i=1}^n\vert u_i({\mathbf{x}})\vert^{2p}-\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p^2)\\
&&\times\sigma_0({\mathbf{x}},\vert u_1(x)\vert^p,\ldots,\vert u_n(x)\vert^p,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&& + \sum_{i=1}^n\vert u_i({\mathbf{x}})\vert^p\,
\sigma_i({\mathbf{x}},\vert u_1(x)\vert^p,\ldots,\vert u_n(x)\vert^p,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&& + \Vert {\mathbf{u}}({\mathbf{x}})\Vert_p\,{\varphi}({\mathbf{x}},\vert u_1(x)\vert^p,\ldots,\vert u_n(x)\vert^p,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\\
&& + \sum_{j=1}^mg_j({\mathbf{x}})\,\psi_j({\mathbf{x}},\vert u_1(x)\vert^p,\ldots,\vert u_n(x)\vert^p,\Vert {\mathbf{u}}({\mathbf{x}})\Vert_p)\end{aligned}$$ where $\sigma, \sigma_i, {\varphi},\psi_j \in \Sigma {\mathbb{R}}[y_1,\ldots,y_{2n+1}]^2$.

\[exsqrt\] Let ${\mathcal{A}}= {\mathbb{R}}[{\mathbf{x}},\sqrt{p({\mathbf{x}})}]$. Of couse one here considers the new basic semi-algebraic set: $$\label{newsetk}
{\mathbf{K}}'\,:=\,{\mathbf{K}}\,\cap\,\{{\mathbf{x}}\::\:g_{m+1}({\mathbf{x}})\geq0\}\quad\mbox{with}\quad{\mathbf{x}}\mapsto g_{m+1}({\mathbf{x}}):=p({\mathbf{x}}),$$ and the lifting $$y_{n+1}^2\,=\,p({\mathbf{x}});\quad y_{n+1}\geq 0.$$

Let $f$ be an element of the algebra $\mathcal{A}:={\mathbb{R}}[{\mathbf{x}},\sqrt{p({\mathbf{x}})}]$ which is positive on ${\mathbf{K}}'$. Then $f$ can be written $$\begin{aligned}
f({\mathbf{x}},\sqrt{p({\mathbf{x}})})&=&\sigma({\mathbf{x}},\sqrt{p({\mathbf{x}})})
+(M-\Vert {\mathbf{x}}\Vert^2-p({\mathbf{x}}))\,\sigma_0({\mathbf{x}},\sqrt{p({\mathbf{x}})})\\
&& + \sum_{j=1}^{m+1}g_j({\mathbf{x}})\,\psi_j({\mathbf{x}},\sqrt{p({\mathbf{x}})}) +\sqrt{p({\mathbf{x}})}\,{\varphi}({\mathbf{x}},\sqrt{p({\mathbf{x}})})\\\end{aligned}$$ where $\sigma, \sigma_i, {\varphi},\psi_j \in \Sigma {\mathbb{R}}[y_1,\ldots,y_{n+1}]$.

Examples in algebras of nonsemi-algebraic functions
---------------------------------------------------

Let $X=[0,\pi/2]$ and ${\mathcal{A}}= {\mathbb{R}}[x,\sin x]$. Again ${\mathbf{y}}=(y_1,y_2)$ but this time the algebra ${\mathcal{A}}$ is isomorphic to the full polynomial algebra ${\mathbb{R}}[{\mathbf{y}}]$. For illustration we consider the quadratic module $Q \subset {\mathcal{A}}$ generated by the elements $x, \pi/2 -x, 1 - \sin^2 x.$ Although the inequality $ 1 - \sin^2 x \geq 0$ is redundant, it is necessary to add it for having the function $1$ in the algebraic interior of $Q$.

As we wish to obtain a certificate of positivity for a function $f(x,\sin x)$ belonging to ${\mathcal{A}}$, an algebraic description of the graph of $x\mapsto \sin x$ is in order.  Choose the polynomials $$x\mapsto p_k(x) = \sum_{j=0}^k (-1)^k \frac{x^{2k+1}}{(2k+1)!},  \qquad k \geq 0.$$ It is well known that $$p_{2k}(x) \geq p_{2k+2}(x) \geq  \sin x \geq p_{2k+1}(x) \geq p_{2k-1}(x), \quad
\forall x \in [0, \pi/2],$$ and that these polynomials converge uniformly to $\sin x$ on $[0,\pi/2]$. A description of the graph of $\sin x$ is: $$h(X)\,=\,\{ (x, \sin x)\,:\ 0 \leq x \leq \pi/2 \} =$$ $$\{ {\mathbf{y}}\in{\mathbb{R}}^2\,: \ 0 \leq y_1 \leq \pi/2 , \quad p_{2k+1}(y_1) \leq y_2 \leq p_{2k}(y_1),\quad k \geq 0\}.$$

In view of our main result, the conclusion is:

Let $f$ be an element of the algebra ${\mathbb{R}}[x,\sin x]$ and assume that $f>0$ for all $ x \in [0,\pi/2]$. Then there exists $k \geq 0$ such that $$x\mapsto f(x,\sin x) = \sigma(x,\sin x) + x \sigma_0(x,\sin x) + (\pi/2 -x) \sigma_2(x,\sin x) +$$ $$[p_{2k}(x)-\sin x]
\sigma_3(x, \sin x) + [\sin x - p_{2k+1}(x)] \sigma_4(x, \sin x),$$ where $\sigma, \sigma_i \in \Sigma {\mathbb{R}}[{\mathbf{y}}]^2.$

Let $X={\mathbb{R}}$ and ${\mathcal{A}}= {\mathbb{R}}[x, e^{ax}, e^{bx}]$. Two distinct cases, corresponding to $a,b$ commensurable or not, will be treated.  This dichotomy is well known to the experts in the control theory of delay systems. 

To fix ideas, we assume that $b>a>0$ and the base is the interval $[0,1]$. Denote $y_1 = x, y_2 = e^{ax}, y_3 = e^{bx}$. We will impose the archimedeanity constraints $$x \geq 0, 1 -x \geq 0,\ \  y_2 \geq 0, e^a - y_2 \geq 0, \ \ y_3 \geq 0, e^b -y_3 \geq 0.$$ Along with these we have to consider the polynomial approximations of the two exponentials: $$p_n(ax) = \sum_{k=0}^n \frac{a^k x^k}{k!}  \leq y_2 \leq  p_n(ax) + \frac{a^{n+1} e^a x^{n+1}}{(n+1)!}$$ and $$p_n(bx) = \sum_{k=0}^n \frac{b^k x^k}{k!}  \leq y_3 \leq  p_n(bx) + \frac{b^{n+1} e^b x^{n+1}}{(n+1)!}.$$ The reader will recognize above an upper bound of the remainder of Taylor’s series approximation of the exponential function.\
[*Case I. The frequencies $a,b$ are not commensurable.*]{}  Then there is no algebraic relation among the variables $y_1,y_2,y_3$ and a function $ f \in  {\mathbb{R}}[x, e^{ax}, e^{bx}]$ which is positive on the interval $[0,1]$ is decomposable into a weighted sum of squares generated by $x, 1-x, e^{ax}, e^a-e^{ax}, e^{bx}, e^b-e^{bx}, e^{ax} - p_n(ax),  p_n(ax) + \frac{a^{n+1} e^a x^{n+1}}{(n+1)!}-e^{ax}, e^{bx} -p_n({bx}),  p_n(bx) + \frac{b^{n+1} e^b x^{n+1}}{(n+1)!}- e^{bx},$ for a large enough $n$.

Note that the above list of weights is redundant, as for instance the constraint $e^{ax}>0$ follows from $ e^{ax} - p_n(ax)>0$, and so on.  In practice it will be important to identify a minimal set of positivity constraints.\
[*Case II.  The frequencies $a,b$ are commensurable.*]{}  Assume that $Na = Mb$ where $N,M$ are positive integers.  Then the decomposition above of a positive (on $[0,1]$) element $f \in  {\mathbb{R}}[x, e^{ax}, e^{bx}]$ holds modulo the algebraic relation $y_2^N = y_3^M$.

When dealing with trigonometric (real valued) polynomials in $n$ variables, one has to consider the algebra ${\mathcal{A}}= {\mathbb{R}}[ \sin \theta_i, \cos \theta_i], \  1 \leq i \leq n.$ The standard lifting proposed in the present article is $$y_i = \sin \theta_i, \ \  z_i = \cos \theta_i,\ \  1 \leq i \leq n,$$ modulo the ideal generated by the relations $$\label{torus}
y_i^2 + z_i^2 -1 = 0, \ \  1 \leq i \leq n.$$ Note that in this case every quadratic module $Q \subset {\mathcal{A}}$ in the variables $\sin \theta_i, \cos \theta_i$ lifts to an archimedean quadratic module $\hat{Q}$ in the variables $y_i, z_i$. Specifically, relations (\[torus\]) assure that the constant function $1$ belongs to the algebraic interior of $\hat{Q}$.

Representation of positive semi-algebraic functions
===================================================

We now consider an algebra of functions which forms an important subclass of semi-algebraic functions. 

Let $(g_j)_{j=1}^m\subset{\mathbb{R}}[{\mathbf{x}}]$ and let ${\mathbf{K}}\subset{\mathbb{R}}^n$ be the basic semi-algebraic set $$\label{setkk}
{\mathbf{K}}\,:=\,\{{\mathbf{x}}\in{\mathbb{R}}^n\::\: g_j({\mathbf{x}})\geq 0,\:j=1,\ldots,m\}.$$

Recall that $f\,:{\mathbf{K}}\to{\mathbb{R}}$ is a semi-algebraic function if its graph $\Psi_f:=\{({\mathbf{x}},f({\mathbf{x}}))\,:\,{\mathbf{x}}\in{\mathbf{K}}\}$ is a semi-algebraic set of ${\mathbb{R}}^n\times{\mathbb{R}}$.

Recall the notation $$a\vee b=\max[a,b];\quad a\wedge b:=\min [a,b];\quad\vert {\mathbf{x}}\vert =(\vert x_1\vert,\ldots,\vert x_n\vert)\in{\mathbb{R}}^n,$$ and let ${\mathcal{A}}$ be the algebra of fonctions $f\,:{\mathbf{K}}\to{\mathbb{R}}$ generated by finitely many of the dyadic operations $\{+,\times,/,\vee,\wedge\}$ and monadyc operations $\vert\cdot\vert$ and $(\cdot)^{1/p}$ ($p\in{\mathbb{N}}$) on polynomials. 

For instance, with $u,v,\ell\in{\mathbb{R}}[{\mathbf{x}}]$ and $h\in{\mathbb{R}}[{\mathbf{x}}]^2$, $q\in{\mathbb{N}}$, the function $$\label{demo}
{\mathbf{x}}\mapsto f({\mathbf{x}}):=(\vert u({\mathbf{x}})+v({\mathbf{x}})\vert ^{1/p})\wedge\left(\sqrt{\Vert h({\mathbf{x}})\Vert_{2q+1}+1/\ell({\mathbf{x}})}\right)$$ is a member of ${\mathcal{A}}$ (assuming of course that $\ell({\mathbf{x}})>0$ or $\ell({\mathbf{x}})<0$ for all ${\mathbf{x}}\in{\mathbf{K}}$). 

A function $f\in{\mathcal{A}}$ is said to have a [*basic semi-algebraic lifting*]{} (in short a “[b.s.a.l.]{}”),  or $f$ is [*basic semi-algebraic*]{} (b.s.a.)  if there exist $p,s\in{\mathbb{N}}$, polynomials $(h_k)_{k=1}^s\subset{\mathbb{R}}[{\mathbf{x}},y_1,\ldots,y_p]$ and a basic semi-algebraic set $${\mathbf{K}}'_f:=\{({\mathbf{x}},{\mathbf{y}})\in{\mathbb{R}}^{n+p}\::\: {\mathbf{x}}\in{\mathbf{K}};\:h_k({\mathbf{x}},{\mathbf{y}})\geq0,\quad k=1,\ldots,s\}$$ such that the graph of $f$ (denoted $\Psi_f$) satisfies: $$\Psi_f:=\{({\mathbf{x}},f({\mathbf{x}}))\::\:{\mathbf{x}}\in{\mathbf{K}}\}\,=\,\{({\mathbf{x}},y_p)\::\:({\mathbf{x}},{\mathbf{y}})\in{\mathbf{K}}'_f\}.$$ In other words, $\Psi_f$ is an orthogonal projection of the basic semi-algebraic set ${\mathbf{K}}'_f$ which lives in the lifted space ${\mathbb{R}}^{n+p}$.

Hence by the projection theorem of real algebraic geometry, a function $f\in{\mathcal{A}}$ that admits a [b.s.a.l.]{}   is semi-algebraic. 

\[sal\] Let ${\mathbf{K}}$ be the basic semi-algebraic set in (\[setk\]).  Then every well-defined $f\in{\mathcal{A}}$ has a basic semi-algebraic lifting. 

It is obvious that the sum $f+g$ and multiplication $fg$ of two b.s.a.  functions $f,g\in{\mathcal{A}}$, is b.s.a.  So let $f\in{\mathcal{A}}$ be b.s.a.,  i.e., $$\Psi_f=\{({\mathbf{x}},y_p)\::\:({\mathbf{x}},{\mathbf{y}})\in{\mathbf{K}}'_f\subset{\mathbb{R}}^{n+p}\}$$ for some integer $p$ and some basic semi-algebraic set ${\mathbf{K}}'_f$. Then:

-   If $f\neq 0$ on ${\mathbf{K}}$ then $f^{-1}$ has the [b.s.a.l.]{}$$\Psi_{f^{-1}}=\{({\mathbf{x}},y_{p+1})\::\:({\mathbf{x}},(y_1,\ldots,y_p))\in{\mathbf{K}}';\:y_{p+1}y_p=1\}$$ and so $f/g$ is b.s.a.  whenever $f$ and $g$ are. 

-   With $f\geq0$ on ${\mathbf{K}}$ and $q\in{\mathbb{N}}$, $f^{1/q}$ has the [b.s.a.l.]{}$$\Psi_{f^{1/q}}=\{({\mathbf{x}},y_{p+1})\::\:({\mathbf{x}},(y_1,\ldots,y_p))\in{\mathbf{K}}';\:y_{p+1}^{q}=y_p;\:y_{p+1}\geq 0\}$$

-   $\vert f\vert$ has the [b.s.a.l.]{}$$\Psi_{\vert f\vert}=\{({\mathbf{x}},y_{p+1})\::\:({\mathbf{x}},(y_1,\ldots,y_p))\in{\mathbf{K}}';\:y_{p+1}^2=y_p^2;\,y_{p+1}\geq0\}$$

-   If $f$ and $g$ have a [b.s.a.l.]{}then so does $f\wedge g$ (resp.  $f \vee g$) because $2(f\wedge g)=(f+g)-\vert f-g\vert$ (resp.  $2(f\vee g)=(f+g)+\vert f-g\vert$). 

\[exlift\] Let $f\in{\mathcal{A}}$ be the function defined in (\[demo\]), and let ${\mathbf{K}}'_f\subset{\mathbb{R}}^{n+8}$ be the basic semi-algebraic set defined by the constraints: $$\begin{aligned}
{\mathbf{K}}'_f=\left\{({\mathbf{x}},{\mathbf{y}})\in{\mathbb{R}}^{n+9}\::\quad\right.g_j({\mathbf{x}})&\geq&0,\quad j=1,\ldots,m;\\
y_i^2-h_i({\mathbf{x}})^2&=&0;\quad y_i\geq0;\quad i=1,2.\\
y_3^{2q+1}-y_1^{2q+1}-y_2^{2q+1}&=&0;\quad y_3\geq 0\\
y_4\,\ell({\mathbf{x}}) &=&1;\\
y_5^2-y_4-y_3&=&0;\quad y_5\geq0\\
y_6^{2p}-(u({\mathbf{x}})+v({\mathbf{x}}))^2&=&0;\quad y_6\geq0\\
y_7^2-(y_6-y_5)^2&=&0;\quad y_7\geq 0\\
2y_8-(y_6+y_5)+y_7&=&0\left.\right\}\end{aligned}$$ Then $\Psi_f=\{({\mathbf{x}},y_8)\::\:({\mathbf{x}},{\mathbf{y}})\in{\mathbf{K}}'_f\}$.

Observe that with each variable $y_k$ of the lifting ${\mathbf{y}}$ is associated a certain function $v_k\in{\mathcal{A}}$. For instance in Example \[exlift\]: $$y_i\to v_i({\mathbf{x}}):=\vert h_i({\mathbf{x}})\vert,\:i=1,2;\:y_3\to v_3({\mathbf{x}})
:=(v_1({\mathbf{x}})^{2q+1}+v_2({\mathbf{x}})^{2q+1})^{1/(2q+1)}$$ $$y_4\to v_4({\mathbf{x}}):=(\ell({\mathbf{x}})^{-1};\:y_5\to v_5({\mathbf{x}}):=\sqrt{v_3({\mathbf{x}})+v_4({\mathbf{x}})}$$ $$y_6\to v_6({\mathbf{x}}):=\vert u({\mathbf{x}})+v({\mathbf{x}})\vert^{1/p};\:y_7\to v_7({\mathbf{x}}):=\vert v_6({\mathbf{x}})-v_5({\mathbf{x}})\vert$$ and $y_8\to v_8({\mathbf{x}}):=f({\mathbf{x}})$.

Next, with ${\mathbf{K}}\subset{\mathbb{R}}^n$ as in (\[setkk\]), consider the set ${\mathbf{S}}\subseteq{\mathbf{K}}$ defined by: $$\label{sets}
{\mathbf{S}}:=\{{\mathbf{x}}\in{\mathbf{K}}\,:\,h_\ell({\mathbf{x}})\geq 0,\:\ell=1,\ldots,s\}$$ for some finite family $(h_k)_{k=1}^s\subset{\mathcal{A}}$.

\[lemma-setS\] The set ${\mathbf{S}}$ in (\[sets\]) is a semi-algebraic set which is the projection of a lifted basic semi-algebraic set.  It can be written $$\begin{aligned}
\nonumber
{\mathbf{S}}\,=\,\left\{{\mathbf{x}}\in{\mathbb{R}}^{n}\::\:\exists {\mathbf{y}}\in{\mathbb{R}}^t\right.&\mbox{s.t.}&{\mathbf{x}}\in{\mathbf{K}};\quad u_k({\mathbf{x}},{\mathbf{y}})=0,\quad k=1,\ldots,r\\
\label{setS}
&&\left.  y_j\geq0,\quad j\in J\right\}\end{aligned}$$ for some integers $r,t$, some polynomials $(u_k)_{k=1}^r\subset{\mathbb{R}}[{\mathbf{x}},{\mathbf{y}}]$ and some index set $J\subseteq\{1,\ldots,t\}$.

With the lifting ${\mathbf{y}}$ is associated a vector of functions ${\mathbf{v}}\in{\mathcal{A}}^t$.

By Lemma \[sal\], each function $h_\ell$ is b.s.a.  and so there is an integer $n_\ell$ and a basic semi-algebraic set ${\mathbf{K}}'_\ell\subset{\mathbb{R}}^{n+n_\ell}$ such that: $$\Psi_{h_\ell}\,=\,\{({\mathbf{x}},y^{\ell}_{n_\ell})\::\:({\mathbf{x}},{\mathbf{y}}^\ell)\in{\mathbf{K}}'_\ell\},\quad \ell=1,\ldots,s,$$ with ${\mathbf{y}}^\ell\in{\mathbb{R}}^{n_\ell}$, $\ell=1,\ldots,s$. Therefore, $${\mathbf{S}}\,=\,\{{\mathbf{x}}\in{\mathbb{R}}^n\::\:
\exists \,{\mathbf{y}}^1,\ldots,{\mathbf{y}}^s\mbox{ s.t. }({ \mathbf{x}},{\mathbf{y}}^\ell)\in {\mathbf{K}}'_\ell;\:y^\ell_{n_\ell}\geq0;\quad \ell=1,\ldots,s\},$$ and so ${\mathbf{S}}$ is the projection of a lifted basic semi-algebraic set which lives in ${\mathbb{R}}^{n+\sum_\ell n_l}$. Obviously it is of the form (\[setS\]). 

Next we state the main result of this section. 

Let ${\mathbf{K}}\subset{\mathbb{R}}^n$ be a compact basic semi-algebraic set as in (\[setkk\]) and let ${\mathbf{S}}$ be as in (\[sets\]) for some finite family $(h_\ell)\subset{\mathcal{A}}$. Let $f\in{\mathcal{A}}$ have the [b.s.a.l.]{}$$\begin{aligned}
\Psi_f\,=\,\left\{({\mathbf{x}},z_{m_f})\right.&:&{\mathbf{x}}\in{\mathbf{K}};\:q_\ell({\mathbf{x}},{\mathbf{z}})\,=\, 0,\quad \ell=1,\ldots,t_f\\
&&\left.  z_j\geq 0,\quad j\in J_f\right\}\end{aligned}$$ (where ${\mathbf{z}}=(z_1,\ldots,z_{m_f})$ and $J\subseteq\{1,\ldots,m_f\}$) and let ${\mathbf{p}}=({\mathbf{p}}_1,\ldots,{\mathbf{p}}_{m_f})\in{\mathcal{A}}^{m_f}$ be the vector of functions associated with the lifting ${\mathbf{z}}$.

If $f$ is positive on ${\mathbf{S}}$ then $$\begin{aligned}
\nonumber
f({\mathbf{x}})&=&\sigma_0({\mathbf{x}},{\mathbf{v}}({\mathbf{x}}),{\mathbf{p}}({\mathbf{x}}))+\sum_{j=1}^m\sigma_j({\mathbf{x}},{\mathbf{v}}({\mathbf{x}}),{\mathbf{p}}({\mathbf{x}}))\,g_j({\mathbf{x}})\\
&&+\sum_{k\in J}\psi_k({\mathbf{x}},{\mathbf{v}}({\mathbf{x}}),{\mathbf{p}}({\mathbf{x}})){\mathbf{v}}_k({\mathbf{x}})\\
&&+\sum_{\ell\in J_f}{\varphi}_\ell({\mathbf{x}},{\mathbf{v}}({\mathbf{x}}),{\mathbf{p}}({\mathbf{x}}))\,{\mathbf{p}}_\ell({\mathbf{x}})\\
\label{put}
&&+{\varphi}_0({\mathbf{x}},{\mathbf{v}}({\mathbf{x}}),{\mathbf{p}}({\mathbf{x}}))(M-\Vert ({\mathbf{x}},{\mathbf{v}}({\mathbf{x}}),{\mathbf{p}}({\mathbf{x}}))\Vert^2)\end{aligned}$$ for some $(\sigma_j),(\psi_k),({\varphi}_\ell)\subset\Sigma{\mathbb{R}}[{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}]$ and a sufficiently large $M>0$.

The following simple example illsutrates why the b.s.a.  functions are much nicer than general semi-algebraic functions.  Let ${\mathcal{A}}= {\mathbb{R}}[x, \chi_S]$ be the algebra generated by the polynomials in the variables $x \in {\mathbb{R}}$ and the characteristic function of a basic algebraic set, say for simplicity given by a single inequality $$S = \{ x \in {\mathbb{R}};\ h(x) \geq 0 \}$$ where $h \in {\mathbb{R}}[x]$ is a non-zero polynomial.  An element $f \in {\mathcal{A}}$ is of the form $f = f_1 \chi_S + f_2 (1-\chi_S),$ with $f_1,f_2 \in {\mathbb{R}}[x]$. Let $Q \in {\mathcal{A}}$ be an archimedean quadratic module with associated positivity set $P(Q)$. The question whether $f|_{P(Q)}>0$ reduces therefore to $(f_1)|_{P(Q)\cap S} >0$ and independently\
$(f_2)|_{P(Q) \setminus S}>0$. While the first condition is reducible to the above setting $$(f_1)|_{P(Q + h \Sigma {\mathbb{R}}[{\mathbf{x}}]^2)}>0,$$ the second condition involves the positivity of the polynomial $f_2$ on a [*non-closed*]{} semi-algebraic set.  This case can be resolved in general only with the help of Stengle’s Positivstellensatz, see for details [@BCR; @PD]. 

To be more explicit, consider $h(x) = \|x\|^2 -1$ and $Q = \Sigma {\mathbb{R}}[x]^2+
(2-\|x\|^2)\Sigma {\mathbb{R}}[x]^2$. We are then led to consider the problem $$\label{Stengle}
 f_2(x)>0 \ \ \ \ {\rm whenever} \ \ \ \ \|x\|^2<1,$$ where $f_2$ is a polynomial in ${\mathbf{x}}$. Stengle’s Theorem states that the implication (\[Stengle\]) holds if and only if there exists a positive integer $N$ and $\sigma_i \in \Sigma {\mathbb{R}}[{\mathbf{x}}]^2, \ \ 0 \leq i \leq 3,$ such that $$f_2 (\sigma_0 + (1-\|x\|^2)\sigma_1 ) = (1-\|x\|^2)^{2N} + \sigma_2 + (1-\|x\|^2)\sigma_3.$$ In conclusion, even if the graph of the characteristic function $\chi_S$ is semi-algebraic, a departure from the requirement that it is a (lifted) basic semi-algebraic set implies that the sought certificate of positivity of an element $f \in {\mathcal{A}}$ requires denominators. 

Semi-algebraic optimization
===========================

In this section we consider the application of preceding results to optimization of a function $f$ of the algebra ${\mathcal{A}}$, over a compact set ${\mathbf{S}}$ as in (\[sets\]) (with ${\mathbf{K}}$ as in (\[setkk\])) and whose defining inequality constraints are also defined with functions in this algebra ${\mathcal{A}}$. Recall that by Lemma \[lemma-setS\], the set ${\mathbf{S}}$ can also be written as the projection (\[setS\]) of a basic semi-algebraic set in a lifted space ${\mathbb{R}}^{n+t}$.

Consider the optimization problem: $${\mathbf{P}}:\quad f^*:=\:\min_{\mathbf{x}}\: \{\,f({\mathbf{x}})\::\: {\mathbf{x}}\in{\mathbf{S}}\:\}$$

With ${\mathbf{K}}$ in (\[setkk\]) compact and with ${\mathbf{S}}$ as in (\[sets\])-(\[setS\]), let $f\in{\mathcal{A}}$ have the [b.s.a.l.]{}$$\begin{aligned}
\Psi_f\,=\,\left\{({\mathbf{x}},z_f)\right.&:&{\mathbf{x}}\in{\mathbf{K}};\:q_\ell({\mathbf{x}},{\mathbf{z}})\,=\, 0,\quad \ell=1,\ldots,t_f\\
&&\left.  z_j\geq 0,\quad j\in J_f\right\}\end{aligned}$$ (where ${\mathbf{z}}=(z_1,\ldots,z_{m_f})$ and $J\subseteq\{1,\ldots,m_f\}$) and let ${\mathbf{p}}=({\mathbf{p}}_1,\ldots,{\mathbf{p}}_{m_f})\in{\mathcal{A}}^{m_f}$ be the vector of functions associated with the lifting ${\mathbf{z}}$. Then ${\mathbf{P}}$ is also the polynomial optimization: $$f^*\,=\,\min_{{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}}\:\{z_{m_f}\::\: ({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})\,\in\,\Omega\}$$ where $\Omega\subset{\mathbb{R}}^{n+t+m_f}$ is the basic semi-algebraic set $$\label{setomega}
\begin{array}{lrll}
\Omega=&\{({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})\::\:&g_j({\mathbf{x}})&\geq0,\quad j=1,\ldots,m\\
&&u_k({\mathbf{x}},{\mathbf{y}})&=0,\quad k=1,\ldots,r\\
&&q_\ell({\mathbf{x}},{\mathbf{z}})&=0,\quad \ell=1,\ldots,t_f\\
&&y_k,z_j&\geq0,\quad k\in J,\:j\in J_f\:\}
\end{array}$$

The proof follows directly from Lemma \[lemma-setS\] and the definiton of the [b.s.a.l.]{}$\Psi_f$.\
Then one may apply the moment-sos approach developed in e.g. [@Lasserre1; @lasserrebook] and build up a hierarchy of semidefinite programs whose associated sequence of optimal values converges to the global optimum $f^*$.

That is, with ${\mathbf{w}}=({\mathbf{w}}_{\alpha\beta\gamma})$ being a real sequence indexed in the index set ${\mathbb{N}}^n\times{\mathbb{N}}^{t}\times{\mathbb{N}}^{m_f}$, let $L_{\mathbf{w}}:{\mathbb{R}}[{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}]\to{\mathbb{R}}$ be the linear functional $$p\:(=\sum_{\alpha\beta\gamma}p_{\alpha\beta\gamma}\,{\mathbf{x}}^\alpha\,{\mathbf{y}}^\beta\;{\mathbf{z}}^\gamma)\quad\mapsto
L_{\mathbf{w}}(p):=\sum_{\alpha\beta\gamma}p_{\alpha\beta\gamma}\,w_{\alpha\beta\gamma}.$$ Let $\theta\in{\mathbb{R}}[{\mathbf{x}},{\mathbf{y}}\,{\mathbf{z}}]$ be the quadratic polynomial $$({\mathbf{x}},{\mathbf{y}}\,{\mathbf{z}})\,\mapsto\,\theta({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})\,:=\,M-\Vert ({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})\Vert^2,$$ with $M$ such that $M>\Vert({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})\Vert^2$ on $\Omega$, and let $a_k:=\lceil ({\rm deg}\,u_k)/2\rceil$ and $b_\ell:=\lceil ({\rm deg}\,q_\ell)/2\rceil$, for every $k=1,\ldots,r$, $\ell=1,\ldots,t_f$.

For $i\geq\max_{k,\ell}[a_k,b_\ell]$, consider the semidefinite program $$\label{sdp1}
\begin{array}{rlll}
\rho_i=&\min &w_{00m_f}&\\
&\mbox{s.t.}&M_i({\mathbf{w}})&\succeq0\\
&&M_{i-a_k}(u_k\,{\mathbf{w}})&\succeq0,\quad k=1,\ldots,r\\
&&M_{i-b_\ell}(q_\ell\,{\mathbf{w}})&\succeq0,\quad \ell=1,\ldots,t_f\\
&&M_{i-1}(y_j\,{\mathbf{w}})&\succeq0,\quad j\in\,J\\
&&M_{i-1}(z_j\,{\mathbf{w}})&\succeq0,\quad j\in\,J_f\\
&&M_{i-1}(\theta\,{\mathbf{w}})&\succeq0\\
&&w_{000}&=1. 
\end{array}$$

\[th-sdp\] Consider the hierarchy of semidefinite programs (\[sdp1\]). 

[(a)]{} The sequence $(\rho_i)$ is monotone nondecreasing and $\rho_i\,\to\,f^*$ as $i\to\infty$.

[(b)]{} Let ${\mathbf{w}}^i$ be an optimal solution of (\[sdp1\]) and assume that $$\label{rank}
{\rm rank}\,M_i({\mathbf{w}})\,=\,{\rm rank}\,M_{i-c}({\mathbf{w}})\,=:d,$$ whre $c:=\max_{b_k,a_\ell}$. Then $\rho_i=f^*$ and ${\mathbf{w}}$ is the moment sequence of a $d$-atomic probability measure supported on $d$ points of the set $\Omega$ defined in (\[setomega\]). 

As ${\mathbf{P}}$ is a standard polynomial optimization problem, the proof follows directly from e.g. [@Lasserre1; @lasserrebook]. 

Theorem \[th-sdp\] is illustrated below on the following two simple examples:

Let $n=2$ and ${\mathbf{P}}:\:f^*=\displaystyle\max_{\mathbf{x}}\{\,\vert x_1\vert \,x_2-x_1^2\,:\:
\Vert {\mathbf{x}}\Vert^2=1\}$. Hence $$\Omega=\{({\mathbf{x}},z)\::\:\Vert {\mathbf{x}}\Vert^2-1=0;\:z^2-x_1^2=0;\:z\geq 0\}.$$ Observe that $\vert x_1\vert\leq 1$ on ${\mathbf{K}}=\{{\mathbf{x}}\,:\,\Vert{\mathbf{x}}\Vert^2=1\}$ and so one may choose $\theta({\mathbf{x}},z):=\:3-\Vert({\mathbf{x}},z)\Vert^2$. At the second relaxation (\[sdp1\]) the rank condition (\[rank\]) is satisfied with $d=2$, and one obtains $f^*=\rho_2=0.2071$ with the two optimal solutions: $$({\mathbf{x}}^*,z^*)=(0.3827,\,0.9239,\,0.3827);\:
({\mathbf{x}}^*,z^*)=(-0.3827,\,-0.9239,\,0.3827).$$

Let $n=2$ and ${\mathbf{P}}:\:f^*=\displaystyle\max_{\mathbf{x}}\{\,x_1\,\vert x_1-2x_2\vert \,:\:
\Vert {\mathbf{x}}\Vert^2=1\}$. Hence $$\Omega=\{({\mathbf{x}},z)\::\:\Vert {\mathbf{x}}\Vert^2-1=0;\:z^2-(x_1-2x_2)^2=0;\:z\geq 0\}.$$ Observe that $\vert x_1-2x_2\vert\leq 3$ on ${\mathbf{K}}=\{{\mathbf{x}}\,:\,\Vert{\mathbf{x}}\Vert^2=1\}$ and so one may choose $\theta({\mathbf{x}},z):=11-\Vert({\mathbf{x}},z)\Vert^2$. At the second relaxation (\[sdp1\]) the rank condition (\[rank\]) is satisfied with $d=1$, and one obtains $f^*=\rho_2=1.6180$ and the optimal solution: $({\mathbf{x}}^*,z^*)=(0.8507,\,-0.5257,\,1.9021)$.

\(a) A usual lifting strategy (well-known from optimizers) to handle optimization problems of the form ${\mathbf{P}}:\min_{\mathbf{x}}\{f({\mathbf{x}})\,:\,{\mathbf{x}}\in{\mathbf{K}}\}$, with $f({\mathbf{x}})=\max_{j\in J}f_j({\mathbf{x}})$ for some finite index set $J$, is to use only one lifting $z$ and solve $$\min_{{\mathbf{x}},z}\:\{\,z\,:\,{\mathbf{x}}\in{\mathbf{K}},\:z\geq f_j({\mathbf{x}}),\:j\in J\}.$$ Similarly with $f({\mathbf{x}})=\vert g({\mathbf{x}})\vert$ one uses $z\geq\pm g({\mathbf{x}})$. In this case one has only one additional variable with no equality constraint.  In particular, this lifting preserves convexity (when present).  But this lifting is valid in some particular cases only and for instance it does not work if $f$ is replaced with $f({\mathbf{x}})=h({\mathbf{x}})-\max_{j\in J}[f_j({\mathbf{x}})]$, or $f({\mathbf{x}})=h({\mathbf{x}})-\vert g({\mathbf{x}})\vert$.

\(b) In the description of the set $\Omega$, a “lifting” ${\mathbf{y}}^\ell$ is associated with each non polynomial function $h_\ell\in{\mathcal{A}}$ that appears in the description of ${\mathbf{P}}$, as well as a lifting ${\mathbf{z}}$ for $f$ (if non polynomial).  This can be rapidly penalizing.  However it is worth noting that there is no mixing between the lifting variables ${\mathbf{z}}$ and ${\mathbf{y}}^\ell$, as well as between the lifting variables ${\mathbf{y}}^\ell$ of different $\ell$’s.  The coupling of all these variables is through the variables ${\mathbf{x}}$. Hence there is an obvious sparsity pattern if the set of all variables $({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})$ is written as the union (with overlaps) $$({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})\,=\,({\mathbf{x}})\,\cup\,({\mathbf{x}},{\mathbf{z}})\,\cup\,({\mathbf{x}},{\mathbf{y}}^1)\,\cup\,\cdots\,\cup\,({\mathbf{x}},{\mathbf{y}}^s)$$ and this sparsity pattern obviously satifies the co-called [*running intersection property*]{}, because for each $1\leq k <s$, $$({\mathbf{x}},{\mathbf{y}}^{k+1})\,\bigcap\,\left(({\mathbf{x}})\cup({\mathbf{x}},{\mathbf{z}})\displaystyle\cup_{i=1}^{k}({\mathbf{x}},{\mathbf{y}}^i)\right)\,\subseteq ({\mathbf{x}}).$$ See e.g. [@lasserresparse].  This is a good news because with such a sparsity pattern one may use the sparse semidefinite relaxations defined in [@Waki], whose associated sequence of optimal values was still proved to converge to $f^*$ in [@lasserresparse].  Hence if on the one hand lifting is penalizing, on the other hand the special structure of the lifted polynomial optimization problem permits to use specialized “sparse” relaxations, which (partly) compensates the increase in the number of variables.  For more details on sparse semidefinite relaxations, the interested reader is referred to e.g. [@lasserresparse] and [@Waki].  And finally, one should also bear in mind that the original problem ${\mathbf{P}}$ being very hard, there is obviously some price to pay for its resolution! 

[99]{}

Bochnack, M. Coste, M.-F. Roy, [*Real Algebraic Geometry*]{}, Ergeb.  Math.  Grenzgebiete (3rd series) [**36**]{}, Springer, 1998, Berlin-New York. 

D. Bertsimas, I. Popescu, [*Optimal inequalities in probability theory: a convex optimization approach,*]{} SIAM J. Optim. [** 15**]{} (2005), no.  3, 780–804. 

B. Bojanov, P. Petrov, [*Gaussian interval quadrature formulae for Tchebycheff systems*]{}, SIAM J. Numer.  Anal. [** 43**]{} (2005), 787–795. 

C. N. Delzell, [*A continuous, constructive solution to Hilbert’s 17-th problem*]{}, Invent.  Math. [** 76**]{}(1984), 365-384. 

C. N. Delzell, [*Continuous, piecewise polynomial functions which solve Hilbert’s 17-th problem*]{}, J. reine Angew.  Math. [** 440**]{}(1993), 157-173. 

J.W. Helton, M. Putinar, [*Positive Polynomials in Scalar and Matrix Variables, the Spectral Theorem and Optimization*]{}, in vol. [* Operator Theory, Structured Matrices, and Dilations*]{}, Theta, Bucharest, 2007, pp 229-306. 

K. Isii, [*The extrema of probability determined by generalized moments.  I. Bounded random variables*]{}, Ann.  Inst.  Statist.  Math. [** 12**]{} (1960), 119–134; errata, 280. 

K. Isii, [*Inequalities of the types of Chebyshev and Cramer-Rao and mathematical programming*]{}, Ann.  Inst.  Statist.  Math. [** 16**]{} (1964), 277–293. 

S. Kakutani, [*Ein Beweis des Satzes von M. Eidelheit über konvexe Mengen,*]{} Proc.  Imp.  Acad.  Tokyo [**13**]{}(1937), 93-94. 

S. Karlin, W.J. Studden, [*Optimal experimental designs*]{}, Ann.  Math.  Statist. [** 37**]{} (1966), 783–815. 

S. Karlin, W.J. Studden,[*Tchebycheff systems: With applications in analysis and statistics.*]{}  Pure and Applied Mathematics, Vol.  XV Interscience Publishers John Wiley & Sons, New York-London-Sydney, 1966. 

G. Köthe, *Topological Vector Spaces.  I.* Springer, Berlin, 1969. 

M. G. Krein, [*The ideas of P. L. Tchebysheff and A. A. Markov in the theory of limiting values of integrals and their further development.*]{} ( Russian) Uspehi Matem.  Nauk (N.S.) [**6**]{} (1951), 3–120. 

M. G. Krein, A. Nudelman, [*A. A. The Markov moment problem and extremal problems.  Ideas and problems of P. L. Tchebysheff and A. A. Markov and their further development.*]{}  Translated from the Russian by D. Louvish, Translations of Mathematical Monographs, Vol. [** 50**]{}.  American Mathematical Society, Providence, R.I., 1977. 

M. G. Krein, M.A.Rutman, [*Linear operators leaving invariant a cone in a Banach space*]{} (in Russian) Uspehi Mat.  Nauk [**23**]{}(1948), pp.  3-95. 

J. B. Lasserre, [*Optimisation globale et théorie des moments*]{}, C. R. Acad.  Sci.  Paris [**331**]{} Série 1, 929–934. 

J.B. Lasserre, [*Global optimization with polynomials and the problem of moments*]{}, SIAM J. Optim. [** 11**]{}(2001), 796-817. 

J.B. Lasserre, [*Convergent SDP-relaxations in polynomial optimization with sparsity*]{}, SIAM J. Optim. [** 17**]{}, (2006), 822–843. 

J.B. Lasserre, [*Moments, Positive Polynomials and Their Applications*]{}, Imperial College Press, London (2009)

, (D. Henrion, A. Garulli, eds.),  Lecture Notes in Control and Information Sciences, Springer, Berlin, Heidelberg, 2005. 

P. A. Parrilo, [*Semidefinite programming relaxations for semialgebraic problems*]{}, Math.  Program.  Ser.  B [**96**]{}, (2003), 293-320.  A. Prestel, C. Delzell, [*Positive polynomials*]{}, Springer, Berlin, 2001. 

M. Putinar, [*Positive polynomials on compact semi-algebraic sets*]{}, Indiana Univ.  Math.  J. [**42**]{}, (1993) 969-984

, (M. Putinar, S. Sullivant, eds.),  IMA Series in Applied Mathematics, Springer, Berlin, 2009. 

F. Riesz, B. Sz.-Nagy, [*Functional analysis*]{}, Transl.  from the 2nd French ed.  by Leo F. Boron.  Reprint of the 1955 orig.  publ.  by Ungar Publ.  Co., Dover Books on Advanced Mathematics, Dover Publications, Inc., New York, 1990. 

M. Riesz, [*Sur le problème des moments.  Troisième Note*]{}, Ark. Mat.  Fys.  **16**(1923), 1–52. 

K. Schmüdgen, [*The K-moment problem for compact semi-algebraic sets*]{}, Math.  Ann. [** 289**]{} (1991) 203-206. 

H. Waki, S. Kim, M. Kojima, M. Maramatsu, [*Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity*]{}, SIAM J. Optim. [** 17**]{}, (2006) 218–

R. Zielke, [*Discontinuous Tchebysheff systems*]{}, Lecture Notes in Mathematics [**707**]{}, Springer, Berlin, 1979. 

[^1]: 

[^2]: Work partially supported by a National Science Foundation Grant-USA.  The authors are grateful to the American Institute of Mathematics in Palo Alto, CA, which has hosted a meeting where the present work was initiated
