[SciPy-Dev] PATCH: enhancing fmin_bfgs to handle functions that are not defined everywhere

Enrico Avventi eavventi@yahoo...
Mon Sep 20 11:47:47 CDT 2010


i would like to propose a patch for enhancing the optimization module. the
diff output is attached. let me know what do you think about it.

*Rationale:* Convergence theory for a large class of uncostrained
algorithms (descent methods) does not require the function to be defined
everywhere. In fact you just need a function that is defined in an open
set and whose sublevel set:

{x: f(x) <= f(x0) }

is compact where x0 is the starting point.
It would be helpful to let the optimization routines to handle the most
case for which they converge.

*Assumptions:* I assumed that the function tends to (plus) infinity as it
its domain boundary. This is reasonable in the sense that if not true the
either tends to minus infinity or can be extended to a larger set.
The function is assumed to be infinite ouside its domain with derivative, if
non defined (None).

*Implementation:* The line search methods is the only block of the
routine(s) that needs to be changed significantly in order to handle such
In particular i modified the line search method (line_search_wolfe2) to call
a new zoom algorith (_barrier_zoom) whenever one of the bracketing points
leads to an unfeasible point.
_barrier_zoom uses linear-logarithmic and quadratic-logarithmic interpolants
of quadratic and cubic ones in order to generate new candidates steps.
Note that the interpolation strategy may not be ideal and could be certainly

All descent algorithms can be easily adapted to use such a line search, here
i started
with fmin_bfgs.

In order to adapt it i added a new exception (DomainError) and modified phi
and derphi
in line_search_wolfe1 to raise it when they are evaluated outside the
Whenever that happens fmin_bfgs catches the exception and calls
Additionally line_search_wolfe2 will call the original _zoom method if the
phase leads to finite-valued points. this ensures that for problems that are
everywhere the old code-path is always taken.
Testing:* I added two functions for testing the scalar_search_wolfe2

phi1(x) = -100 x - log(1-x)


phi2(x) = -100 x + (1-x)^-k.

All old and new tests pass.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-dev/attachments/20100920/44dfb82a/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: svn_diff
Type: application/octet-stream
Size: 12635 bytes
Desc: not available
Url : http://mail.scipy.org/pipermail/scipy-dev/attachments/20100920/44dfb82a/attachment-0001.obj 

More information about the SciPy-Dev mailing list