next | previous | forward | backward | up | index | toc

# 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 polynomial or a rational function
• D, an integer, degree bound for the SDP relaxation (optional)
• h, , 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, , 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