Workshop Optimization and

Control.

IMA Minneapolis, January 16–20 2007.

January 13, 2007

Salma Kuhlmann ^{1} , Research Center Algebra, Logic and Computation University of Saskatchewan, McLean Hall, 106 Wiggins Road, Saskatoon, SK S7N 5E6, Canada

email: skuhlman@math.usask.ca

The slides of this talk are available at: http://math.usask.ca/˜ skuhlman/slidesim.pdf

1Partially supported by the Natural Sciences and Engineering Research Council of Canada.

Approximation of positive polynomials by sums of squares.

Introduction.

In algebraic geometry, we consider ideals of the polynomial ring and algebraic varieties in affine space. In semi-algebraic geometry, we consider preorderings of the polynomial ring and semialgebraic sets in affine space.

• Let ℝ[X] := ℝ[X_{1}, ⋯, X_{n}] be the ring of polynomials in n variables and real coefficients.

• A subset M ⊆ ℝ[X] is a quadratic module if 1 ∈ M, M is closed under addition and multiplication by squares (i.e. a^{2}f ∈ M, ∀a ∈ ℝ[X] and f ∈ M).

• A quadratic preordering is a quadratic module which is also closed under multiplication.

• The smallest preordering of ℝ[X] is the set of sums of squares of ℝ[X], denoted by ∑ ℝ[X]^{2}.

• Given a finite subset S = {f_{1}, ..., f_{s}} of ℝ[X], the smallest preordering containing S (preordering finitely generated by S) is:

T_{S} = {_{e∈{0,1}^{s}}^{∑} σ_{e}f^{e} : σ_{e} ∈ ∑ ℝ[X]^{2}, f_{1}, ⋯, f_{s} ∈ S}

where f^{e} := f_{1}^{e_{1}} ⋯ f_{r}^{e_{s}}, if e = (e_{1}, ⋯, e_{s}).

• The smallest module containing S (module finitely generated by S) is:

M_{S} = {σ_{0} + σ_{1}f_{1} + ... + σ_{s}f_{s} ; σ_{e} ∈ ∑ ℝ[X]^{2} .}

• Let S = {f_{1}, ⋯, f_{s}} ⊂ ℝ[X], S defines a basic closed semialgebraic subset of ℝ^{n}:

K = K_{S} = {x ∈ ℝ^{n} : f_{1}(x) ≥ 0, …, f_{s}(x) ≥ 0} • Consider polynomials positive semi-definite on K_{S}:

Psd(K_{S}) := {f ∈ ℝ[X] : f(x) ≥ 0 for all x ∈ K_{S}}

• Psd(K_{S}) is a preordering in ℝ[X] and T_{S} ⊆ Psd(K_{S}).

Hilbert’s 17th Problem and Stengle’s Positivstellensatz are concerned with the issue of representation of positive semi-definite polynomials; motivated by the question: when it true that Psd(K_{S}) = T_{S} ?

More generally, we are concerned with the issue of approximating Psd(K_{S}) by “smaller” preorderings (modules):

T_{S}^{†} = {f : ∀ real ϵ > 0 , f + ϵ ∈ T_{S}}.

T_{S}^{‡} = {f : ∃q ∈ ℝ[X] such that ∀ real ϵ > 0, f+ϵq ∈ T_{S}}.

\overline{T_{S}} := \{f : L(f) ≥ 0, ∀ lin. funct. L ≠ 0 on ℝ[X] s. t. L(T_{S}) ≥ 0\}.

We have:

T_{S} ⊆ T_{S}^{†} ⊆ T_{S}^{‡} ⊆ \overline{T_{S}} ⊆ Psd(K_{S}) .

We say:

• T_{S} is saturated if Psd(K_{S}) = T_{S}.

• (†)_{S} holds if T_{S}^{†} = Psd(K_{S})

• (‡)_{S} holds if T_{S}^{‡} = Psd(K_{S})

• S solves the K_{S}– moment problem if \overline{T_{S}} = Psd(K_{S}). Note that this is equivalent to saying that T_{S} is dense in Psd(K_{S}).

Remark 0.1 (i) \overline{T_{S}} is the closure of T_{S} in ℝ[X] (for the finest locally convex topology on ℝ[X]).

