Computing real minima of positive univariate polynomials (of degree $\le 6$)

Question

Let $p : \mathbb R \rightarrow \mathbb R$ be a non-constant positive polynomial with $\deg(p) \leq 6$. We know that $p$ has between $1$ and $3$ minima. How can an approximation to the global minimum be found numerically?

This problem occurs naturally when trying to compute the closest point to a cubic spline.

The approaches I've seen so far all solve the generic quintic equation $p'(t) = 0$. But this gives up a lot of structure, since now we're computing (up to) $5$ roots instead of $3$. Are there any numerical methods more tailored to this kind of situation?

The kind of structure I'm thinking of: since we know that if $t$ is a minimum and $p''(t) \geq 0$ at any local minimum, we could factor the (non-constant, leading coefficient positive) quartic $p''(t)$ and obtain (up to) $3$ intervals where the roots must lie, where only one interval can be finite.

Answer 1

This doesn’t answer the question you asked, but it might solve the problem that motivated your question.

Here’s what I’d do to find the closest point on a cubic curve …

1. Calculate $n$ points on the curve, and use these to construct a polyline approximation.
2. Find the closest point on the polyline, and it’s corresponding parameter value, $t$.
3. Do $m$ iterations of Newton-Raphson to polish the value of $t$.

Suggested values are: $n$ should be 3 to 10 times the degree of the curve, and $m$ should be 3 or 4. You’ll need to change those values to match your speed/accuracy/reliability requirements.

All of this should work fine on a GPU.