Dogleg Step Lite

Problem

Compute the dogleg step for a 2D quadratic with diagonal Hessian diag(b0, b1).

The Newton point is pB = -g / diag(b0, b1). If ||pB|| <= radius use it. Otherwise compute the Cauchy point pU = -(g dot g / g dot B g) * g; if ||pU|| >= radius scale it to the boundary, else find the positive tau with ||pU + tau * (pB - pU)|| = radius and return that point. Return the step as a two-element list.

Hint

The dogleg path runs from the origin to the Cauchy point to the Newton point.

Test cases

case 1

in: [[0.5,0.5],1,1,10]

expected: [-0.5,-0.5]

case 2

in: [[4,3],1,1,1]

expected: [-0.8,-0.6]

case 3

in: [[10,10],1,1,0.5]

expected: [-0.35355339059327373,-0.35355339059327373]

case 4

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

expected: [-1,0]

Starter codePython

def dogleg_step_lite(g, b0, b1, radius):
    # Your code here
    pass

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