Projected Gradient Box Step

Problem

Run projected gradient descent on the box-constrained quadratic f(x) = 0.5 * x^T A x + c^T x with A = [[3, 1], [1, 2]] and c = [-1, -2].

Starting from x, repeat n_iters times: compute grad = A x + c, take the step x = x - lr * grad, then clip each coordinate into [lo, hi]. Return the final two-element list.

Hint

The unconstrained minimum is (0, 1); the box only matters when it excludes that point.

Test cases

case 1

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

expected: [1.553585843712981e-7,0.9999997486245301]

case 2

in: [[2,2],0.1,50,-1,2]

expected: [0.0000622249483433113,0.9998993186679868]

case 3

in: [[-3,-3],0.05,200,-0.5,1]

expected: [3.4536742144027475e-7,0.9999994411837736]

case 4

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

expected: [0.5,0.5]

Starter codePython

def projected_gradient_box(x, lr, n_iters, lo, hi):
    # Your code here
    pass

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