# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
A sum of squares approximation of nonnegative polynomials. (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 ${ℝ}^{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\left(x\right):x\in K\right\}=max\left\{\lambda :f\left(x\right)-\lambda \ge 0,\forall x\in K\right\},$ where $K\subseteq {ℝ}^{n}$ is suitable.

For $f={\sum }_{\alpha }{f}_{\alpha }{x}^{\alpha }\in ℝ\left[{x}_{1},\cdots ,{x}_{n}\right],$ define ${||f||}_{1}={\sum }_{\alpha }|{f}_{\alpha }|$ and denote by P the problem ${f}^{*}:=inf\left\{f\left(x\right):x\in {ℝ}^{n}\right\},$ and by ${𝒫}_{M}$ the problem $inf\left\{\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}}\right\}·$ Here $\mu \in 𝒫\left({ℝ}^{n}\right),$ the space of probability measures on ${ℝ}^{n}·$ Let $inf{𝒫}_{M}$ be the optimal value of ${𝒫}_{M}·$ The multiindices $\alpha \in {ℕ}^{n}$ are considered suitably endowed with a natural linear order.

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

T3.3: Assume $f$ has a global minimum ${f}^{*}>-\infty ·$ Then $max{Q}_{r}^{*}=min{Q}_{r}↑inf{𝒫}_{M}$ for all admissible $r$ as $r\to \infty ·$ Let ${𝐲}^{\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 }·$ Then every pointwise accumulation point y${}^{*}$ of the sequence $\left\{{𝐲}^{\left(r\right)}\right\}$ of optimal solutions admits a representation ${y}_{\alpha }^{*}=\int {x}^{\alpha }d{\mu }^{*}$ with a unique ${\mu }^{*}\in 𝒫\left({ℝ}^{n}\right)$ that itself is an optimal solution to ${𝒫}_{M}·$ As a consequence one can approximate the optimal value ${f}^{*}$ of $𝐏$ as closely as desired by solving SDP relaxations ${Q}_{r}$ for sufficiently large values of $r$ and $M·$ $M$ can be fixed whenever whenever a global minimizer ${x}^{*}$ of $f$ can be shown to have $\infty$-norm$\le M·$ 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)·$ For every $\epsilon >0$ there is some $r\left(f,\epsilon \right)\in ℕ$ such that ${f}_{\epsilon }=f+\epsilon {\sum }_{k=0}^{r\left(f,\epsilon \right)}\frac{1}{k!}\left({x}_{1}^{2k}+\cdots +{x}_{n}^{2k}\right)$ is sum of squares. In particular $||f-{f}_{\epsilon }{||}_{1}\to 0$ as $\epsilon ↓0·$ Define the semialgebraic set $𝐊=\left\{x\in {ℝ}^{n}:{g}_{j}\left(x\right)\ge 0,j=1,\cdots ,m\right\}·$

C4.3: If the ${g}_{j}$ are concave (hence $𝐊$ convex) and satisfy Slater’s condition, $f$ is convex, and $𝐊$ compact, then ${f}_{\epsilon }={f}_{0}+{\sum }_{j=1}^{m}{\lambda }_{j}{g}_{j}$ with some sos ${f}_{0}$ and nonnegative ${\lambda }_{j}·$    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
Sostools