I have a set of measured data points that empirically defines a function of two variables. I need to fit this data set with a nonlinear analytical function that is given but it contains five adjustable fitting parameters in addition to the two variables. Let us define the error measure between the fit and the data using the traditional sum-square-error (with an optional user-selected weighting function) definition. The goal is to numerically calculate the fitting parameters that minimize this error measure, and some numerical routine is needed to do that. My problem is that all of the publicly available routines that I have tried look for relative minimums in the error measure instead of the global minimum. The routine declares success when a relative minimum is found. For my specific application there is an enormous number of relative minimums, so that almost any change in the initial guess produces an entirely different returned result. I have to manually keep track of which relative minimum (out of many because of many initial guesses) is the smallest. A smarter routine would not declare success each time a relative minimum in the error measure is found. Instead, it would remember results from prior initial guesses and recognize that if the most recent calculated relative minimum is not smaller than all prior calculations, then it needs to keep working. Does anyone know of a publicly available routine (e.g., a package in MATLAB) that does this?
To make sure I understand you: do you want model fitting, with some data smoothing? The reason for smoothing can be noise in observed data set or that your model is approximate. My first thought is to take criterion of relative entropy and to use model-based smoothing by approaching convex programming routine. And convex programming would give you a global extremum if your "algorithmic" assumptions are relevant. Check my example paper on smoothing and model fitting with abrupt changes at paper "Simultaneous State and Parameter Estimation Using Maximum Relative Entropy with Nonhomogenous Differential Equation Constraints". If you experience problems, send me the function and describe what you know about the system. or post this all info here and I will try to see how we could help. Good luck.
Thank you for your suggestion. I do want model fitting (the model is a simplified approximation of the actual physics) to data produced by real physics except for some experimental scatter. The topic in your paper is new to me so I will have to study it for a long time to understand it. But it is worth my effort to do that, because the problem I described has occurred more than once, so I will start reading your paper.
If your problem/metric is not convex (and I think you have defined your problem as being non-convex) then I'm not sure there is a general technique which will give the best answer because until you have found all the answers you won't know which one is best. Unless you are very lucky it sounds like a classic NP problem - the time taken to solve will extend very fast as more data is available.
Some things to think about:
- Can you reduce the region of the search?
- Can you find a solution in stages, extract one or two parameters first then look for the rest?
- Can you predict regions which are worthwhile searching for solutions from general behaviour of the function or results of previous fits?
- Can you choose a different metric for "best" which makes the problem convex?
- You probably have to accept you will not get the best solution - what is good enough?
- Can you remove noise first with a smoothing function or filter then fit your function to it to extract the parameters?
I don't have any knowledge of the academic studies of the general optimization problem but a technique I have used in the real world (with no knowledge of the behaviour of the system I was trying to optimize) is to:
I agree on all your points except:
1. Maximimization of relative entropy is a convex optimization task
2.
I would recommend never do this unless it is really unavoidable. Start of your signal can "speak" about one parameters, the end of your curve can speak about another In particular. See my example paper on Simultaneous state and variable estimation and there you will find an explanation on why and when it can happen.
3. I disagree on NP and time complexity, because in real life experiments very frequently the "answers" space is really limited or even discrete, so we can constrain our posterior function and know the answer really quickly. Just more context is required as you correctly noticed. Unfortunately I cannot yet provide a numeric example on this, because my publication is still pending on Big Data optimization in financial app.
I am looking forward to open problems in practical applications which are considered NP-hard. That would be really cool to resolve.
Renaldas
Did you think about any member of numerous family of genetic algorithms, simulated annealing, particle swarm optimization and alike? Well, they do not guarantee a global solution either but at least automatcally 'think' for you what other starting point might be better. The only way to find global optimum I know is interval arithmetics. See Wikipedia for that.
There sure is a lot to think about here. For the latest very specific problem that I am working on, I actually can work this in stages. Some data sets resemble limiting cases in which a straight-line (using a suitable kind of graph paper) represents the data well (I guess this is a kind of data smoothing), and analysis easily solves for some of the fitting parameters from the properties of these straight lines. The remaining fitting parameters, to be determined by the remaining data points, are few enough to be found by trial and error. But I have come up against this kind of problem before and this procedure doesn't always work so I was looking for a more universal approach. What I have been doing, for the more difficult examples, is steps 1 through 4 listed in Nick's post. But I have been doing these steps manually, which is a lot of work. I was wondering if some publicly-available software will perform these steps automatically.
In providing suggestions, it would be very helpful to see your 5-parameter analytical function and the domain of the data to which it applies. It would aslo be helpful to know the data uncertainty structure. For example, is the problem one of ordinary least squares (OLS), generalized least squares (GLS), a different norm (l_1, for instance), etc? Also, are there any constraints on the parameters (non-negativity, summing to unity, etc.)? It certainly sounds an intriguing problem.
Try the Luus-Jakola method to get in the region of the global optimum for situations like that. Basically you randomly search in an N-space "box" for a fair number of trials, take the best answer among those, re-center the box on that answer, then shrink the box by 5-15% (ie, make the dimensions only slightly smaller than the first search), then repeat the search. Do this outer search about 20 times.
Original article: Luus, R.; Jaakola, T. H. I. Optimization by Direct Search and
Systematic Reduction of Size of Search Region. AIChE J. 1973, 19 (4),
760-766.
On-line evaluation with a formal description: http://pubs.acs.org/doi/pdf/10.1021/ie060051q
Oh, and after you get in the right ballpark using L-J, *then* use a gradient method to fine-tune the answer.
As I understand you are searching for the global optimization method which will return values of 5 your model parameters. So evolutionary or swarm algorithms, as Marek said, are a good choice.
I optimized with success the hysteresis model having 5 parameters using evolution strategy (ttp://www.gdudek.el.pcz.pl/files/Histereza_SE13.pdf).
In Global Optimization Toolbox in Matlab you have some tools: genetic algorithms, particle swarm, simulated annealing and direct search.
I reccomend tournament searching which is very simple:
http://www.gdudek.el.pcz.pl/files/TourSearch_14.pdf
Thank you for giving me the information that I really need. I am not trying to figure out how to find the global best fit. I am looking for software that already figured out the method because I only care about the answer, not the method. I use Octave instead of MATLAB because Octave is free, but Octave also has "Nonlinear Programming" tools that include the tools you described. I think that will work.
I have recently been fitting a function of around 20 parameters to a dataset. I can recommend Matlab's MultiStart and GlobalSearch in combination with a least-squares fitting routine (lsqnonlin) for this kind of problem. These algorithms basically find many local minima (and then select the best). It requires the Global Optimization Toolbox. Send me a message if you would like to have an example implementation.
Maybe you can consider the recursive least squares algorithm (RLS) with forgetting factor (RLS-FF). RLS is the recursive application of the least squares (LS) regression algorithm, so that each new data point is taken in account to modify (correct) a previous estimate of the parameters from some linear (or linearized) correlation thought to model the observed system. The method allows for the dynamical application of LS to time series acquired in real-time. As with LS, there may be several correlation equations with the corresponding set of dependent (observed) variables. For the RLS-FF algorithm, acquired data is weighted according to its age, with increased weight given to the most recent data. The correlation parameters are updated gradually. Application example ― I have applied the RLS-FF algorithm to estimate the parameters from the KLa correlation, used to predict the O2 gas-liquid mass-transfer, hence giving increased weight to most recent data:
Thesis Controlo do Oxigénio Dissolvido em Fermentadores para Minimi...
This one is definitely better in many cases:
http://www.physicsjournal.net/article/view/30/3-3-11
Thank you Koen Van de Moortel . I'm sure that some readers can benefit from your recommendation. However, for my particular application the problem is that there is an enormous number of relative minimums in the error measure. I mean really enormous, each initial guess seems to converge to another relative minimum and produce a different best fit. A routine that declares success (declares a fit to be the best fit) when it finds a relative minimum in the error measure is not useful for finding the global minimum, i.e., for finding the true best fit. What is needed is a routine that keeps track of all of these relative minimums and then selects the global minimum from them.
L.D. Edmonds You made me curious! I suspect there is some periodicity in the data? If you could send me some data and the kind of model you expect, I can take a look and maybe find an algorithm to implement in my software.
Interesting discussion. It reminds me of our control apps where we first estimate the rate of change state first and only then do we come back to the current state variable. Otherwise, if you have a multi-variate problem from a real-life, the synchronization between observations is a frequently bigger issue compared to the "noise" significance. In your case, the problem of picking "correct" samples to include in your criterion is still a problem, while in the rate of change domain estimation it is resolved, but includes the additional steps/homework of optimization. Nevertheless, I liked your criterion, Koen.
I appreciate your interest Koen Van de Moortel in asking for a copy of the data and kind of model, but I won't blame you if you regret asking for that because there are a lot of pages in the report. But maybe this is a good example of a model that has a lot of fitting parameters so maybe you won't regret asking for it. Anyway, it is in the following link.
Research Estimates of SEU Rates from Heavy Ions in Devices Exhibiting...
There are discussions in that report on curve-fitting algorithms that were used including the actual routines that were used. Again, I can understand if you have better things to do than study that very long report.
L.D. Edmonds Looks very interesting. Unfortunately not something to read in 5 minutes. If I had some funding, I would be happy to delve into this material.
Understood. I also would not read that long report for fun. I wrote it because I was paid to do that. However, it could be useful in the off-chance that some follower of this thread is so passionately dedicated to testing out a proposed "smarter fitting routine" that the person is willing to read that long report to use it as a test case. The examples in that report are particularly obstinate and challenge any proposed smarter routine so the report provides good test cases. As I said before, there is an enormous number of relative minimums in the error measure. What I did not say before but will say here is that it is virtually certain that the "best fits" that I accepted to include in the report are not true best fits. They were accepted when "they looked good enough to me and after a lot of searching I couldn't find anything better." Anyone that is capable of finding the true best fits for the examples in that report will indeed have a smarter fitting routine.
L.D. Edmonds You challenge me... Would it be possible to just send me the bare function you have the most problems with? Just y=f(x, parameters)=... and a dataset I can play with?
The equations defining the fitting function are (41) through (46) (starting on page 30), with the function I calculated in Appendix C. The text surrounding these equations also identify the ten fitting parameters. An example data set is the text box starting on page 33 and continuing to page 35. Column 6 is the measured function value that the fit is suppose to agree with. Columns 3 through 5 are the function arguments. Have fun.
- Badges
- Science topic
- Similar topics
- Physical Sciences
- Materials Science
- Materials
- Inorganic Materials
- Ceramics
- Glass