Denote by P_{d} the (finite dimensional) vector space consisting of all polynomials in ℝ[X] of degree ≤ 2d, and by T_{d} = T_{S} ∩P_{d}. The set T_{d} is obviously a bf cone in P_{d}, i.e., T_{d} + T_{d} ⊆ T_{d} and ℝ^{+}T_{d} ⊆ T_{d}. Denote by \overline{T}_{d} the closure (in the Euclidean topology) of T_{d} in P_{d}. Then:

(ii) T_{S}^{‡} = ∪_{d≥0}\overline{T}_{d}.

(iii) The containments (end of page 4) may be strict. The conjecture that T_{S}^{‡} ≠ \overline{T_{S}} was given in [K–M] and recently proved in [N].

(iv) All the above, except for Psd(K_{S}) depend in general on the choice of the description S of K = K_{S}.

PLAN OF THE TALK

In this talk I will give an Atlas of what is known about the various approximations of Psd(K_{S}) by those preorderings (or the corresponding module versions) depending on the description S, the dimension of the semi-algebraic set K_{S}, intrinsic geometric properties of K_{S} (e.g. compact or unbounded), and special properties of K_{S} (symmetry, sparse representation):

(I) Saturation.

(II) The dagger condition.

(III) The double-dagger condition.

(IV) The density condition.

(V) Special situations.

Saturation

In [S1] Scheiderer showed: Theorem 0.2 If dim(K_{S}) ≥ 3, then there exists a polynomial p(X) ∈ ℝ[X] such that p(x) ≥ 0 for all x ∈ ℝ^{n} but p ∉ T_{S} (so T_{S} cannot be saturated).

Scheiderer’s result is intrinsic; under this hypothesis on K = K_{S}, independently of the chosen description S, and whether K_{S} is compact or unbounded, the preordering T_{S} cannot be saturated.

In the same paper, he also shows another intrinsic result: Theorem 0.3 If n = 2 and K_{S} contains a cone of dimension 2, then there exists a polynomial p(X) ∈ ℝ[X] such that p(x) ≥ 0 for all x ∈ ℝ^{n} but p ∉ T_{S} (so T_{S} cannot be saturated).

Low dimensional sets: This left open the question formulated in [K-M]: what if K_{S} ⊆ ℝ^{2} does not contain a cone of dimension 2? Are there compact/noncompact examples of such K_{S} for which T_{S} is saturated?

Recently, Scheiderer developed in a series of papers [S2], [S3], [S4] several local global principles to determine when a polynomial f ≥ 0 on K_{S} belongs to the quadratic module M_{S}. His results generalize both Schmüdgen’s and Putinar’s Striktpositivstellensätze. With these tools, he was able to produce the example that we were looking for:

Example 0.4 The modules generated by: S_{1} = {1 + x, 1 − x, 1 + y, 1 − y} (compact K_{S}) and S_{2} = {x, 1 − x, y, 1 − xy} (noncompact K_{S}) are saturated.

In [K-M-S], we studied saturated preorderings (modules) for subsets of the real line. We discuss the case n = 1 in the next slides.

To state [K-M-S; Theorem 2.2]. We need to define some notions.

If K ⊆ ℝ is a non-empty closed semi-algebraic set. Then K is a finite union of intervals. It is easily verified that K = K_{N}, for N the set of polynomials defined as follows: •If a ∈ K and (−∞, a) ∩ K = ∅, then X − a ∈ N. •If a ∈ K and (a, ∞) ∩ K = ∅, then a − X ∈ N. •If a, b ∈ K, (a, b) ∩ K = ∅, then (X − a)(X − b) ∈ N.

• N has no other elements except these.

We call N the natural set of generators for K.

We first consider the non-compact case:

Theorem 0.5 Assume that K = K_{S} ⊆ ℝ is not compact. Then T_{S} is saturated if and only S contains the natural set of generators of K (up to scalings by positive reals).

For the compact case, we also have a criterion. Assume that K_{S} has no isolated points :

Theorem 0.6 Let K_{S} be compact, S = {g_{1}, ⋯, g_{s}}. Then T_{S} is saturated if and only if, for each endpoint a ∈ K_{S}, there exists i ∈ {1, ⋯, s} such that x − a divides g_{i} but (x − a)^{2} does not.

What about the module version?

In [K-M-S] we asked whether M_{S} = T_{S} if K_{S} ⊆ ℝ is compact. Scheiderer provided a positive answer using his local-global criteria. In [F] another elementary proof of this fact is given. Thus the above theorem is a criterion for the quadratic module M_{S} to be saturated.

