1
$\begingroup$

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!

$\endgroup$
12
  • 1
    $\begingroup$ A quadratic curve is a parabola, and none of those are monotonic. Maybe you have some different concept in mind – what do you really mean when you write, "monotonic"? $\endgroup$
    – Gerry Myerson
    Mar 25, 2019 at 3:34
  • $\begingroup$ @GerryMyerson good point. I mean monotonic within a range. Updated the question. $\endgroup$
    – Alan Wolfe
    Mar 25, 2019 at 3:38
  • $\begingroup$ @RodrigodeAzevedo i could, and i'm betting the best fit curve does that, but how do i calculate where to put it, for the best fit? $\endgroup$
    – Alan Wolfe
    Mar 25, 2019 at 3:38
  • $\begingroup$ @Rod, no, OP didn't mention the word, "restriction", but edited it in after my comment. $\endgroup$
    – Gerry Myerson
    Mar 25, 2019 at 3:40
  • 1
    $\begingroup$ BTW, proof: wolframalpha.com/input/?i=quadratic+fit+(0,1),(1,2),(2,10) $\endgroup$
    – Alan Wolfe
    Mar 25, 2019 at 13:14

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ I'm not sure how to apply an inequality constraint to least squares. Is that something that can be explained easily? $\endgroup$
    – Alan Wolfe
    Mar 25, 2019 at 3:55
  • $\begingroup$ Least-squares is an optimization problem. The nice, simple case has no constraints. In this case, we have an inequality constraint. This makes the optimization problem much harder. Fortunately, numerical optimization can handle these constraints. If you use Python, try CVXPY (note that the code example on the main page is least-squares with inequality constraints). $\endgroup$
    – Rodrigo de Azevedo
    Mar 25, 2019 at 3:58
  • $\begingroup$ Something simpler (but more restrictive) would be to replace the $\leq$ or $\geq$ with $=$. Handle the resulting equality constraint using, say, Lagrange multipliers. No need for numerical solvers. $\endgroup$
    – Rodrigo de Azevedo
    Mar 25, 2019 at 4:01
  • $\begingroup$ I was specifically trying to avoid numerical methods, so thanks a bunch! $\endgroup$
    – Alan Wolfe
    Mar 25, 2019 at 4:03
  • 1
    $\begingroup$ You have a convex quadratic program. Hence, if you find a minimizer, it should be unique and yield the global minimum. Whether you like the fit or not is another story. Assuming no mistakes, of course. $\endgroup$
    – Rodrigo de Azevedo
    Mar 25, 2019 at 17:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .