[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


hello,

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

*Rationale:* Convergence theory for a large class of uncostrained
optimization
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
convex
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
general
case for which they converge.

*Assumptions:* I assumed that the function tends to (plus) infinity as it
approaches
its domain boundary. This is reasonable in the sense that if not true the
function
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
any,
non defined (None).

*Implementation:* The line search methods is the only block of the
optimization
routine(s) that needs to be changed significantly in order to handle such
functions.
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
instead
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
improved.

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
domain.
Whenever that happens fmin_bfgs catches the exception and calls
line_search_wolfe2.
Additionally line_search_wolfe2 will call the original _zoom method if the
bracketing
phase leads to finite-valued points. this ensures that for problems that are
defined
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)

and

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

All old and new tests pass.

regards,

Enrico
-------------- 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