The dagger condition

In [Sc1] Schmüdgen proved the following intrinsic result: Theorem 0.7 If K_{S} is compact, then (†)_{S} holds for T_{S}.

A quadratic module M is archimedean if for all f ∈ ℝ[X], there exists an integer n ≥ 1 such that n − f and n + f ∈ M. Putinar proved the following result: Theorem 0.8 If M_{S} is archimedean, then (†)_{S} holds for M_{S}.

Remark 0.9 (i) If T_{S} (or M_{S}) is archimedean then K_{S} is compact. (ii) Wörman showed that if K_{S} is compact then T_{S} is archimedean (providing a proof of Schmüdgen’s Theorem via the Kadison-Dubois Theorem). (iii) If K_{S} is compact, M_{S} need not be archimedean.

What if K_{S} is not compact?

Apart from the non-compact examples of dimension ≤ 2 presented in the previous section, no non-compact examples in dimension ≥ 3 are known. This motivated considering (‡) instead, as we shall see in the next section.

The doubledagger condition

Non-compact examples by dimension extension. In [K-M] we construct a large number of non-compact examples where (‡) holds. Let S ⊆ ℝ[X] finite and set p = 1 + ∑_{i=1}^{n} X_{i}^{2}. Denote by ℝ[X, Y] the polynomial ring in n + 1 variables X = X_{1}, …, X_{n}, Y and consider the finite set S′ = S ∪ {1 − pY, −(1 − pY)} in ℝ[X, Y]. Then K_{S′} consists of those points on the hypersurface

H = {(x, y) ∈ ℝ^{n+1} | p(x)y = 1}

in ℝ^{n+1} which map to K_{S} under the projection (x, y) ↦ x. Theorem 0.10 (‡)′_{S} holds.

Cylinders with compact base.

We continue to denote by ℝ[X, Y] the polynomial ring in n + 1 variables X_{1}, …, X_{n}, Y.

Consider a subset S = {g_{1}, …, g_{s}} of ℝ[X, Y] where the polynomials g_{1}, …, g_{s} involve only the variables X_{1}, …, X_{n}.

So K_{S} has the form K × ℝ, K ⊆ ℝ^{n}. We further assume that K is compact.

We describe this situation by saying that K_{S} is a cylinder with compact cross-section. In [K-M] we prove:

Theorem 0.11 If K_{S} is a cylinder with compact crosssection, then (‡)_{S} holds. More precisely, let f ∈ ℝ[X, Y] is such that f ≥ 0 on K_{S}. Let d ≥ 1 so that the degree of f as a polynomial in Y is ≤ 2d. Set

q(Y) := 3 + Y + 3Y^{2} + Y^{3} + … + 3Y^{2d} .

Then for all ϵ > 0, f + ϵq(Y) ∈ T_{S}.

Closed Polyhedra.

In [K-M-S] we develop a ”fiber criterion” for (‡) to hold on subsets of cylinders. In particular, we get an application to generalized polyhedra.

Assume that K_{S} is the basic closed semi-algebraic set in ℝ^{m}, m ≥ 1, defined by S = {ℓ_{1}, …, ℓ_{s}}, where ℓ_{1}, …, ℓ_{s} are linear, so K_{S} is a closed polyhedron. If K_{S} is compact then, by [J–P], (†) holds for M_{S}.

What if K_{S} is not compact?

If K_{S} contains a cone of dimension 2 then, by [K–M] (‡) fails for T_{S}.

In [K–M] we asked whether (‡) holds in the remaining case, i.e., when K_{S} is not compact and does not contain a cone of dimension 2.

In [K–M–S] we settle this question completely:

Theorem 0.12 Let P be a closed polyhedron in ℝ^{m} defined by a finite set S of linear polynomials.

(i) If P is compact then (†) holds for M_{S}. (ii) If P is not compact but does not contain a 2dimensional cone then (‡) holds for M_{S}. (iii) If P contains a 2-dimensional cone then (‡) fails for T_{S}.

The density condition.

All the previous examples, compact or not, satisfying one of the previous conditions considered, satisfy the density condition. In [Sc2], Schmüdgen gives other methods to produce examples where the density condition holds. In [K-M] we gave an intrinsic condition for the density condition to fail:

Theorem 0.13 The density condition fails whenever n ≥ 2 and K_{S} contains a cone of dimension 2.

