# How to restrict coefficients of polynomial, so the function is strictly monotonic?

I need to restrict the degree of freedom of the coefficients of a polynomial, so the function is always strictly monotonic in the domain $$x\in\left[0, 1\right]$$ and $$y\in\left[0, 1\right]$$. The polynomial also has to go through the points $$(0, 0)$$ and $$(1, 1)$$.

The general formula for a polynomial of degree 3 is

$$a_3\cdot x^3 + a_2\cdot x^2 + a_1\cdot x + a_0\quad .$$

The constraints $$f(0) = 0$$ and $$f(1) = 1$$ give

$$a_0 = 0$$

and

$$a_3 = 1 - a_2 - a_1$$

yielding the fitted polynomial

$$(1 - a_2 - a_1)\cdot x^3 + a_2\cdot x^2 + a_1\cdot x\quad .$$

The number of parameters is already reduced to 2, but I also need the function to be strictly monotonic, so $$f'(x) \geq 0$$. The additional constraints $$f'(0) \geq 0$$ and $$f'(1) \geq 0$$ give

$$a_1 \geq 0$$

and

$$a_2 \leq 3 - 2\cdot a_1$$

but this does not imply $$f'(x) \geq 0$$ in general. Is there a simple way to achieve what I want, even for the general case, where the degree of the polynomial is not restricted to 3 and can be any integer number?

As a result, I want to choose the coefficients of the polynomial according to some constraints and the function is always strictly monotonic, includes the points $$(0, 0)$$ and $$(1, 1)$$ and is inside the unit square (see curves).

EDIT: I performed a Monte Carlo simulation to determine the constraints graphically (see monte carlo). The black lines correspond to

$$a_1 \geq 0$$

and

$$a_2 \leq 3 - 2\cdot a_1\quad .$$

The rest looks elliptic to me. All dots inside the yellow area give monotonic increasing functions (see array of curves).

EDIT2: The accepted answer is correct. See the visual proof.

• IN the last sentence, you mean the unit square (not cube), right? – Mark Fischler Feb 27 '19 at 16:50
• Indeed, thats what I meant. – Yannick Feb 28 '19 at 7:48
• @Yannick - Nice graph. Always fun to see abstract reasoning sync up with simulation. – JonathanZ supports MonicaC Feb 28 '19 at 19:04
• Do you know what's going on with the portion of the yellow region that lies outside of the ellipse? – JonathanZ supports MonicaC Feb 28 '19 at 19:07
• @JonathanZ My guess is the following: requiring the discriminant of the derivative to be negative gives monotonic solutions on the whole domain $x\in \mathbb{R}$. I need the polynomial only monotonic for $x\in [0, 1]$. The derivative is allowed to be negative for $x < 0$ and $x > 1$. This should correspond to the yellow region outside the ellipse. – Yannick Mar 1 '19 at 9:06

The $$n=3$$ case is tractable: Your polynomial is increasing if the derivative is always positive, so it's enough to show that it is never zero. (Never zero means it has the same sign everywhere, $$f(0) < f(1)$$ ensures that that sign is positive.) Since the derivative is a quadratic, having no zeros is equivalent to its discriminant being negative:$$(2a_2)^2 -4\cdot 3 \cdot (1-a_2-a_1)\cdot a_1 \leq 0$$ I'd bet that that's the ellipse you're seeing in your simulation.

Unfortunately I can't see any way for this to generalize to $$n >3$$.

edit - I have changed the condition to include 0, a simple counterexample to the strict inequality is the polynomial $$4*(x-1/2)^3 + 1/2$$.

• This answer is wrong. The condition is that the derivative is never negative in the range $[0,1]$ and that is very different. – Mark Fischler Feb 28 '19 at 16:16
• This answer is correct. Thank you very much. – Yannick Feb 28 '19 at 17:30
• @Yannick: You're welcome. And while I usually don't like asking for votes, right now this answer is at -1, which doesn't seem right for an answer that's been accepted by the original poster. (I'm not 100% sure but I think Mark is pointing out the (valid) distinction between "always positive" and "never negative", but it doesn't matter in the case of a quadratic like we have here.) – JonathanZ supports MonicaC Feb 28 '19 at 19:01
• @JonathanZ I already up-voted, but apparently it doesn't count as I am a new user :( – Yannick Mar 1 '19 at 8:57
• Because the zeroes (roots) of nonconstant polynomials are "isolated" (even when roots have multiplicity greater than one), a nonconstant polynomial is a strictly increasing function on any closed interval where its derivative is nonnegative (for example, $y=x^3$). In terms of determining a region of coefficients where this holds, it doesn't make much of a difference. – hardmath Mar 11 '19 at 2:16

I assume that you have $$n$$ data points $$(x_i,y_i)$$ that you want to fit (probably in the least-square sense) according to the model $$y(x)=a_3\, x^3 + a_2\,x^2 + a_1\, x + a_0$$ with a bunch of constraints.

As you wrote, the first ones $$y(0)=0$$ and $$y(1)=1$$ are simple and allow to make $$a_0=0\qquad \text{and} \qquad a_3=1-a_2-a_1$$ Then, as you wrote, the model is now reduced to $$y=(1-a_2-a_1)\,x^3+a_2\,x^2+a_1\,x$$ However the constraints on the derivative should be $$n$$ $$y'(x_i)=3(1-a_2-a_1)\,x_i^2+2a_2\,x_i+a_1 >0\qquad \forall i=1,2,\cdots,n$$

So, you face an optimization problem with $$n$$ inequality constraints; this not very difficult.

May I suggest you post a series of data points I could work with ?

• Actually, I don't have data points and I don't want to perform an optimization. I want to determine constraints on $a_2$ and $a_1$ analytically, so for every choice the polynomial is strictly increasing. It would be perfect to derive a solution for the general case with arbitrary degree $n$. – Yannick Feb 28 '19 at 7:55