Quadratic least squares can be used to fit a quadratic curve to $3$ or more points, such that the resulting curve is the quadratic curve that has the least squared distance of the data points to the resulting curve.
Is there a way to do the same but with the restriction that the resulting curve is monotonic over a specific range? Like being monotonic in $[0,500]$ for instance. The data set itself is monotonic over the same range.
One thing that's come to mind is to do a regular fit and then adjust the result to have positive derivatives. While that would technically be a fit, I don't think it'd be optimal.
I've also thought about maybe doing some gradient descent to find a good fit, but I'm really hoping to find something like least squares, which is a constant time algorithm that doesn't get caught in local minima.
I specifically am trying to fit a monotonic quadratic curve to three data points, so any other technique that does the same would also be useful.
I'm looking to understand and implement this, so I'm looking for the information about how to do it, instead of being pointed at any software that might be able to do it for me.
Thank you!
Best Answer
If I understand correctly, you have a set of points $\{ (x_i, y_i) \}_{i \in [n]}$ and would like to find a monotonic segment of a parabola that is "close" to them. Assuming that the parabola is of the following form $$y = a x^2 + b x + c$$ where $a \neq 0$, then the extremum is attained at $\bar x := -\frac{b}{2a}$. Hence, when solving the least-squares problem, append the inequality constraint
$$\bar x \leq \min_{i \in [n]} \{ x_i \}$$
or the the inequality constraint
$$\bar x \geq \max_{i \in [n]} \{ x_i \}$$
Try each of them and find which one yields the lowest least-squares "cost".