In [P–S] a stronger intrinsic condition is given (if K_{S} contains a “nasty curve”then the density condition fails). The following example is particularly interesting: Example 0.14 Consider

K := {(x, y) ∈ ℝ^{2}: −1 ≤ (x^{2} − 1)(y^{2} − 1) ≤ 0}

in the plane ℝ^{2} = V (ℝ) (see figure 1).

Arguing using the Powers-Scheiderer condition, one shows now that K-moment problem is not finitely solvable.

Note however that the given set is very special; it displays interesting symmetries. This motivates the next section.

Special Situations.

Invariant Sets.

We can extend the results of the previous sections in another direction.

The idea is to fix a distinguished subset B ⊂ ℝ[X] and to attempt the various approximations only for polynomials in B. That is, we want to study the inclusions

T_{S} ∩ B ⊆ \overline{T_{S}} ∩ B ⊆ Psd(K_{S}) ∩ B .

In [C–K–S], we investigated the particularly privileged situation when B is the subring of invariant polynomials with respect to some action of a group on the polynomial ring ℝ[X].

Let us revisit the last example of the last section:

Example 0.15 K is G-invariant, where G = D_{4} the dihedral group of order eight acting on ℝ^{2} in the natural way (as the symmetry group of a square centered at the origin).

The ring of invariants is ℝ[x, y]^{G} = ℝ[u, v] with

u = x^{2} + y^{2}, v = x^{2}y^{2},

and the orbit variety W = ℝ^{2}//G is itself an affine plane.

The image of π: V (ℝ) → W (ℝ) is Z = π(ℝ^{2}) = {(u, v) ∈ ℝ^{2}: u ≥ 0, v ≥ 0, u^{2} ≥ 4v}.

Since (x^{2} − 1)(y^{2} − 1) = v − u + 1, we have

π(K) = {(u, v) ∈ ℝ^{2}: v ≥ 0, 1 ≤ u − v ≤ 2}. This is a (half-) strip in the (u, v)-plane (see figure 2):

The moment problem for π(K) is solved by the preordering N in ℝ[u, v] = W (ℝ) generated by v, u − v − 1 and 2 − u + v (by [K-M-S]). This means that the G-invariant K-moment problem is solvable (i.e. invariant linear functional non-negative on the finitely generated preordering is represented by an invariant measure).

Positive polynomials on fibre products.

Throughout this section, a real algebraic, affine variety V ⊆ ℝ^{d} is the common zero set of a finite set of polynomials.

The algebra of regular functions on V (the coordinate ring of V) is ℝ[V] = ℝ[X]/I(V), where I(V) is the radical ideal associated to V.

The non-negativity set of a subset S ⊂ ℝ[V] is

K(S) = {x ∈ V; f(x) ≥ 0, f ∈ S}.

Let I be a non-empty set, endowed with a partial order relation i ≤ j. A projective system of algebraic varieties indexed over I consists of a family of varieties (affine in our case) V_{i}, i ∈ I, and morphisms f_{ij} : V_{j} ⟶ V_{i} defined whenever i ≤ j, and satisfying the compatibility condition

f_{ik} = f_{ij}f_{jk} if i ≤ j ≤ k.

The topological projective limit V = proj.lim(V_{i}, f_{ij}) is the universal object endowed with morphisms

f_{i} : V ⟶ V_{i}

satisfying the compatibility conditions

f_{i} = f_{ij}f_{j}, i ≤ j.

A directed projective system carries the additional assumption on the index set that for every pair i, j ∈ I there exists k ∈ I satisfying i ≤ k and j ≤ k.

A finite partially ordered set I = {i_{0}, ..., i_{n}} is a rooted tree if the order structure is generated by the inequalities

i_{1} ≥ i_{0} and for every k > 1, i_{k} ≥ i_{j(k)} with j(k) < k.

In [K–P] We are concerned with finite projective systems of algebraic varieties. The main result is the following:

Theorem 0.16 Let (V_{i}, f_{ij}) be a finite projective system of real affine varieties, indexed over a rooted tree. Let Q_{i} ⊂ ℝ[V_{i}] be archimedean quadratic modules, subject to the coherence condition f_{ij}^{∗}Q_{i} ⊆ Q_{j}. Let p ∈ ∑_{i} f_{i}^{∗}ℝ[V_{i}] be an element which is positive on the set ∩_{i∈I}f_{i}^{−1}K(Q_{i}). Then p ∈ ∑_{i} f_{i}^{∗}Q_{i}.

