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 ε 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):xK}=max{λ:f(x)-λ0,xK}, where K n is suitable.

For f= α f α x α [x 1 ,,x n ], define ||f|| 1 = α |f α | and denote by P the problem f * :=inf{f(x):x n }, and by 𝒫 M the problem inf{fdμ: i=1 n e x i 2 dμne M 2 }· Here μ𝒫( n ), the space of probability measures on n · Let inf𝒫 M be the optimal value of 𝒫 M · The multiindices α n are considered suitably endowed with a natural linear order.

P3.2: Assume -<f * · Then inf𝒫 M f * as M· Next the author introduces for rdegf/2, r 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 α f α y α , given certain semidefiniteness constraints on the reals y α ·

T3.3: Assume f has a global minimum f * >-· Then maxQ r * =minQ r inf𝒫 M for all admissible r as r· Let 𝐲 (r) ={y α (r) } be an optimal solution of Q r and embed it naturally into Banach space l · Then every pointwise accumulation point y * of the sequence {𝐲 (r) } of optimal solutions admits a representation y α * =x α dμ * with a unique μ * 𝒫( n ) 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 -normM· 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 0f * =minf(x)· For every ε>0 there is some r(f,ε) such that f ε =f+ε k=0 r(f,ε) 1 k!(x 1 2k ++x n 2k ) is sum of squares. In particular ||f-f ε || 1 0 as ε0· Define the semialgebraic set 𝐊={x n :g j (x)0,j=1,,m}·

C4.3: If the g j are concave (hence 𝐊 convex) and satisfy Slater’s condition, f is convex, and 𝐊 compact, then f ε =f 0 + j=1 m λ j g j with some sos f 0 and nonnegative λ j ·    In particular this shows a simplified Putinar representation for f ε , 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:
12D15Formally real fields
14P10Semialgebraic sets and related spaces
13J30Real algebra
90C22Semidefinite programming
Software:
Sostools