forum.alglib.net
http://forum.alglib.net/

Levenberg Marquardt, beginners question
http://forum.alglib.net/viewtopic.php?f=2&t=3759		 Page 1 of 2
Author:  Chillosaurus [ Tue Jul 12, 2016 10:24 am ]
Post subject:  Levenberg Marquardt, beginners question
Dear all,
I am using the minlm subpackage of ALGlib for optimization.
I have realized that my results were worse than with the matlab version of the Levenberg Marquardt optimization. So, I printed the objective function values to the screen and they were first decreasing, but then getting worse again. The result does correspond to the result of the last iteration and not the minimum objective function.
How do I need to setup my problem correctly to find the minimum of my objectiv function?

In the moment I am using:
Code:
real_1d_array x1 = x;
   real_1d_array bndl1 = "[+5,-200]";
   real_1d_array bndu1 = "[10000000000000000000000000,-1]";
   ae_int_t maxits1 = 100; // 100 iterations.
   N = 2 * indices.n_elem;
   minlmstate state1;
   minlmreport rep1;
   double epsg1 = 0.000000000001;
   double epsf1 = 0;
   double epsx1 = 0;
   minlmcreatev(2,N, x1, 0.0001, state1);
   minlmsetbc(state1, bndl1, bndu1);
   minlmsetcond(state1, epsg1, epsf1, epsx1, maxits1);
   alglib::minlmoptimize(state1, SpotSize);
   minlmresults(state1, x1, rep1);
   printf("%d\n", int(rep1.terminationtype));
   printf("%d\n", int(rep1.iterationscount));
   printf("%s\n", x1.tostring(4).c_str());
Author:  Sergey.Bochkanov [ Tue Jul 12, 2016 1:27 pm ]
Post subject:  Re: Levenberg Marquardt, beginners question
1. Can you post actual code here? It is hard to say something using just a short snippet.

2. Maybe you need larger differentiation step (not smaller!). Sometimes numerical differentiation amplifies rounding errors in your function, so you may need larger step to reduce amplification ratio.
Author:  Chillosaurus [ Tue Jul 12, 2016 2:09 pm ]
Post subject:  Re: Levenberg Marquardt, beginners question
I encounter the same problem with two different objective functions.
The most simple of them is a least squares approximation to some data. My code is written in C++.
Code:
void function_ConicTilted(const real_1d_array &x, real_1d_array &fi, void *ptr)
{
   double sum = 0;
   for (i = 0; i < vLensfX.n_elem; i++){
      fi[i] = pow((vZ(i) - (((vX(i) * vX(i) + vY(i) * vY(i)) / x[0]) / (1 + sqrt(1 - (1 + x[1])*(vX(i)* vX(i) + vY(i) * vY(i)) / (x[0] * x[0]))) + dc1 )),2);
      sum = sum + fi[i];
   }
   cout << sum << ", " << x[0] << ", " << x[1] << endl;
}

The vecotrs vZ,vX,vY contain the x,y,z coordinates of the points to be fitted, dc1 is just a constant.All of them are real valued and of identical size.
The display of the objective function "sum" starts with 14.753 and goes down to 3.58 after the function is called about 20 times. Than it increases again. The final value is reported for 3.6634. The terminationtype is 2 and iterationscount is 34.

The calling sequence for the minimization routine is very similar to the one posted above.
Code:
   real_1d_array x = "[+10,-30 ]";
   real_1d_array bndl = "[+5,-200]"; //Form shall be convex and radicant shall be positive any time!
   real_1d_array bndu = "[+INF,-1]";
   double epsg = 0.00000000001;
   double epsf = 0;
   double epsx = 0;
   ae_int_t maxits = 0;
   minlmstate state;
   minlmreport rep;
   minlmcreatev(2,vX.n_elem, x, 0.01, state);
   minlmsetbc(state, bndl, bndu);
   minlmsetcond(state, epsg, epsf, epsx, maxits);
   alglib::minlmoptimize(state, function_ConicTilted);
   minlmresults(state, x, rep);


Is there a recommended way to determine the best size of the differentiation step?

Thank you for your help!
Author:  Sergey.Bochkanov [ Tue Jul 12, 2016 2:46 pm ]
Post subject:  Re: Levenberg Marquardt, beginners question
Maybe the reason is that you explicitly square fi[] in your code, i.e. you assign "fi = pow(abcdefg,2);" instead of "fi = abcdefg;"

Levenberg-Marquardt optimizes sum of squared f_i, and ALGLIB optimizer assumes that you pass f_i, and it will perform squaring/summation for you. If you pass f_i^2, it will result in sum of f_i^4 being optimized.
Author:  Sergey.Bochkanov [ Tue Jul 12, 2016 2:47 pm ]
Post subject:  Re: Levenberg Marquardt, beginners question
And it explains why sum f_i^2 behaves non-monotonically - because optimizer tries to minimize another function.
Author:  Chillosaurus [ Wed Jul 13, 2016 6:03 am ]
Post subject:  Re: Levenberg Marquardt, beginners question
Yes! I removed it and I get the same result as with the matlab implementation now.

