import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize_scalar


np.random.seed(0)


N = 1000
GPA = np.random.normal(80, 10, N).clip(30, 100) / 100
PAPER = np.random.choice([0, 1], size=N, p=[0.8, 0.2])
One = np.ones(N)


X = np.column_stack((GPA, PAPER, One))
weight_real = np.array([1, 0.1, -0.85]) * 100
z = X @ weight_real
p = 1 / (1 + np.exp(-z))
y = np.random.binomial(1, p)


plt.figure(figsize=(8, 5), dpi=500)


for exp in range(3):


    w = np.zeros(X.shape[1])


    num_iterations = 1000000
    
    Iter = list()
    Gradient_norm = list()
    for i in range(num_iterations):
        z = X @ w
        y_pred = 1 / (1 + np.exp(-z))
        
        gradient = X.T @ (y_pred - y) / N
        
        norm = np.linalg.norm(gradient, 2)
        
        Iter.append(i)
        Gradient_norm.append(norm)
        
        
        if norm < 1e-6:
            break
        
        
        def g(alpha):
            w_new = w - alpha * gradient
            z = X @ w_new
            y_pred = 1 / (1 + np.exp(-z))
            return -np.mean(y * np.log(y_pred) + (1 - y) * np.log(1 - y_pred))
        
        
        if exp == 0:
            learning_rate = 10
        else:
            
            
            if exp == 1:
                alpha_m = 20
                g0 = g(0)
                while True:
                    if g(alpha_m) > g0:
                        break
                    else:
                        g0 = g(alpha_m)
                        alpha_m *= 2
                    
            
                
                result = minimize_scalar(g, method='golden', bracket=(0, alpha_m)) 
            
                learning_rate = result.x
            
            if exp == 2:
                alpha = 50
                g0 = g(0)
                while g(alpha) > g0 - alpha * 0.25 * norm ** 2:
                    alpha *= 0.5
                learning_rate = alpha
                
         
        w -= learning_rate * gradient
        
        if i % 1000 == 0:
            loss = -np.mean(y * np.log(y_pred) + (1 - y) * np.log(1 - y_pred))
            print(f"Iteration {i}: Loss = {loss}", w)
    
    print(w)
    plt.plot(Iter, Gradient_norm)
plt.legend(['fixed step size', 'exact line search', 'inexact line search'])
plt.yscale('log')
