BFGS One Update (2x2)

Problem

Apply one BFGS update to an inverse Hessian approximation.

Given H, the parameter change s, and the gradient change y, compute rho = 1 / (y dot s) and H_new = H - rho * (s y^T H + H y s^T) + rho^2 * (y^T H y) s s^T + rho * s s^T. Return the new matrix as a list of rows; if y dot s is zero, return H unchanged.

Hint

Compute Hy and yHy first, then combine the four matrix terms.

Test cases

case 1

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

expected: [[0.9200000000000002,-0.27999999999999986],[-0.27999999999999986,0.52]]

case 2

in: [[[2,0.5],[0.5,1]],[1,-2],[0.5,1.5]]

expected: [[3.5600000000000005,-0.5200000000000002],[-0.5200000000000002,-1.1600000000000001]]

case 3

in: [[[1.5,0.2],[0.2,0.8]],[2,1],[-1,4]]

expected: [[17.6,4.9],[4.9,1.4749999999999996]]

case 4

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

expected: [[1,0],[0,1]]

Starter codePython

def bfgs_update(H, s, y):
    # Your code here
    pass

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