- #1
matts0611
- 7
- 0
Hello, I am working on a research project that requires me to write a solver for solving a particular problem. I could really use some math advice if anyone is willing to assist.
I need to minimize a non-linear objective functions of 5 variables.
It is a pretty complex function. Each of the variables has a min and max value that it can be.
I wrote an iterative solver for it in C that uses the "steepest descent" method to find the minimum. At each point it calculates the negative gradient by numerical differentiation and then does a line search in that direction to find the step size. The step size is done with quadratic interpolation. The step size in that direction is bounded by the constraints
This seems to give me a fairly good result except that it takes too long to converge (almost 3000 iterations). I need something that converges much faster than this.
I did some reading and it seems that for non-linear solvers the quasi-Newton (second order) method known as BFGS (Broyden-Fletcher-Goldfarb-Shanno) seems to be a pretty popular and agreed upon good method to use.
Basically it iteratively constructs an approximation of the second derivative as it steps through the solution space. The first step it simply uses the steepest descent direction. This method is traditionally for unconstrained problems.
I found a few solvers that use similar methods. One is called GRG2 (Generalized Reduced Gradient) and is used in many programs such as the MS Excel solver. I tried my problem in the Excel solver and it works very well. It finds the solution in about 25 or so iterations. This is about what I want. This solver was written by Leon Lasdon.
I also found another solver called L-BFGS-B that uses BFGS with bound constraints but is built for problems with a large number of variables (thats what the L stands for).
I found a Python wrapper for this solver and used it to solve my function and it performs well also.
I learned about how BFGS works by reading some texts and looking around online, basically every iteration is searched in the direction D = -(H^-1)*G
Where G is the gradient at the current position and H is the approximate Hessian matrix (matrix of second derivative values).
I tried to write a solver that uses this method to solve my problem but it doesn't seem to work correctly. I made the same modifications as to the steepest descent (to bound the step size by looking at the bounds of the variables in that direction) but I can't seem to get it to work correctly. It converges but it converges to an answer that is not very optimal.
It seems to work on other math problems that I've tried but for some reason not on the problem that I need to solve. I try to compare my iteration results with the Excel solver and even on the second iteration I move in the wrong direction, but I check the math by hand and it is indeed in the direction that I should be going in. I have double and triple checked my math and compared against example problems and I seem to be doing the right thing (without taking into account the bound constraints).
I think the problem lies with how I modified the algorithm to work with bound constraints but I'm not sure. I have tried reading papers by Byrd about the L-BFGS-B algorithm to see how it works but I'm having a hard time understanding what I'm doing wrong.
I know this post is really long but I'm in need of assistance on this.
Does anyone have any knowledge in this area and is willing to help?
I can compensate you for your time if needed.
Thank you,
Matt
I need to minimize a non-linear objective functions of 5 variables.
It is a pretty complex function. Each of the variables has a min and max value that it can be.
I wrote an iterative solver for it in C that uses the "steepest descent" method to find the minimum. At each point it calculates the negative gradient by numerical differentiation and then does a line search in that direction to find the step size. The step size is done with quadratic interpolation. The step size in that direction is bounded by the constraints
This seems to give me a fairly good result except that it takes too long to converge (almost 3000 iterations). I need something that converges much faster than this.
I did some reading and it seems that for non-linear solvers the quasi-Newton (second order) method known as BFGS (Broyden-Fletcher-Goldfarb-Shanno) seems to be a pretty popular and agreed upon good method to use.
Basically it iteratively constructs an approximation of the second derivative as it steps through the solution space. The first step it simply uses the steepest descent direction. This method is traditionally for unconstrained problems.
I found a few solvers that use similar methods. One is called GRG2 (Generalized Reduced Gradient) and is used in many programs such as the MS Excel solver. I tried my problem in the Excel solver and it works very well. It finds the solution in about 25 or so iterations. This is about what I want. This solver was written by Leon Lasdon.
I also found another solver called L-BFGS-B that uses BFGS with bound constraints but is built for problems with a large number of variables (thats what the L stands for).
I found a Python wrapper for this solver and used it to solve my function and it performs well also.
I learned about how BFGS works by reading some texts and looking around online, basically every iteration is searched in the direction D = -(H^-1)*G
Where G is the gradient at the current position and H is the approximate Hessian matrix (matrix of second derivative values).
I tried to write a solver that uses this method to solve my problem but it doesn't seem to work correctly. I made the same modifications as to the steepest descent (to bound the step size by looking at the bounds of the variables in that direction) but I can't seem to get it to work correctly. It converges but it converges to an answer that is not very optimal.
It seems to work on other math problems that I've tried but for some reason not on the problem that I need to solve. I try to compare my iteration results with the Excel solver and even on the second iteration I move in the wrong direction, but I check the math by hand and it is indeed in the direction that I should be going in. I have double and triple checked my math and compared against example problems and I seem to be doing the right thing (without taking into account the bound constraints).
I think the problem lies with how I modified the algorithm to work with bound constraints but I'm not sure. I have tried reading papers by Byrd about the L-BFGS-B algorithm to see how it works but I'm having a hard time understanding what I'm doing wrong.
I know this post is really long but I'm in need of assistance on this.
Does anyone have any knowledge in this area and is willing to help?
I can compensate you for your time if needed.
Thank you,
Matt