1
$\begingroup$

I am looking for an algorithm that fits a parabola to a set of data points. However, no data point may be below the parabola. All points must be above the parabola. Is there an standard algorithm for finding that parabola?

This is a 2D problem. I have about 20 points.

$\endgroup$
  • 1
    $\begingroup$ Your problem is underspecified. There are infinitely many parabolas that lie below your data points. Which one do you want? $\endgroup$ – Wolfgang Bangerth Jul 11 '16 at 20:50
  • $\begingroup$ The one that fits the data points best, e.g. minimizes the error of the parabolic regression. $\endgroup$ – ManuelAtWork Jul 12 '16 at 6:04
  • $\begingroup$ @ManuelAtWork by the way, if you decide any answers below solve your problem you have, you should accept them as the answer to your question. If not, you should add more information as to what you might still need answered. $\endgroup$ – spektr Jul 13 '16 at 21:36
3
$\begingroup$

Choward already sketched a good approach, I am just going to elaborate.

So the equation for a parabola in the plane $\mathbb{R}^2$ is given by the zero locus of a quadratic equation $$f_a(x,y) = a_{11}x^2 + a_{12}xy + a_{22}y^2 + a_{1}x + a_{2}y + a_{0} = 0,$$ where $a = (a_{11}, a_{12}, a_{22}, a_{1}, a_{2}, a_{0}) \in \mathbb{R}^6$ is the vector of unknown coefficients. However, in gnereal such equation can describe any conic sections, such as a hyperbola, an ellipse and can even degenerate to a pair of striaght lines (that happens whenever the plynomial $f_a(x,y)$ is reducible). To make sure you get a parabola, you need to impose the restriction $g(a) = a_{12}^2 - 4 a_{11} a_{22} = 0$ (and to make sure the polynomial is irreducible). If you want all of your sample points $(x_j,y_j), \,\,\, j=1,...,N$ to be above the parabole, you simply have to impose also the linear with respect to $a$ restriction $l_j(a) = f_a(x_j,y_j) \geq 0$ for all $j=1,...,N$ as well as let's say $a_{11} \geq 0$. Now take the least square functional $$J(a) = \sum_{j=1}^{N} \left(f_a(x_j,y_j)\right)^2$$ which is a quadratic (so convex) function of $a \in \mathbb{R}^6$ and find its minimum on the set of restrictions $$R = D \cap A$$ where $$D = \{a \in \mathbb{R}^6 \, :\, l_j(a) = f_a(x_j,y_j) \geq 0 ,\, a_{11}\geq 0 \}$$ $$A = \{a \in \mathbb{R}^6 \, :\, g(a) = a_{12}^2 - 4 a_{11} a_{22} = 0\}.$$ In order to do that, you can form the Lagrange multiplier cost function $$L(a,\lambda) = J(a) + \lambda g(a)$$ and look for its minimum on the convex polyhedral set (e.g. a set determined by linear inequalities like in our case) $$P = \{(a,\lambda) \in \mathbb{R}^6 \times \mathbb{R} \, :\, l_j(a) = f_a(x_j,y_j) \geq 0 ,\, a_{11}\geq 0\} = D \times \mathbb{R}.$$ This is a convex probelm with quadratic cost function $L$ and linear restricitions $P$, so I beleive most programing languages would have standard functions that would solve this kind of calculus problem: find the minimum of $L(a,\lambda)$ on $P$. I think one can simplify the whole thing by taking $a_{11} = 1$.

In the case of a parabola given by $y = f_a(x) = a_{11} x^2 + a_1 x + a_0$ you simply have $f_a(x,y) = f_a(x) - y$ and $g(a) \equiv 0$ so the problem simplifies significantly and there is no need for Lagrange multipliers.

$\endgroup$
1
$\begingroup$

I have never heard of the need for solving a problem like this, so I am unsure if there's a standard algorithm for your question. Without the need to have points above the parabola, this problem would be a typical least square problem. But due to your constraint, you need to formulate the problem differently.

I think there's a number of ways one might approach this, but one idea I have is to formulate the problem as the following:

$$ J(\vec{\beta}) = \frac{1}{2N}\sum_{i=1}^{N}\lbrace \delta_i^2 + \gamma\max(\delta_i,0)^2\rbrace$$ where $$ \delta_i = f(x_i,y_i, \vec{\beta}) - z_i$$ $$ \vec{\beta} = \left[\beta_1, \beta_2, \beta_3,\beta_4, \beta_5, \beta_6\right]^{T} $$ $$ f(x,y,\vec{\beta}) = \beta_1 + \beta_2x + \beta_3 y + \beta_4 x^2 + \beta_5 y^2 + \beta_6 x y $$

and where $\gamma$ is a coefficient that amplifies a penalization term for when the current parabola fit has data points that fall below it. Based on this formulation, you can try to minimize $J(\vec{\beta})$ with respect to $\vec{\beta}$ through some iterative optimization procedure.

$\endgroup$
  • $\begingroup$ Thank you! Yes, one can look at the problem from a least squares perspective. Another approach would be searching for a local convex hull with parabolic shape. I want a regression that minimizes the deltas but is always 'conservative' from a structural engineer's point of view. $\endgroup$ – ManuelAtWork Jul 12 '16 at 6:03
  • $\begingroup$ I have implemented your modified least square approach. It works well for a suitable penalty factor. Btw, the factor 1/(2N) can be omitted (float divisions are expensive). $\endgroup$ – ManuelAtWork Jul 12 '16 at 9:13
  • $\begingroup$ @ManuelAtWork yes conceptually a convex hull with parabolic shape would be nice, but obviously a normal convex hull algorithm won't generate a parabaloid fit. It will just generate a graph connecting points $\endgroup$ – spektr Jul 12 '16 at 14:00
  • $\begingroup$ @ManuelAtWork I am surprised you think dividing the resulting sum by 2N is expensive, but either way you can get a good result without it. This factor is really to make the cost function perceived as the "average" modified error. Anyway, glad you have seen good results. $\endgroup$ – spektr Jul 12 '16 at 14:02
  • $\begingroup$ @choward: Is it obvious that the result is a parabola and not another conic section like a ellipse or hyperbola? $\endgroup$ – Futurologist Jul 12 '16 at 17:53

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.