L-BFGS Two-Loop Lite

Problem

Run the L-BFGS two-loop recursion for a small history.

Starting from p = q, loop over the correction pairs from newest to oldest applying p = p - alpha * y with alpha = (s dot p) / (y dot s), saving each alpha. Scale p by gamma, then loop oldest to newest applying p = p + s * (alpha - beta) with beta = (y dot p) / (y dot s). Return the resulting search direction.

Hint

Save each alpha in the backward pass and reuse them reversed in the forward pass.

Test cases

case 1

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

expected: [0.125,0.75]

case 2

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

expected: [0.25,-1.1111111111111112,2.3333333333333335]

case 3

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

expected: [2.4000000000000004,0.19999999999999996]

Starter codePython

def lbfgs_two_loop(q, s_list, y_list, gamma):
    # Your code here
    pass

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