Most studies and literature try to find the convex lower envelope of a convex function. I wonder if there are good references for quantifying the "best" convex upper envelope. I came up with this reference request due to the following problem
Suppose $y=f(x)$ is a convex function on a polytope $\mathcal{X}\subset\mathbb{R}^n$. I have a large number of samples $(x_1,y_1),...,(x_m,y_m)$ which includes the vertices of $\mathcal{X}$. Then, I try to construct the best convex piece-wise affine function (i.e., $y=\max_{l\in L} a_l^Tx+c_l$) such that all the points are on the function. It can be deducted that this function will be a convex upper envelope of $f(x)$.
For $n=1$, this is straightforward. But for higher dimension $n$, is there an efficient way to do this? Any reference suggestions or proof hints are very welcome.
You can take the convex hull of the point set $\{(x_i,y_i)\} \subset \mathbb R^{n+1}$. The 'lower part' (w.r.t. the last coordinate) of this polytope gives your convex, piecewise affine function.