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 $\Bbb R^n$ simple sum of squares (sos) perturbations $f_\varepsilon$ 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\{f(x): x\in K\}=\max \{\lambda: f(x)-\lambda \geq 0, \forall x\in K\},$ where $K\subseteq \Bbb R^n$ is suitable. For $f=\sum_\alpha f_\alpha x^\alpha\in \Bbb R[x_1,\dots,x_n],$ define $\vert \vert f\vert \vert _1=\sum_\alpha \vert f_\alpha\vert $ and denote by {\bf P} the problem $f^*:=\inf\{f(x): x\in \Bbb R^n\},$ and by ${\cal P}_M$ the problem $\inf \{\int f \,d\mu: \int \sum_{i=1}^n e^{x_i^2} d\mu \leq ne^{M^2}\}.$ Here $\mu\in {\cal P}(\Bbb R^n), $ the space of probability measures on $\Bbb R^n.$ Let $\inf {\cal P}_M$ be the optimal value of ${\cal P}_M.$ The multiindices $\alpha \in \Bbb N^n$ are considered suitably endowed with a natural linear order. P3.2: Assume $-\infty < f^*.$ Then $\inf {\cal P}_M \downarrow f^*$ as $M\rightarrow \infty.$ Next the author introduces for $r\geq \deg f/2,$ $r\in \Bbb N$ a semidefinite programming problem $Q_r$ that is a relaxation of ${\cal P}_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 \uparrow \inf {\cal P}_M$ for all admissible $r$ as $r \rightarrow \infty.$ Let ${\bold y}^{(r)}= \{y_\alpha^{(r)}\}$ be an optimal solution of $Q_r$ and embed it naturally into Banach space $l_\infty.$ Then every pointwise accumulation point {\bf y}$^*$ of the sequence $\{ {\bold y^{(r)}} \}$ of optimal solutions admits a representation $y_\alpha^*=\int x^\alpha d\mu^* $ with a unique $\mu^*\in {\cal P}(\Bbb R^n)$ that itself is an optimal solution to ${\cal P}_M.$ As a consequence one can approximate the optimal value $f^*$ of ${\bold P}$ 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$\leq M.$ This method is simpler than the procedure proposed in {\it J. B. Lasserre} [SIAM J. Optim. 11, No. 3, 796--817 (2001; Zbl 1010.90061)]. Another important result is T4.1: Assume $0\leq f^*=\min f(x).$ For every $\varepsilon >0$ there is some $r(f,\varepsilon) \in \Bbb N$ such that $f_\varepsilon =f+ \varepsilon \sum_{k=0}^{r(f,\varepsilon)} \frac{1}{k!}(x_1^{2k}+\cdots+x_n^{2k})$ is sum of squares. In particular $\vert \vert f-f_\varepsilon\vert \vert _1 \rightarrow 0$ as $\varepsilon \downarrow 0.$ Define the semialgebraic set ${\bold K}= \{x\in \Bbb R^n: g_j(x)\geq 0, j=1,\dots ,m\}.$ C4.3: If the $g_j$ are concave (hence ${\bold K}$ convex) and satisfy Slater’s condition, $f$ is convex, and ${\bold K}$ compact, then $f_\varepsilon=f_0+\sum_{j=1}^m \lambda_j g_j$ with some sos $f_0$ and nonnegative $\lambda_j.$ \quad In particular this shows a simplified Putinar representation for $f_\varepsilon,$ see {\it M. Putinar} [Indiana Univ. Math. J. 42, No. 3, 969--984 (1993; Zbl 0796.12002)] or {\it A. Prestel} and {\it 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:
12D15Formally real fields
14P10Semialgebraic sets and related spaces
13J30Real algebra
90C22Semidefinite programming
Software:
Sostools
WorldCat.org
Full Text: DOI