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 and unique: $ a_{i} > 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 http://dl.dropbox.com/u/6809582/linearfunctions.png

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} + \epsilon,\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?