lowerBound -- finds a lower bound for a polynomial

Synopsis

Usage:

(bound,sol) = lowerBound(f)

(bound,sol) = lowerBound(f,D)

(bound,sol,mult) = lowerBound(f,h,D)
Inputs:
- f, a ring element, a polynomial or a rational function
- D, an integer, degree bound for the SDP relaxation (optional)
- h, a matrix, row vector with polynomial entries (optional)
Optional inputs:
- RoundTol => ..., default value 3, tolerance for rational rounding
- Solver => ..., default value null, picking a semidefinite programming solver
- Verbosity => ..., default value 0, control the level of information printed
Outputs:
- bound, a lower bound on f
- sol, an instance of the type SDPResult,
- mult, a matrix, column vector with polynomial multipliers

Description

This method finds a lower bound for a polynomial or rational function $x\mapsto 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 => -.999994})

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 $h_1(x),...h_m(x)$, we can look for multipliers $l_i(x)$ such that $f(x) - t + \sum_i l_i(x) h_i(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 => .382683})
         4

o20 : Sequence

Ways to use lowerBound :

lowerBound(RingElement)
lowerBound(RingElement,Matrix,ZZ)
lowerBound(RingElement,ZZ)

For the programmer

The object lowerBound is a method function with options.

lowerBound -- finds a lower bound for a polynomial

Synopsis

Description

See also

Ways to use lowerBound :

For the programmer