BFGS Curvature Check

Problem

Check the curvature condition before a BFGS update.

Given s = x_new - x and y = grad_new - grad_old, return [ys, yy_ss, passed] where ys = s dot y, yy_ss = (y dot y) / (s dot s) with 0.0 when s is zero, and passed is the boolean ys > eps. A positive ys keeps the updated inverse Hessian positive definite.

Hint

If the curvature condition fails, skip the update or damp the pair.

Test cases

case 1

in: [[1,1],[2,3],1e-8]

expected: [5,6.5,true]

case 2

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

expected: [-2.5,0.5,false]

case 3

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

expected: [0,0,false]

case 4

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

expected: [-2,0.5,false]

Starter codePython

def bfgs_curvature_check(s, y, eps):
    # Returns [ys, yy_ss, passed]
    # Your code here
    pass

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