Exact Line Search Quadratic Step

Problem

For f(x) = 0.5 x^T A x - b^T x, the exact minimizer along the steepest descent direction d = -(A x - b) is lr = ||g||^2 / (g^T A g) with g = A x - b.

Given A as nested rows, b, and the current point x, return the optimal step size.

Hint

Set the directional derivative along the descent direction to zero.

case 1

in: [[[2,0],[0,2]],[0,0],[1,1]]

expected: 0.5

case 2

in: [[[1,0],[0,4]],[1,0],[0,0]]

expected: 1

case 3

in: [[[3,1],[1,3]],[1,1],[1,-1]]

expected: 0.4166666666666667

Starter codePython

def exact_line_search_quadratic_step(a, b, x):
    # Your code here
    pass

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