Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, i.e. $u_g$ is piecewise affine and $u_g(x_i)=g_i$ for $1\le i\le n$. Denote by $u_g^c$ the concave envelope of $u_g$ on $[x_1,x_n]$, namely,
$u_g^c:[x_1,x_n]\to\mathbb R$ is concave and $u_g^c\ge u_g$ on $ [x_1,x_n]$;
For any concave function $f\ge u_g$, one has $f\ge u_g^c$.
Given some $x^*\in [x_1,x_n]$, define $L:\mathbb R^n\to\mathbb R$ by $L(g):=u_g^c(x^*)$. Then it follows easily by definition that $L$ is convex on $\mathbb R^n$. My question is the following:
Is there a closed formula or a (efficient) numerical scheme to compute $L(g)$?
Is there a closed formula or a (efficient) numerical scheme to compute the sub-gradient $\nabla L(g)$?
I am interested in solving the minimisation problem $\inf_{g\in\mathbb R^n}L(g)$. It seems a very elementary question in convex optimisation or linear programming, but I can not find a suitable reference.
Any answer, remark or reference suggestion would be much appreciated! Thanks a lot!
