[SciPy-User] [SciPy-user] optimization using fmin_bfgs with gradient information

[Ernest Adrogué]

23/07/09 @ 10:42 (+0200), thus spake Sebastian Walter:
> 1)
> approx_fprime uses probably finite differences to approximate the
> gradient, so at x = 2
> it computes  (f(2+epsilon) - f(2))/epsilon =  (2+epsilon)**2/epsilon
> which can be very large
> 
> 2) When using AD to evaluate derivatives, only one path through the
> control flow graph (which is defined by the if statement in your
> function) is taken.
> I.e. if x<2, AD will not know that for x>=2 it would have taken
> another way through the control flow graph of your algorithm.
> 
> I.e. it  would compute
> f'(x<2) = 0 and f'(x>=2) = x**2  without realizing that the function
> is nondifferentiable at that point.
> 
> 3)
> If you have such an objective function as you have shown above, then
> your optimization problem is not well-formed because it does not have
> a real minimizer x_*.
> I'd assume that your objective function looks more like
> f(x) = abs(x)
> which is non-differentiable at x=0.
> This kind of objective function destroys the convergence properties of
> algorithms that assume continuously differentiable objective
> functions, i.e. the convergence to the minimizer can be very slow.
> For such problems, special purpose algorithms, e.g.  the so-called
> "bundle methods" can be used which converge superlinearly, as far as I
> know.

Nice explanation. I have made some tests with a simplified
model, and have found fmin_slsqp to be the fastest method by far.
It takes around 1 minute and a half to estimate a model with 128
parameters.

p	time
16	0.36s
32	4.56s
64	32.74s
128	3.66min

Second comes fsolve, but its performance decreases rapidly as
the number of parameters increases.

So I probably will stick to slsqp, unless I find a better solution.
These "bundle methods" sound interesting. I have found an
interesting paper with one such algorithm described in detail,
which might come handy if I finally decide to try it out. In case
someone is interested, is here:
http://www.mathematik.uni-trier.de/~huebner/software/bundle_method_documentation.pdf

Ernest