5
$\begingroup$

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!

$\endgroup$

4 Answers 4

3
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ I don't think determining positivity/negativity of the derivative (which can be an arbitrary polynomial here) will be very efficient. Not that I immediately know if there is a better way or not. $\endgroup$ Sep 10, 2014 at 6:20
  • $\begingroup$ Some root finders converge very quickly, but of course whether this is efficient enough depends on what the OP has in mind; to be clear one doesn't always need to find a root of $p'$ (though this is very cheap for $\deg p < 3$), one only needs to detect a change in sign. If one knows more about the polynomials and intervals or has some tolerance for deviations from monotonicity (e.g., if one is still happy with $x_1 > x_0 \implies f(x_1) > f(x_0) - \epsilon$ for some fixed $\epsilon$) one can probably improve efficiency. $\endgroup$ Sep 10, 2014 at 11:59
  • $\begingroup$ Where did the $x$'s go in your derivative? $\endgroup$ Apr 21, 2016 at 1:19
  • $\begingroup$ @LoveTooNap29 I'm not sure---thanks for the catch! Unfortunately the error carried over to the formula for $\Delta$, which should now be correct. $\endgroup$ Apr 21, 2016 at 12:17
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

  1. 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.

$\endgroup$
-1
$\begingroup$

Travis is right, hobs is mistaken I'm afraid. When the roots of the derivative have even multiplicity but are real, there exist values of which the derivative is strictly negative and values of which it is strictly positive. So your polynomial is not monotonic. I think hobs thinks about the matrix of which the derivative is the characteristic equation. Then the roots are the eigenvalues, and the matrix is definite.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .