🔒 Line search from scratch for gradient descent

[prime wave]

Hi guys, going through my text book i stumbled upon the following statement (see picture) and decided to test its validity by implementing it in Python.

def objective_fct(point):
    """custom loss function
    """
    A = np.array([[1,1],[1,1]])
    b = np.array([[4],[2]])
    c = np.array([1])
    return (point.T@A@point + b.T@point + c).item()

def objective_gradient(point):
    return 2*A@point+b

def ag_test(objective_fct,current_point,eta,c,desc_direction):
    # computes the Armijo-Goldstein test and returns a boolean value
    right = objective_fct(current_point)-c*eta*desc_direction.T@objective_gradient(current_point)
    left = objective_fct(current_point-eta*desc_direction)
    return (right-left>0)

# starting point, could be a random guess too
theta_0 = np.array([[0],[0]])

def steepest_descent(theta_0,n_steps,eps):
    """
    implements the steepest descent algorithm for a quadratic objective function
    """
    c = 10**-4
    states = [theta_0]
    up = upperbound_stepsize(np.array([[1,1],[1,1]]),eps)
    step_size,copy = up, up
    
    for t in range(n_steps):
        theta_t = states[-1]
        while not ag_test(objective_fct,theta_t,step_size,c,objective_gradient(theta_t)):
            step_size-=c  # shrink the step size
            #print(f"Step size: {step_size}")
        
        states.append(theta_t - step_size*objective_fct(theta_t))
        step_size = copy  # reset the step size to the max

        # add a breaking statement if we have redundant calculations
        if np.linalg.norm(states[-1]-states[-2],ord=2)<10**-8:
            return (states,t)
        
    return states,step_size

steps, n_steps = steepest_descent(theta_0,1000,0.1)
x = []
for k in range(len(steps)):
    x.append(steepest_descent(A,b,c,steps[k]))
x

[wise gale]

@prime wave

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[prime wave]

For context: L represents the objective function, eta is the step-size, d_t is the descent direction (in my case the opposite of the gradient evaluated at the current point theta_t.
My initial point is (0,0) and my initial step size is 1/max(lambda(A)), A being the 2x2 matrix used in my objective function. For some reason, the algo takes forever to run, the breaking condition in the test is never reached, am I doing something wrong or is it my example objective function that is not suited?
Thanks

here is my upper_bound function too

def upperbound_stepsize(A,eps=0.01):
    """
    computes the upper bound constant stepsize according to the theorem stated before
    I put 1 instead of 2 in the numerator of the fraction because I removed the 0.5 factor in the 
    quadratic form and included it in the A matrix rather. The validity of the bound is not altered by this.
    """
    return 1/np.max(np.linalg.eigvals(A))-eps

[wise gale]

@prime wave

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.