Steepest Descent Path Step

Problem

Take one exact-line-search steepest descent step on the quadratic f(x) = 0.5*x^T*A*x - b^T*x with A = [[a, b], [b, c]] and b_vec = (b1, b2).

The gradient is g = A*x - b_vec and the optimal step is alpha = (g^T g) / (g^T A g). Return x - alpha*g as [x1, x2].

Hint

For a quadratic, the exact line search minimizes f along the negative gradient direction.

case 1

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

expected: [0,0]

case 2

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

expected: [0.7384615384615385,-0.04615384615384621]

case 3

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

expected: [1,0]

case 4

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

expected: [0.35714285714285715,0.7142857142857143]

Starter codePython

def steepest_descent_step(point, a, b, c, b1, b2):
    # Return the updated [x, y]
    # Your code here
    pass

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