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.

Answers 1

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.

September 11, 2019 17:18 PM

Related Questions

Updated June 03, 2017 00:20 AM

Updated April 28, 2018 19:20 PM

Updated August 23, 2019 10:20 AM

Updated August 22, 2017 02:20 AM