I am looking for the optimal piecewise linear upper bound for a single variable function $f(x)$ - specified as a list of $(x,f(x))$ pairs. So, I have $(x_1,f(x_1)),(x_2,f(x_2)), \ldots, (x_n,f(x_n))$.
- The piecewise approximation cannot have more than $L$ linear components, where $L$ is fixed number. I can solve the least squares fit via a dynamic programming problem, but not sure how it can be extended to upper bound.
- Is there a way to regularize the problem so that I do not end up with large number of small line segments?