# approximate convex upper envelope for a convex function

by Mathexx   Last Updated September 11, 2019 17:20 PM

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.

Tags :

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.

gerw
September 11, 2019 17:18 PM

## Related Questions

Updated June 03, 2017 00:20 AM

Updated November 19, 2018 05:20 AM

Updated April 28, 2018 19:20 PM

Updated August 23, 2019 10:20 AM

Updated August 22, 2017 02:20 AM