Can I use automatic differentiation in fmincon?
18 次查看(过去 30 天)
显示 更早的评论
I have a likelihood function that I'm solving in Matlab but it takes several hours to maximize using fmincon. I wondered if the package autodiff, or some Matlab package for automatic differentiation, could speed it up. If so, how can I use it with fmincon or some other constrained optimization command? There doesn't seem to be an automatic differentiation option in the fmincon documentation.
0 个评论
采纳的回答
Alan Weiss
2017-9-11
I doubt that you would get any significant speedup using automatic differentiation if you use it simply to specify the gradient of the objective. fmincon usually does a good job estimating gradients by finite differences, and usually this is not very time-consuming. However, if you would compute the Hessian of the Lagrangian using automatic differentiation, then you might get some speedup. See this example using symbolic computations of gradients and Hessians, where the result took only 19 iterations using an analytic Hessian, but 79 iterations using finite differences.
Yes, symbolic computations are not exactly the same as AD, but after using matlabFunction they are quite comparable.
Alan Weiss
MATLAB mathematical toolbox documentation
2 个评论
Zach
2017-9-15
Alan, I'd expect a pretty hefty speedup from specifying gradients, especially if the objective function is expensive since it's calling the objective twice for every input in order to compute the finite differences. It won't reduce the total number of iterations, but should reduce the number of function evaluations significantly.
Alan Weiss
2017-9-18
Well, if your objective function has analytic derivatives, and does not include any integration, then generally it doesn't take all that long to evaluate. The length of time to evaluate the analytic expression for the gradient is quite often longer than the length of time to evaluate the objective a few times when approximating a gradient. Generally, if you have an N-dimensional variable, then fmincon uses N objective function evaluations to approximate a gradient using forward finite differences.
Feel free to use tic and toc statements on the example I linked to see that analytic gradients often don't save time. However, the analytic Hessian certainly saves time, mainly by substantially lowering the number of iterations.
Alan Weiss
MATLAB mathematical toolbox documentation
更多回答(2 个)
Shaun Forth
2017-9-11
Hi Michael,
To the best of my knowledge the Matlab optimization toolbox still does not have automatic differentiation.
Some key questions are:
- How many inputs N do you have and how many constraints Mc? As you have a constrained problem (objective + constraints) you will have M=Mc+1 functions required to be differentiated. If M<<N then reverse (adjoint) mode AD would be preferred.
- Is your code vectorized? The effect of vectorization in your code may be huge. If you have a large loop then for overloaded AD each operation in the loop has to be overloaded and functions called each cycle of the loop. The overhead of calling the functions may be substantial. If that same loop were instead vectorized then just one function is called for each operation. For reverse mode, even source transformation AD tools are likely to store data to a so-called tape (a.k.a. stack) in order to perform the reverse pass through the code to compute derivatives. Loops will result in many calls of a function to store data, vectorized functions result in many fewer calls (though with more data stored each call).
For Matlab the operator-overloaded AD tools are relatively robust, my own tool MAD has been used for many years but only supports forward mode. It is also integrated within the TOMLAB optimization library. The source transformation tools may require more interaction with the developer to get the coverage of all the Matlab functions used in your code.
Regards Shaun
Steve Grikschat
2020-10-8
Updated for R2020b
Optimization Toolbox now includes automatic differentiation for problems built with the problem-based workflow. Nonlinear constrained and unconstrained problems now solve with fmincon and fminunc using automatic differentiation.
This blog post by Alan Weiss explains it excellently
For more information, see the following
0 个评论
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!