Timeline for Optimal knot placement for fitting piecewise-continuous linear functions to a nonlinear function
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2010 at 6:14 | comment | added | Gilead | 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. | |
| Nov 15, 2010 at 20:45 | comment | added | Brian Borchers | 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. | |
| Nov 12, 2010 at 19:59 | comment | added | Gilead | 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. | |
| Nov 12, 2010 at 1:37 | history | answered | Brian Borchers | CC BY-SA 2.5 |