I have a function $f$ I'd like to determine numerically and I have a bunch of $(x, y)$ pairs which approximate the function in the following sense: all of the points satisfy $f(x) \leq y$, most of the points have $f(x) = y$ (at least to the accuracy I need), a few of the points have $y$ significantly bigger than $f(x)$. (The points come from a simulated annealing which occasionally fails.)
I believe that $f$ can be well approximated by a low-order polynomial, so I'd like to find such which lies below all of the points and which hits as many as possible, but does not mind missing a few. That's a rather woolly thing to want, so I guess I should look for the largest which lies below all of the points, where largest would be with respect to the $L^p$ norm, say $p = 1$ of $2$, on an interval containing all of the $x$s.
Any pointers or references on how to find such a polynomial would be much appreciated.