Given a simplex in $\mathbb{R}^n$ and a smooth function $f\mapsto\mathbb{R}$ with bounded $f''$, how can I quickly and simply obtain a rough estimate of a lower bound of $f$ (in the simplex) from $x_i$ (the vertices of the simplex) and $y_i=f(x_i)$?
I suppose I could assume an upper bound on $f''$ and then fit a maximally concave-up quadratic to the simplex's vertices. However I would prefer something simpler and quicker (even if not as tight) as this is to be used just as a heuristic in multiple simultaneous Nelder-Mead searches to gauge how promising each simplex is and therefore on which branch of the search to invest processing.
Edit:
I'm hoping for an expression about as simple as this:
$y_{min}+Kd^2$ where K is upper bound on $f''$ and $d$ is some simple distance based on separation between $x_i$ (e.g. min distance, max distance, mean distance, RMS distance, or something).