Determining whether a polynomial is monotonic on a given interval $I$ 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!
 A: 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$.
A: 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. 
A: A little late to the party but I'd like to add my answer for anyone who happens to stumble upon this.


*

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


*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. 
A: 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.
