Say I have identified a limit that approaches the bounded maximum value of a polynomial (with rational coefficients) to arbitrary precision.
An example such limit is:
$lim_{k->\infty} ((\int_a^b (f(x) + m)^k dx)^{(1/k)})$
Where:
- f(x) is a polynomial in x
- a,b are the bounds of the region of interest,
- m is any value larger than the minimum value of f(x) in the bounded region.
For example, plugging in $f(x) = 25 - x^2, n=1000, m=500, a=-10, b=-10$ and evaluating on wolfram alpha:
(1000th root of (definite integral from -10 to 10 of (25 - x^2 + 500)^1000))-500 $\approx 25.13 \approx 25 $
I now want to turn the approximation of this limit into an algorithm for bounded extremum finding and understand how it compares with existing approaches. For this example, with a fixed (but potentially astronomically large) k and m, I would expect the integral could be calculated and evaluated in time roughly O(kn), where n is the length of the initial polynomial. (Roughly: total number of bits in rational coefficients)
How does this compare to other algorithms which compute global maxima within some range? What is the best known big-O() for this calculation?
I am aware of two general methods competing with this oracle: gradient descent and factoring/root finding.
Gradient descent afaik cannot guarantee convergence beyond a local extremum, does this differ when restricted to polynomials?
How fast are factoring/root finding techniques?
Are there any other numerical techniques for this case?