We also consider fibre products of affine real varieties: Let Z = X_{1} ×_{Y} X_{2} be the fibre product of affine real varieties. Specifically

f_{i}; X_{i} ⟶ Y, i = 1, 2,

are given morphisms and

Z = {(x_{1}, x_{2}) ∈ X_{1} × X_{2}; f_{1}(x_{1}) = f_{2}(x_{2})}.

This is still an algebraic variety, with the ring of regular functions

ℝ[X_{1} ×_{Y} X_{2}] = ℝ[X_{1}] ⊗_{ℝ[Y]} ℝ[X_{2}].

Denote by u_{i} : Z ⟶ X_{i}, i = 1, 2, the projection maps, so that: f_{1}u_{1} = f_{2}u_{2}.

Proposition 0.17 With the above notation, let Q_{i} ⊆ ℝ[X_{i}], i = 1, 2, be archimedean quadratic modules. If an element p ∈ u_{1}^{∗}ℝ[X_{1}] + u_{2}^{∗}ℝ[X_{2}] is strictly positive on the set u_{1}^{−1}K(Q_{1})∩u_{2}^{−1}K(Q_{2}), then p ∈ u_{1}^{∗}Q_{1}+u_{2}^{∗}Q_{2}.

The proposition applies to the case of fibre products of affine spaces to recover a result of [L].

Specifically, let X_{1} = ℝ^{n_{1}} × ℝ^{m}, X_{2} = ℝ^{m} × R^{n_{2}} and Y = ℝ^{m}, while f_{1}, f_{2} are the corresponding projection maps onto Y. Denote by x_{1}, y, x_{2} the corresponding tuples of variables. Then one immediately identifies

Z = ℝ^{n_{1}} × ℝ^{m} × ℝ^{n_{2}}

and the proposition yields:

Corollary 0.18 Let Q_{x_{1},y}, Q_{y,x_{2}} be archimedean quadratic modules in the respective sets of variables. Let Π := (K(Q_{x_{1},y}) × ℝ^{n_{2}}) ∩ (ℝ^{n_{1}} × K(Q_{y,x_{2}})) ⊆ Z. If a polynomial p(x_{1}, y, x_{2}) = p_{1}(x_{1}, y)+p_{2}(y, x_{2}) is positive on Π, then p ∈ Q_{x_{1},y} + Q_{y,x_{2}}.

*******

The End

References

[C-K-M] J. Cimpric, S. Kuhlmann and C. Scheiderer: Sums of squares and moment problems in equivariant situations, submitted (2006).

[F] W. Fan: Non-negative polynomials on compact semi-algebraic sets in one variable case M.Sc. Thesis, Saskatoon (December 2006).

[J–P] T. Jacobi, A. Prestel: Distinguished representations of strictly positive polynomials, J. reine angew. Math. 532, 223–235 (2001).

[K-M-S] S. Kuhlmann, M. Marshall, N. Schwartz: Positivity, sums of squares and the multi-dimensional moment problem II, Adv. Geom. 5, 583-607, (2005).

[K–P] S. Kuhlmann – M. Putinar: Positive Polynomials

on Fibre Products, submitted (2006).

[L] J.B. Lasserre: Convergent semidefinite relaxations in polynomial optimization with sparsity, SIAM J. Optim. 17, 796-817, (2006).

[N] T. Netzer: Doublegagger not equivalent to moment problem, unpublished note (2006)

[P–S] V. Powers, C. Scheiderer: The moment problem for non-compact semialgebraic sets, Adv. Geom. 1, 71–88 (2001).

[P] M. Putinar: Positive polynomials on compact sets, Ind. Univ. Math. J. 42 (1993), 969–984 [S1] C. Scheiderer: Sums of squares of regular func-

tions on real algebraic varieties, Trans. Amer. Math. Soc. 352, 1030–1069 (1999)

[S2] C. Scheiderer: Sums of squares on real algebraic curves , Math. Zeit. 245 (2003), 725–760

[S3] C. Scheiderer: Distinguished representations of non-negative polynomials , J. Algebra 289 (2005), 558–573

[S4] C. Scheiderer: Sums of squares on real algebraic surfaces, Manuskripta Math. 119 (2006), 395–410

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

[Sc2] K. Schmüdgen: On the moment problem for closed semi-algebraic sets, J. reine angew. Math. 558, 225–234 (2003)