forum.alglib.net

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?

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.

You can let the optimization algorithm play with whatever values it wants, but normalize the vector inside your target function.