"""对应第6.2讲第31—34页：比较三种步长。运行后保存曲线。"""
from pathlib import Path
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize_scalar

a = np.array([4., 25., 50.])
demand = 10.

def f(x):
    return np.sum(a*x + x**3/3)

def solve(strategy, max_iter=10000, tolerance=1e-7):
    x = np.ones(3)*demand/3
    history = []
    for k in range(max_iter):
        c = a + x**2
        y = np.zeros(3)
        y[np.argmin(c)] = demand
        d = y - x
        gap = -c @ d
        history.append(float(max(gap, 0)))
        if gap < tolerance:
            break
        if strategy == 'decreasing':
            alpha = 1/(k+2)
        elif strategy == 'exact':
            # 只在线段上找，因此步长限定在[0,1]。
            ans = minimize_scalar(lambda t: f(x+t*d), bounds=(0, 1),
                                  method='bounded', options={'xatol':1e-14})
            alpha = ans.x
        elif strategy == 'backtracking':
            alpha = 1.
            while f(x+alpha*d) > f(x) - 0.25*alpha*gap:
                alpha *= 0.5
        else:
            raise ValueError(strategy)
        x = x + alpha*d
    return x, np.array(history)

if __name__ == '__main__':
    plt.figure(figsize=(8,5))
    for strategy in ['decreasing', 'exact', 'backtracking']:
        x, gaps = solve(strategy)
        print(strategy, 'iterations=',len(gaps), 'x=',x,
              'f=',f(x), 'gap=',gaps[-1])
        plt.semilogy(np.arange(len(gaps)),np.maximum(gaps,1e-14),label=strategy)
    plt.xlabel('Iteration')
    plt.ylabel('Frank-Wolfe gap')
    plt.legend()
    plt.tight_layout()
    target=Path(__file__).resolve().parent.parent/'运行结果'/'FrankWolfe_三种步长.png'
    target.parent.mkdir(exist_ok=True)
    plt.savefig(target,dpi=160)
    print('Saved:',target)
