Coordinate Descent Sweep

Problem

Run one full coordinate-descent sweep on f(x) = 0.5 * x^T A x - b^T x.

Visit coordinates j = 0 .. n-1 in order and set each to the exact minimizer (b[j] - sum over k != j of A[j][k] * x[k]) / A[j][j] using the most recently updated values. Skip coordinates whose diagonal entry is 0. Return the updated list.

Hint

Later coordinates see the updates already made earlier in the sweep.

Test cases

case 1

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

expected: [0.25,0.5833333333333334]

case 2

in: [[1,1],[[2,0],[0,5]],[4,5]]

expected: [2,1]

case 3

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

expected: [1,1]

Starter codePython

def coordinate_descent_sweep(x, A, b):
    # Your code here
    pass

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