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

Question

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.

Answer 1

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 ?

Answer 2

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