Setting convergence criteria for scipy.optimize.fmin (and others)

Question

I am working on an optimization task where cost function evaluations are very expensive, and some error can be tolerated. I'm using some pre-packaged scipy methods from scipy.optimize to get started. The first one I'm working with is fmin, which implements the nelder mead simplex algorithm.

This function has two convergence related parameters xtol and ftol, which (as I understand it) specifiy a convergence criteria where if x or f (the parameter set, and the cost respectively) change by less than xtol or ftol on an iteration, the function returns.

However, since cost functions are so expensive for me, I want to also be able to specify a cost threshold where it will return immediately if it finds a point with less cost than the threshold.

Is it possible to specify this threshold for scipy.optimize.fmin?

Bonus question: I haven't looked in detail at many other methods, but it doesn't look like this threshold option exists for those either. Is this typical for scipy optimization methods? Would it be valuable for me to try to contribute this functionality?

Answer 1

It is possible to stop the iteration for any criterion that can be expressed as a function of x. The idea here is to hijack the callback method and use exceptions for flow control. Here are two solutions that exploit this idea:

from scipy.optimize import fmin_bfgs
import numpy as np
f = lambda x: np.linalg.norm(x**2)
x0 = np.random.rand(100)

Solution 1:

global result

class SmallEnoughException(Exception):
    pass

def check_conv_criteria(xk):
    global result
    if np.linalg.norm(xk) < 0.1:
        result = xk
        raise SmallEnoughException()

try:
    x, _, _ = fmin_bfgs(f, x0, callback=check_conv_criteria)
except SmallEnoughException:
    x = result

Solution 2:

class StopOptimizingException(Exception):
    pass

class CallbackCollector:

    def __init__(self, f, thresh):
        self._f  = f
        self._thresh = thresh

    def __call__(self, xk):
        if self._f(xk) < self._thresh:
            self.x_opt = xk
            raise StopOptimizingException()

try:
    cb = CallbackCollector(f, thresh=0.2)
    x, _, _ = fmin_bfgs(f, x0, callback=cb)
except StopOptimizingException:
    x = cb.x_opt