This method finds a lower bound for a polynomial or rational function x↦f(x). More precisely, this method solves the following relaxation
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 |