next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
SOS :: 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);
Executing CSDP
Input file: /tmp/M2-2520684-0/4.dat-s
Output file: /tmp/M2-2520684-0/5
Status: SDP solved, primal-dual feasible
Start rational rounding
i4 : bound

o4 = 8

o4 : QQ
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);
Executing CSDP
Input file: /tmp/M2-2520684-0/8.dat-s
Output file: /tmp/M2-2520684-0/9
Status: SDP solved, primal-dual feasible
Start rational rounding
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 SOS.

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);
Executing CSDP
Input file: /tmp/M2-2520684-0/12.dat-s
Output file: /tmp/M2-2520684-0/13
Status: SDP solved, primal-dual feasible
Start rational rounding
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);
Executing CSDP
Input file: /tmp/M2-2520684-0/16.dat-s
Output file: /tmp/M2-2520684-0/17
Status: SDP solved, primal-dual feasible
Start rational rounding
i20 : (bound, recoverSolution sol)

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

o20 : Sequence

See also

Ways to use lowerBound :