1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ IN the last sentence, you mean the unit square (not cube), right? $\endgroup$ – Mark Fischler Feb 27 at 16:50
  • $\begingroup$ Indeed, thats what I meant. $\endgroup$ – Yannick Feb 28 at 7:48
  • $\begingroup$ @Yannick - Nice graph. Always fun to see abstract reasoning sync up with simulation. $\endgroup$ – JonathanZ Feb 28 at 19:04
  • $\begingroup$ Do you know what's going on with the portion of the yellow region that lies outside of the ellipse? $\endgroup$ – JonathanZ Feb 28 at 19:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Yannick Mar 1 at 9:06
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This answer is wrong. The condition is that the derivative is never negative in the range $[0,1]$ and that is very different. $\endgroup$ – Mark Fischler Feb 28 at 16:16
  • $\begingroup$ This answer is correct. Thank you very much. $\endgroup$ – Yannick Feb 28 at 17:30
  • $\begingroup$ @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.) $\endgroup$ – JonathanZ Feb 28 at 19:01
  • 1
    $\begingroup$ @JonathanZ I already up-voted, but apparently it doesn't count as I am a new user :( $\endgroup$ – Yannick Mar 1 at 8:57
  • $\begingroup$ 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. $\endgroup$ – hardmath Mar 11 at 2:16
1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Yannick Feb 28 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.