Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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?

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

In the limit of fine subdivision, the local goodness of fit depends on only two things: the absolute value of the local second derivative, and the local density of knots. For a segment of constant second derivative $a$ over an interval of length $c$, the integrated squared error over the interval comes out to $a^2c^5/120$. Given a small approximation interval (small enough that the second derivative does not vary by much over its length) whose squared error contribution is $E$, replacing that interval by two approximation intervals of half the width reduces the total squared error by approximately $E- 2(E/32)=(15/16)E$. The best segment to subdivide (according to this approximation) is thus whichever one contributes the most to the error. It follows that in the limit of many knots the optimum will have an equal contribution to the error coming from each segment. This is true, in the limit, when the local density of knots at $f(x)$ is proportional to $f^{\prime\prime}(x)^{2/5}$. A very good approximation to your optimal assignment problem can thus be obtained by making a plot, from $L$ to $U$, of $\int_L^x f^{\prime\prime}(s)^{2/5}\ ds$, dividing it into equally spaced horizontal strips, and placing your knots at the horizontal values where the integral plot crosses from one horizontal strip to the next.

Incidentally, if you keep the same number of straight-line approximations but allow them to cross the function (and back) in their interiors rather than at their endpoints, you can improve the integrated squared error by (in the limit) a factor of 6.

share|improve this answer
    
Thanks for the very insightful answer. I have a few questions: 1) could you provide a reference for the $a^2 c^5 /120$ error, or a clue as to how it was derived? 2) For any quadratic polynomial $f(x)=a_2 x^2+a_1 x+a_0$, your integral function $I(x)=\int_L^x f^{\prime\prime}(s)^{2/5}\ ds=(2a_2)^{2/5}(x-L)$ is a linear function. If we take equally spaced horizontal strips in the range of $I(x)$, all the crossing points correspond to equally spaced knots; somehow I don't think equispaced knots are optimal for all quadratic polynomials. Have I missed something? Thanks. –  Gilead Nov 12 '10 at 20:20
    
The value $a^2c^5/120$ comes from direct calculation: either observe the invariance and reduce to the special case $\int_0^c (ax^2/2-axc/2)^2\ dx$, or take the fully general $(a/2)x^2+a_1x+a_0$, find the line that crosses it at $x_0$ and $x_0+c$, and integrate the squared error, proving the invariance by the cancellation of all parameters other than $a$ and $c$. Since the original problem is invariant with respect to addition of linear terms, and any horizontal shift of a parabola is equivalent to adding a linear term, equispaced knots are indeed optimal for a quadratic polynomial. –  Tracy Hall Nov 14 '10 at 16:10
add comment

Do you really want to solve this problem, or do you just want to get a good approximation to the function? I would bet that your overall goal is actually to get a fast and reasonably accurate approximation to the function, and there are lots of ways of doing that without solving what you already know is a hard optimization problem.

If you have some good reason why you really need to solve the nonconvex nonsmooth optimization problem as you've formulated it, then consider using branch and bound with convex underestimating functions. If n is reasonably small, then a branch and bound code might actually be able to find a provable epsilon optimal solution in reasonable time.

share|improve this answer
    
Well, you're right in that what I'm looking for is a fast and accurate way of getting a good approximation. However, I'd like for it to be based on the analytical properties of $f(x)$, so that I can say something about the achievable approximation error. Tracy's answer is much more in the vein of what I'm looking for. However, you mention there are ways of getting a good approximation... I'd love to hear what they are. I merely posed the optimization problem to demonstrate the subtle difficulties of this problem -- I'm really looking for another approach. –  Gilead Nov 12 '10 at 19:59
    
First, you might consider using something more sophisticated than a piecewise linear function. Why not cubic splines instead? There's a huge literature on heuristics for locating knots for spline approximation- you could simply use one of these heuristics to get a reasonable set of knots, check to see whether the L2 error is sufficiently small and if not, then you could add more knots until it is sufficient. –  Brian Borchers Nov 15 '10 at 20:45
    
Well, the reason I'm going with linear splines is because I need to shoehorn this into an MILP where I can efficiently represent the piecewise function using SOS2 constraints. The reason I care about optimality is because I want to be able to approximate a nonlinear function with as small an $n$ as possible (every piecewise function = 1 binary variable, and I have many such functions, so it gets expensive very fast). Thanks for the lead -- I'll check to see if there are any references on locating knots for linear splines. –  Gilead Nov 17 '10 at 6:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.