CODEWITHSUNDEEP
algorithmmathematical-optimization
Ephemera
Ephemera

Reputation: 8970

Algorithms for curve fitting with a given model

Say I have a set of (x, y) data points, and I am told that the model that best describes these data points looks something like this:

Equation

Where A, B, C and D are unknown constants. The aim is to find values for A, B, C and D that create a 'function of best fit', based on some measure of quality (e.g. the coefficient of determination).

Many programs can take a series of data points and create a smooth best-fit function of different types (polynomial, exponential, etc). Their algorithms solve for coefficients in a given (simple) model, and most of these curve fitting algorithms are reasonably documented. However, the above function (meant to generally indicate a 'more complicated' function), cannot be fit to data without some custom programming.

My question is: What are some of the algorithms used for this kind of model fitting?

One algorithm that has been described to me is Particle Swarm Optimisation, which is quite computationally expensive. While I'm not suggesting there will be 'cheap' (in time complexity) algorithms for this sort of problem, I would be interested to know what other algorithms (evolutionary or otherwise) are out there.

Upvotes: 1

Views: 3482

Answers (1)

mcdowella
mcdowella

Reputation: 19601

If I had to fit a function like yours using least squares, I would probably try http://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm. If you look at the Notes section of that page you can see that it amounts to approximating the function you are trying to fit with a linear function. The account there says that convergence is not guaranteed, which is true. Starting from a point x, it can step to a point x', which is even worse. However, if x is not a local optimum, there will be some point near x, Ax' + (1-A)x which is better, and you can try and find this by starting at A=1/2 and repeatedly halving it.

To minimize a completely unstructured mathematical function I would probably fall back on the Torczon Simplex algorithm, because there is a reasonably understandable proof that this converges under fairly weak assumptions. There is a pointer to this from the references at the end of http://en.wikipedia.org/wiki/Pattern_search_%28optimization%29.

Upvotes: 1

Related Questions