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 => .353553}) 4 o20 : Sequence |
The object lowerBound is a method function with options.