Does this also mean that ALGlib optimizer is not a good choice if I want to maximize a function?
Can I just choose the differntiation step equal to the smallest relevant digit of my expected optimization result or is there some scaling involved that I need to consider when setting the size for the differentiation step?
How can I return the final and initial value of my objective function?

Thanks!
Author:  Sergey.Bochkanov [ Wed Jul 13, 2016 10:43 am ]
Post subject:  Re: Levenberg Marquardt, beginners question
> Does this also mean that ALGlib optimizer is not
> a good choice if I want to maximize a function?

If you want to maximize f(x), you may minimize -f(x) instead.

> Can I just choose the differntiation step equal to
> the smallest relevant digit of my expected
> optimization result
There exists such a thing as "scale of variables". You should set it first with minlmsetscale() function, and then you may choose differentiation step equal to 0.0001 (optimizer will multiply it by scale automatically). It is a good value for most scenarios. It is better to select it once, and not to play with it after optimal value is found.

> How can I return the final and initial value
> of my objective function?
minlmsetxrep() allows you to activate function reports. After you turn it on, you may pass a rep() callback to optimizer, and it will be called after each iteration (and once - in the beginning, before first iteration). You may use current point reported by this callback to get information about solution progress.
Author:  Chillosaurus [ Wed Jul 13, 2016 1:13 pm ]
Post subject:  Re: Levenberg Marquardt, beginners question
>> If you want to maximize f(x), you may minimize -f(x) instead.
You said that the sum of squares of the f(x) is minimized. Then the minus sign does not change anything.

>> You should set it first with minlmsetscale() function
How do I determine the scaling coefficients that are input to this function?

>> minlmsetxrep() allows you to activate function reports. After you turn it on, you may pass a rep() callback to optimizer, and it will be called after each iteration (and once - in the beginning, before first iteration). You may use current point reported by this callback to get information about solution progress.

OK, I have added minlmsetxre() to my calling sequence. I do not understand what else I need to do to print my final and initial objective function value to screen.

Code:
   real_1d_array x1 = x;
   real_1d_array bndl1 = "[+5,-200]";
   real_1d_array bndu1 = "[10000000000000000000000000,-1]";
   ae_int_t maxits1 = 1000; // <1000 iterations.
   N = 2 * indices.n_elem; // maximum number of functions fi
   minlmstate state1;
   minlmreport rep1;
   double epsg1 = 0.000000000001;
   double epsf1 = 0;
   double epsx1 = 0;
   //minlmsetscale(state1,);  // ???
   minlmsetxrep(state1, true); // what else is to do to print final and inital objective function value?
   minlmcreatev(2,2*N, x1, 0.0001, state1);
   minlmsetbc(state1, bndl1, bndu1);
   minlmsetcond(state1, epsg1, epsf1, epsx1, maxits1);
   alglib::minlmoptimize(state1, SpotSize);
   minlmresults(state1, x1, rep1);
Author:  Sergey.Bochkanov [ Thu Jul 14, 2016 2:05 pm ]
Post subject:  Re: Levenberg Marquardt, beginners question
> You said that the sum of squares of the f(x) is minimized. Then the minus sign does not change anything.

Got it! Yes, you are right, you can't use Levenberg-Marquardt to do such optimization - neither ALGLIB implementation, nor any other on the market.

From the other side, you may use some other ALGLIB optimizer (say, L-BFGS) to solve maximization problem - just "collapse" your vector function to scalar one (calculate sum of squares at your side) and pass it to general purpose optimizer, which will process it as black box, without knowing about its internal structure.

However, I should warn you that such optimization problems are generally NP-hard and may have terribly many local extrema. It is better to refomulate your problem in a more well-defined way.

> How do I determine the scaling coefficients that are input to this function?
You may know their expected magnitudes. Of course, you do not know exact value beforehand (you do not need optimizer if you know it), but often you may guess that it is in 1...10 or 1000-2000 range. Right bound of this range is a scale.

> OK, I have added minlmsetxre() to my calling sequence. I do not understand
> what else I need to do to print my final and initial objective function value to screen.
You should study signature of minlmoptimize() function - its actual declaration in header file. You will find out that it accepts rep() callback parameter, which is NULL by default.

Define your own rep() function and pass it to optimizer. It will call it repeatedly after each iteration. First value reported is an initial point, last value reported corresponds to the final one.
Author:  Chillosaurus [ Fri Jul 15, 2016 12:43 pm ]
Post subject:  Re: Levenberg Marquardt, beginners question
>>>> How do I determine the scaling coefficients that are input to this function?
>> You may know their expected magnitudes. Of course, you do not know exact value beforehand (you do not need optimizer if you know it), but often you may guess that it is in 1...10 or 1000-2000 range. Right bound of this range is a scale.

Thank you. Does this mean that a good choice of scaling is to set the scaling equal to my upper bounds?


>> Define your own rep() function and pass it to optimizer. It will call it repeatedly after each iteration. First value reported is an initial point, last value reported corresponds to the final one.

That does not sound like a good idea. If I need to create a new function anyway, it will be better to just call it once before and once after the optimization.
Page 1 of 2 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/