How to efficiently minimize factored single variable polynomial?

Question

I have a factored single variable polynomial of degree $n$ with $n$ real roots (maybe not distinct). What will be the most efficient method to find the global minimum of such polynomial?

Answer 1

You are given $$f(x)=(x-a_1)(x-a_2)\cdots (x-a_n) $$ with $a_1\le a_2\le\ldots \le a_n$. We may assume $n$ is even, or else there is no global minimum. Local minima are between roots in intervals $(a_{2k-1},a_{2k})$, namely where $f$ is negative; we need to find these local minima and pick the lowest among them. Exception: If all $(a_{2k-1},a_{2k})$ are empty (i.e., all roots are of even multiplicity), then $f(x)\ge 0$ for all $x$ and the roots are precisely the minimizers, and we are done.

We have $$\tag1f'(x)=\sum_{i=1}^n\prod_{j=1\atop j\ne i}^n(x-a_j) $$ and look for roots of this in $(a_{2k-1},a_{2k})$. If one or both of $a_{2k-1},a_{2k}$ is of higher multiplicity $m_{2k-1}\ge2$ or $m_{2k}\ge2$, then it is also a root of $f'$ (or multiplicity $m_{2k-1}$ or $m_{2k}-1$). To avoid distraction, get rid of these and consider $$g(x)=\frac{f'(x)}{\prod_{i=1}^n(x-a_i)^{m_i-1}} $$ which doesn't really involve divisions but rather dropping a few factors from $(1)$. Now use any of the well-known methods to find zeres of $g$ in $(a_{2k-1},a_{2k})$. For example, the secant method works (because $g$ is non-zero at the interval ends) and avoids computation of $g'$.