forum.alglib.net

ALGLIB forum
It is currently Fri Mar 29, 2024 1:32 am

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 12 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Levenberg Marquardt, beginners question
PostPosted: Tue Jul 12, 2016 10:24 am 
Offline

Joined: Tue Jul 12, 2016 10:18 am
Posts: 6
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());


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Tue Jul 12, 2016 1:27 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
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.


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Tue Jul 12, 2016 2:09 pm 
Offline

Joined: Tue Jul 12, 2016 10:18 am
Posts: 6
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!


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Tue Jul 12, 2016 2:46 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
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.


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Tue Jul 12, 2016 2:47 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
And it explains why sum f_i^2 behaves non-monotonically - because optimizer tries to minimize another function.


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Wed Jul 13, 2016 6:03 am 
Offline

Joined: Tue Jul 12, 2016 10:18 am
Posts: 6
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!


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Wed Jul 13, 2016 10:43 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
> 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.


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Wed Jul 13, 2016 1:13 pm 
Offline

Joined: Tue Jul 12, 2016 10:18 am
Posts: 6
>> 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);


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Thu Jul 14, 2016 2:05 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
> 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.


Top
 Profile  
 
 Post subject: Re: Levenberg Marquardt, beginners question
PostPosted: Fri Jul 15, 2016 12:43 pm 
Offline

Joined: Tue Jul 12, 2016 10:18 am
Posts: 6
>>>> 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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ]  Go to page 1, 2  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 64 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group