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.

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.

Updated November 19, 2018 05:20 AM

Updated April 28, 2018 19:20 PM

- Serverfault Query
- Superuser Query
- Ubuntu Query
- Webapps Query
- Webmasters Query
- Programmers Query
- Dba Query
- Drupal Query
- Wordpress Query
- Magento Query
- Joomla Query
- Android Query
- Apple Query
- Game Query
- Gaming Query
- Blender Query
- Ux Query
- Cooking Query
- Photo Query
- Stats Query
- Math Query
- Diy Query
- Gis Query
- Tex Query
- Meta Query
- Electronics Query
- Stackoverflow Query
- Bitcoin Query
- Ethereum Query