#!/usr/bin/env python3
# Source: t4-optimization.html
import numpy as np
from math import erf, sqrt, pi

def rbf(a, b, ls=0.3):
    return np.exp(-0.5 * (a[:, None] - b[None, :]) ** 2 / ls ** 2)

def gp_posterior(X, y, Xs, noise=1e-6):
    K = rbf(X, X) + noise * np.eye(len(X))
    Ks = rbf(X, Xs)
    Lc = np.linalg.cholesky(K)
    alpha = np.linalg.solve(Lc.T, np.linalg.solve(Lc, y))
    mu = Ks.T @ alpha
    v = np.linalg.solve(Lc, Ks)
    sd = np.sqrt(np.maximum(1.0 - (v ** 2).sum(axis=0), 1e-12))
    return mu, sd

def expected_improvement(mu, sd, best, xi=0.01):
    z = (best - mu - xi) / sd                 # minimization
    cdf = 0.5 * (1 + np.vectorize(erf)(z / sqrt(2)))
    pdf = np.exp(-0.5 * z ** 2) / sqrt(2 * pi)
    return (best - mu - xi) * cdf + sd * pdf

f = lambda x: np.sin(3 * x) + 0.5 * x         # stand-in for validation loss
grid = np.linspace(0, 2, 401)
X = np.array([0.1, 1.0, 1.9]); y = f(X)
for step in range(6):
    mu, sd = gp_posterior(X, y - y.mean(), grid)
    ei = expected_improvement(mu + y.mean(), sd, y.min())
    x_next = grid[np.argmax(ei)]
    X, y = np.append(X, x_next), np.append(y, f(x_next))
print("best x = %.3f, best f = %.3f" % (X[y.argmin()], y.min()))
# best x = 1.525, best f = -0.228   (true minimum near x = 1.515)
