I encountered this problem in my research and it is turning out to be a surprisingly difficult one(for me, at least). 

Suppose we have a univariate nonlinear function $f(x)$ where $x \in [L,U]$. Our goal is to approximate this nonlinear function with $n$ piecewise-continuous linear functions $g_{i}(x)$ within the given domain. We assume that $n$ is a pre-specified number. We define each line segment as follows:
$$
g_{i}(x) = \frac{f(a_{i}) - f(a_{i-1})}{a_{i} - a_{i-1}} (x - a_{i-1}) + f(a_{i-1})\text{ for }a_{i-1} \leq x \leq a_{i}
$$
where $a_{i}$ are knot points in $[L,U]$ and $i = 1,\ldots,n$. The first and the last knot points are fixed at the boundaries, that is, $a_{0} = L, a_{n} = U$. Also, the knot points are ordered: $ a_{i} \geq a_{i-1}$ for $i=1,\ldots,n$.

I want to find the optimal placements for the knot points $a_{1},\ldots,a_{n-1}$, such that the overall squared-approximation error $e$ is minimized. We can pose the objective as follows:
$$
\min_{a_{1},\ldots,a_{n-1}} \left\{ e = \int_{L}^{U} [f(x) - g_{i}(x)]^2 dx \right\}
$$

This picture illustrates the problem:
![Piecewise Linear functions][1]

The final optimization problem looks like the following (after a simple reformulation into a optimal-control-like form):
$$
\begin{align*}
&\min_{a_{1},\ldots,a_{n-1}}  e(U)\\
s.t.\quad & \frac{de(x)}{dx} =  [f(x) - g_{i}(x)]^2, \quad e(L) = 0\\
&g_{i}(x) = \frac{f(a_{i}) - f(a_{i-1})}{a_{i} - a_{i-1}} (x - a_{i-1}) + f(a_{i-1})\text{ for }a_{i-1} \leq x \leq a_{i}\\
& a_{0} = L, a_{n} = U\\
& a_{i} \geq a_{i-1},\quad i=1,\ldots,n
\end{align*}
$$
This optimization problem is extremely difficult to solve numerically, owing to its nonsmoothness and nonconvexity. 

Question: How do I solve this problem to global optimality? Can anyone provide any attacks (even partial ones)? Any simplifying properties?


  [1]: http://dl.dropbox.com/u/6809582/linearfunctions.png