*(English)*Zbl 1129.12004

Using results from the generalised moment problem and duality from convex optimization the author shows that given a nonnegative polynomial $f$ on ${\mathbb{R}}^{n}$ simple sum of squares (sos) perturbations ${f}_{\epsilon}$ arbitrarily near to $f$ can be constructed. This is important since sos representations can be found relatively fast by semidefinite programming and are a surrogate for deciding the NP hard problem of nonnegativity of a polynomial. Furthermore, certain minimization problems for polynomials can be related to problems for positive semidefinite polynomials by observing that $min\left\{f\right(x):x\in K\}=max\{\lambda :f(x)-\lambda \ge 0,\forall x\in K\},$ where $K\subseteq {\mathbb{R}}^{n}$ is suitable.

For $f={\sum}_{\alpha}{f}_{\alpha}{x}^{\alpha}\in \mathbb{R}[{x}_{1},\cdots ,{x}_{n}],$ define ${\left|\right|f\left|\right|}_{1}={\sum}_{\alpha}\left|{f}_{\alpha}\right|$ and denote by **P** the problem ${f}^{*}:=inf\{f\left(x\right):x\in {\mathbb{R}}^{n}\},$ and by ${\mathcal{P}}_{M}$ the problem $inf\{\int f\phantom{\rule{0.166667em}{0ex}}d\mu :\int {\sum}_{i=1}^{n}{e}^{{x}_{i}^{2}}d\mu \le n{e}^{{M}^{2}}\}\xb7$ Here $\mu \in \mathcal{P}\left({\mathbb{R}}^{n}\right),$ the space of probability measures on ${\mathbb{R}}^{n}\xb7$ Let $inf{\mathcal{P}}_{M}$ be the optimal value of ${\mathcal{P}}_{M}\xb7$ The multiindices $\alpha \in {\mathbb{N}}^{n}$ are considered suitably endowed with a natural linear order.

P3.2: Assume $-\infty <{f}^{*}\xb7$ Then $inf{\mathcal{P}}_{M}\downarrow {f}^{*}$ as $M\to \infty \xb7$ Next the author introduces for $r\ge degf/2,$ $r\in \mathbb{N}$ a semidefinite programming problem ${Q}_{r}$ that is a relaxation of ${\mathcal{P}}_{M}\xb7$ Let its dual be ${Q}_{r}^{*}\xb7$ In ${Q}_{r}$ one has to minimize ${\sum}_{\alpha}{f}_{\alpha}{y}_{\alpha},$ given certain semidefiniteness constraints on the reals ${y}_{\alpha}\xb7$

T3.3: Assume $f$ has a global minimum ${f}^{*}>-\infty \xb7$ Then $max{Q}_{r}^{*}=min{Q}_{r}\uparrow inf{\mathcal{P}}_{M}$ for all admissible $r$ as $r\to \infty \xb7$ Let ${\mathbf{y}}^{\left(r\right)}=\left\{{y}_{\alpha}^{\left(r\right)}\right\}$ be an optimal solution of ${Q}_{r}$ and embed it naturally into Banach space ${l}_{\infty}\xb7$ Then every pointwise accumulation point **y**${}^{*}$ of the sequence $\left\{{\mathbf{y}}^{\left(r\right)}\right\}$ of optimal solutions admits a representation ${y}_{\alpha}^{*}=\int {x}^{\alpha}d{\mu}^{*}$ with a unique ${\mu}^{*}\in \mathcal{P}\left({\mathbb{R}}^{n}\right)$ that itself is an optimal solution to ${\mathcal{P}}_{M}\xb7$ As a consequence one can approximate the optimal value ${f}^{*}$ of $\mathbf{P}$ as closely as desired by solving SDP relaxations ${Q}_{r}$ for sufficiently large values of $r$ and $M\xb7$ $M$ can be fixed whenever whenever a global minimizer ${x}^{*}$ of $f$ can be shown to have $\infty $-norm$\le M\xb7$ This method is simpler than the procedure proposed in *J. B. Lasserre* [SIAM J. Optim. 11, No. 3, 796–817 (2001; Zbl 1010.90061)].

Another important result is T4.1: Assume $0\le {f}^{*}=minf\left(x\right)\xb7$ For every $\epsilon >0$ there is some $r(f,\epsilon )\in \mathbb{N}$ such that ${f}_{\epsilon}=f+\epsilon {\sum}_{k=0}^{r(f,\epsilon )}\frac{1}{k!}({x}_{1}^{2k}+\cdots +{x}_{n}^{2k})$ is sum of squares. In particular $\left|\right|f-{f}_{\epsilon}{\left|\right|}_{1}\to 0$ as $\epsilon \downarrow 0\xb7$ Define the semialgebraic set $\mathbf{K}=\{x\in {\mathbb{R}}^{n}:{g}_{j}\left(x\right)\ge 0,j=1,\cdots ,m\}\xb7$

C4.3: If the ${g}_{j}$ are concave (hence $\mathbf{K}$ convex) and satisfy Slater’s condition, $f$ is convex, and $\mathbf{K}$ compact, then ${f}_{\epsilon}={f}_{0}+{\sum}_{j=1}^{m}{\lambda}_{j}{g}_{j}$ with some sos ${f}_{0}$ and nonnegative ${\lambda}_{j}\xb7$ In particular this shows a simplified Putinar representation for ${f}_{\epsilon},$ see *M. Putinar* [Indiana Univ. Math. J. 42, No. 3, 969–984 (1993; Zbl 0796.12002)] or *A. Prestel* and *C. N. Delzell* [Positive polynomials. From Hilbert’s 17th problem to real algebra. Springer Monographs in Mathematics. Berlin: Springer (2001; Zbl 0987.13016)].

In a footnote the reader is informed that this well written and interestingly motivated paper also appeared in SIAM J. Optim. 16, 751–765 (2006), see above.

##### MSC:

12D15 | Formally real fields |

14P10 | Semialgebraic sets and related spaces |

13J30 | Real algebra |

90C22 | Semidefinite programming |