Backtracking Line Search Step

Problem

Run backtracking line search on f(v) = v ** 2 along the descent direction -grad.

Start with step = 1.0 and shrink it by factor rho while (x - step * grad) ** 2 > x * x - c * step * grad * grad (the Armijo condition). Return the first step size that satisfies the condition.

Hint

Keep shrinking the step until the actual value lies under the Armijo line.

Test cases

case 1

in: [0.1,1,0.5,0.1]

expected: 0.0625

case 2

in: [0.5,1,0.5,0.1]

expected: 0.5

case 3

in: [1,0,0.5,0.1]

expected: 1

case 4

in: [3,2,0.5,0.25]

expected: 1

Starter codePython

def backtracking_line_search(x, grad, rho, c):
    # Your code here
    pass

4 test cases · run your code against them in the editor