#!/usr/bin/env python3
# Source: t4-optimization.html
import numpy as np

def run(kappa, method, tol=1e-6, max_it=100000):
    # f(x) = 0.5 x^T A x with eigenvalues 1 and kappa
    A = np.diag([1.0, kappa]); L, mu = kappa, 1.0
    x = np.array([1.0, 1.0]); v = np.zeros(2); y = x.copy()
    for t in range(max_it):
        if np.linalg.norm(x) < tol:
            return t
        if method == "gd":
            x = x - (1 / L) * (A @ x)
        elif method == "heavy":
            a = 4 / (np.sqrt(L) + np.sqrt(mu)) ** 2
            b = ((np.sqrt(kappa) - 1) / (np.sqrt(kappa) + 1)) ** 2
            x_new = x - a * (A @ x) + b * v
            v = x_new - x; x = x_new
        elif method == "nesterov":
            b = (np.sqrt(kappa) - 1) / (np.sqrt(kappa) + 1)
            x_new = y - (1 / L) * (A @ y)
            y = x_new + b * (x_new - x); x = x_new
    return max_it

for k in [10, 100, 1000]:
    print(k, {m: run(k, m) for m in ["gd", "heavy", "nesterov"]})
# 10   {'gd': 132,   'heavy': 27,  'nesterov': 44}
# 100  {'gd': 1375,  'heavy': 95,  'nesterov': 158}
# 1000 {'gd': 13809, 'heavy': 321, 'nesterov': 519}
