Determining whether a polynomial is monotonic on a given interval $I$

Question

Consider a regression/data fitting problem with polynomials. We have an extra constraint that the solution must be monotonic. So I have the following questions:

• For a given polynomial, how to efficiently determine if it is monotonic (at least in a given interval)?
• Furthermore, how to impose the monotonic constraint (again at least in a given interval)?

Thanks a lot in advance!

Answer 1

A polynomial $p(x)$ is monotonic on an interval $I$ iff its derivative $p'(x)$ is everywhere nonnegative or everywhere nonpositive on $I$, or equivalently if all of the roots of $p'(x)$ in the interior of the interval have even order.

As an manually workable example, consider a generic cubic polynomial $$p(x) := Ax^3 + Bx^2 + Cx + D.$$ Differentiating gives $$p'(x) = 3A x^2 + 2B x + C,$$ and (henceforth provided that $A \neq 0$) this has no real roots if $$\Delta := (2B)^2 - 4(3A)(C) = 4(B^2 - 3 A C)$$ is negative and a real double root if $\Delta = 0$. If $\Delta > 0$ then $p'$ has two single roots.

So, $p$ is monotonic on $\mathbb{R}$ iff $\Delta \leq 0$. On an interval $I$, $p$ is monotonic iff either (1) $\Delta \leq 0$ or (2) $\Delta > 0$ and neither of the roots of $p'$ (which can be computed with the quadratic formula) are contained in the interior of $I$.

Answer 2

A little late to the party but I'd like to add my answer for anyone who happens to stumble upon this.

1. To determine if the polynomial $p(x)$ is monotonic on the interval $[a,b]$:

Calculate the derivative $p^{\prime}(x)$ and its real roots in the desired interval, namely the points $x^{*} = \{x \in [a,b]:p^{\prime}(x)=0\}$. If all roots in $x^{*}$ have even multiplicity or $x^{*}$ is empty then the polynomial is monotonic. This also works for monotonicity over the entire real line. You will need to check at least one value of $p^{\prime}(x)$ in $[a,b]$ to determine if it is monotonically increasing or decreasing. I'm currently working on a package for constrained regression (very early stages) and have this coded up in R here.

2. There are several methods for fitting monotone polynomials to data:

Currently the best available is an R package called MonoPoly, see here. The MonoPoly package works by using a parameterisation of the polynomial which enforces monotonicity of a region. I'll update this answer with my work when it is more refined.

UPDATE: Fit monotone polynomial (and mixed effects models) with gcreg.

Answer 3

It looks like someone else had your problem (monotone approximation) and labeled it as "nontrivial" in this paper which proves a theorem related to your problem, but I can't figure out the implications for you.