binary search of maximum on concave function

gistfile1.txt

import matplotlib.pyplot as plt
import numpy as np
import math


def find_maximum(f, min_x, max_x, epsilon=1e-3):
    def binary_search(l, r, fl, fr, epsilon):
        mid = l + (r - l) / 2
        fm = f(mid)
        binary_search.eval_count += 1
        if (fm == fl and fm == fr) or r - l < epsilon:
            return mid, fm
        if fl > fm >= fr:
            return binary_search(l, mid, fl, fm, epsilon)
        if fl <= fm < fr:
            return binary_search(mid, r, fm, fr, epsilon)
        p1, f1 = binary_search(l, mid, fl, fm, epsilon)
        p2, f2 = binary_search(mid, r, fm, fr, epsilon)
        if f1 > f2:
            return p1, f1
        else:
            return p2, f2

    binary_search.eval_count = 0

    best_th, best_value = binary_search(min_x, max_x, f(min_x), f(max_x), epsilon)
    print("Found maximum %f at x = %f in %d evaluations" % (best_value, best_th, binary_search.eval_count))
    return best_th, best_value


def function1(x):
    return (5 -(x + 3)**2 - 0.1 * (x - 3) ** 4) / 100 + math.cos(1.0 + x / 3.0) * 10.0 - x * 2 


mx, my = find_maximum(function1, -10, 10)

x = np.arange(-10, 10, 0.2)

plt.plot(x, np.vectorize(function1)(x))


plt.annotate('max', xy=(mx, my), xytext=(mx + 1, my + 0.5),
             arrowprops=dict(facecolor='black', shrink=0.05),
             )

plt.show()