4
$\begingroup$

First, Please, keep in mind that I'm a programmer not mathematician, and I have a fair mathematical background.

I used optimization in Java to fit some observations to a trigonometric function, I tried the following optimizers: BOBYQA, CMA-ES, Powell, and Simplex to optimize the function as a scalar function, and also Levenberg-Marquardt and Gauss-Newton to optimize it as a vector function, I got good results for

$z = a.\sin(x)+b.\cos(y)$

, but for a non-linear relation like: $y = \cos(a.x)$ or $z = \sin(a.x) + \cos(b.x)$, the results are very unsatisfying and I have to choose an initial guess very close to the correct values of $a$ and $b$, and certainly this is not practical, example:

$y=6.4\cdot e^{5.5x}$

gives

$(6.39 \text{ and } 5.5)$ if the initial guess is set to $(7,7)$

and gives

$(2.07 \text{ and }5.5)$ for initial guess of $(8,8)$

and , certainly, this is a very bad guess. So I guess I need either of two choices:

  1. Find a method for selecting a very good initial guess
  2. Find a method for improving the optimizer so that it could get a good result even if the initial guess is not good.

Thanks

$\endgroup$
  • $\begingroup$ Just to make I understand the question ... you used various optimization techniques to find values of $a$ and $b$ that make the function $y = ae^{bx}$ best fit some observed $(x,y)$ data values. And you ran into the trouble you described. Is that correct? $\endgroup$ – bubba Aug 18 '13 at 11:11
  • $\begingroup$ I see that BOBYQA was written by M. J. D. Powell. He is one of the world's leading experts on optimization, so I assume that his software is of high quality. I've done similar optimizations myself (though not using any of the packages you mentioned), and my experiences have been much better than yours. Most algorithms have trouble if the objective function is very badly behaved, or the starting point is far from the desired solution, but I don't think either of those two problems are present in your example. I would expect better results, even with a less-than-ideal starting point. $\endgroup$ – bubba Aug 18 '13 at 11:21
  • $\begingroup$ bubba, Yes, exactly. I also was expecting better results, because (8,8) is not very far from the correct guess, please notice that the above result are obtained by a Levenberg-Marquardt Optimizer, this is exactly what I did: - Generated 35 of random values - Calculated y = 3.4 * e^(2*x) for every point - Implemented a function that calculates z = ae^(bx) to be used by the optimizer - Set the initial guess to (8,8) - Set the bounds to (16,16) - Set the number of interpolation points of BOBYQA Optimizer to 4 (Is is suitable?) - Specified 1000000 maximum iterations how to estimate init guess? $\endgroup$ – Osama Salah Aug 18 '13 at 18:05
  • 1
    $\begingroup$ Right. (8,8) is not very far from the right answer, and I'd expect any decent optimization function to perform properly. I can only guess at what the problem might be. I'd suggest you use a larger number of interpolation points ($m$). A quadratic function of two variables has 6 degrees of freedom, so using $m= 4$ points seems too small, to me. Powell suggests using $m = 2n+1 = 5$. Another idea: use Mathematica or something similar to graph the objective function, and see if there's anything strange about it. $\endgroup$ – bubba Aug 19 '13 at 5:24
  • 1
    $\begingroup$ Aha. So, if the objective function has local minima, then, as far as I know, the only possible approach is to start your iterations at several different locations, and hope that one of these iterations leads to a global minimum. Not very scientific. To find good starting ponts, you can just sample the objective function and try to find places where it's small. Since your solution space is only 2D, that's not too bad. $\endgroup$ – bubba Aug 20 '13 at 10:30
3
$\begingroup$

I finally got it, the problem was caused by falling in a local optimum, following is a short comparison between results I got from the mentioned algorithms:

  • Powell and BOBYQA give wonderful results with high precision but low accuracy, this means that you have to provide a very good initial guess and rather tight bounds
  • Simplex is slightly better in not falling in a local optimum, I think this is because it uses Nelder-Mead Simplex or Multi-Directional Simplex to update its guesses, both allows providing long steps to search far from the initial guess and thus avoiding the local optimum, it also requires no bounds, it estimates them well
  • CMA-ES is much more accurate but slightly less precise, it allows you to specify bounds and step length, but strangely gives different results for different runs and some of them may fall in a local optimum.

I finally made the following algorithm to get reliable, accurate, and precise results:

  1. Use CMA-ES to get a rough estimation with high accuracy
  2. Calculate the mean squared error
  3. If the mean squared error is larger than a threshold, repeat CMA-ES again
  4. With acceptable error, use Simplex to get a more precise result
  5. I also used a Multi-Start-Multivariate optimizer with CMA-ES and simplex to help avoiding local optima

This gave acceptable results

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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