next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
SumsOfSquares :: lowerBound

lowerBound -- finds a lower bound for a polynomial

Synopsis

Description

This method finds a lower bound for a polynomial or rational function x↦f(x). More precisely, this method solves the following relaxation

max   t     s.t.     f(x) - t   is SOS

In some cases the minimizer can be extracted with the method recoverSolution.

i1 : R=QQ[x];
i2 : f = (x-1)^2 + (x+3)^2;
i3 : (bound,sol) = lowerBound(f);
i4 : (bound, recoverSolution sol)

o4 = (8, {x => -.999805})

o4 : Sequence
i5 : f - bound == sosPoly sol

o5 = true

By default the method tries to obtain a rational lower bound. Since there is a trade-off between rounding and optimality, we specify the rounding precision as an optional input argument.

Quotient rings: Given an ideal I, we can also find a lower bound for f on the variety of I. This can be done by constructing the associated quotient ring. A degree bound must be provided.

i6 : R = QQ[x,y]/ideal(x^2 - x, y^2 - y);
i7 : f = x - y;
i8 : (bound,sol) = lowerBound(f,2);
i9 : bound

o9 = -1

o9 : QQ
i10 : f - bound == sosPoly sol

o10 = true

Avoiding quotient rings: Constructing the quotient ring is sometimes too expensive since it requires Gröbner bases. There is an alternative (though weaker) relaxation that avoids Gröbner bases computation. Given equations h1(x),...hm(x), we can look for multipliers li(x) such that f(x) - t + ∑i li(x) hi(x) is a sum of squares.

i11 : R = QQ[x,y];
i12 : f = x - y;
i13 : h = matrix{{x^2 - x, y^2 - y}};

              1       2
o13 : Matrix R  <--- R
i14 : (bound,sol,mult) = lowerBound (f, h, 2);
i15 : bound

o15 = -1

o15 : QQ
i16 : f - bound + h*mult == sosPoly sol

o16 = true

Optimizing rational functions: The following is an example of how to optimize a rational function.

i17 : R = QQ[x];
i18 : f = (x^2-x)/(x^2+1);
i19 : (bound,sol) = lowerBound (f);
i20 : (bound, recoverSolution sol)

         1
o20 = (- -, {x => .353553})
         4

o20 : Sequence

See also

Ways to use lowerBound :