Consider a convex function $f(x)$ of one variable $x$ on some interval $[a,b]$.
Question: What is known about the L1 approximation of $f(x)$ by piecewise linear functions? How to construct approximation for the prescribed number of nodes? Are there some algorithms and/or theoretical results?
Moreover let us impose additional conditions on approximation - as shown on figures below - values of approximation at nodes (and $a,b$) should be equal to values of $f(x)$, or saying in the other way: approximation should be pointwise less than or equal to the function.
Geometrically it means that we need to find a piecewise linear curve such that the area under it is most close to area under $f(x)$, in the other words areas of sectors are minimal.
If one needs to find only one node one easily derives a clear geometric solution - to place node at point $x$ where tangent is parallel to the chord between $f(a)$ and $f(b)$. (See figure 1). If we have many points it gives condition connecting node with neighbouring nodes, so one might think about nodes as about some system with pairwise interaction.
I have some dynamic programming algorithm, but I guess much should be known.
Figure 1: Red - best one-node approximation - node at point where tangent is parallel to chord
Figure 2: Approximation with two nodes
