forum.alglib.net

ALGLIB forum
It is currently Thu Mar 28, 2024 2:42 pm

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  [ 3 posts ] 
Author Message
 Post subject: adding constraints to MinLBFGS
PostPosted: Wed Jul 07, 2010 5:32 pm 
Offline

Joined: Tue Jul 06, 2010 8:00 pm
Posts: 21
I have an optimization problem for which I am using MinLBFGS. I have to minimize a non-linear function of a vector of Xs, but at the same time I have to make all Xs sum up to 1.0 and also make them non-negative (>= 0.0). The minimization works fine without constraints. I looked at the MinLBFGS test subroutine in VBA to see how the constraints could be added; however, I am not sure how to do it in an optimal way.

I tried adding the square of difference between the sum of Xs and 1.0 to the st.F field, so as to increase the minimized objective function when the sum of Xs departs from 1. At the same time, I tried adding terms to the st.G(i) gradients in a fashion similar to how it is done in the MinLBFGS test for solving a set of linear equations. The optimization results are not the same what I get when using Excel Solver function on identical input data.

Could Sergey or someone else please let me know of the proper way to add constraints in MinLBFGS?


Top
 Profile  
 
 Post subject: Re: adding constraints to MinLBFGS
PostPosted: Thu Jul 08, 2010 2:21 pm 
Offline

Joined: Tue Jul 06, 2010 8:00 pm
Posts: 21
My fault for not having looked at the ALGLIB contents closer in a rush to implement things quickly. I found the MinASA module which accepts constraints as ranges for each X in a vector. Since in my optimization the sum of all Xs has to be 1 and all Xs have to be non-negative, I simply specified the lower bound of 0 and upper bound of 1 for each X. The results are fine in that respect. But how to properly implement the constraint of the sum of all Xs to be 1? I tried the following:
- At each iteration, I sum up all Xs in a variable "xsum"
- Add a term "Square(xsum - 1.0)" to st.F
- Add a term "2.0 * (xsum - 1.0)" to each st.G(i)

That seems to work but only roughly. The resulting sum of Xs is typically in the .997 to 1.03 range, which is too big an error for my liking. I tried various combinations of EpsG, EpsX, and EpsX to no effect. I tried to calculate the gradient for each X using 4 points instead of just 2 points (as Sergey suggested be done for MinLBFGS). A slight improvement resulted but it still does not work perfectly (a reference implementation with Solver in Excel does, in that all Xs always sum up to 1 as prescribed).

Could anyone offer any pointers on how to solve that? Esp. how to properly calculate a gradient of a non-linear function with accuracy. Thanks in advance.


Top
 Profile  
 
 Post subject: Re: adding constraints to MinLBFGS
PostPosted: Thu Jul 08, 2010 9:05 pm 
Offline

Joined: Mon Jul 05, 2010 11:13 am
Posts: 3
You can let the optimization algorithm play with whatever values it wants, but normalize the vector inside your target function.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 43 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:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group