Coordinate Descent One Coordinate

Problem

Perform one exact coordinate-descent update on f(x) = 0.5 * x^T A x - b^T x.

Set coordinate j to the exact minimizer (b[j] - sum over k != j of A[j][k] * x[k]) / A[j][j], leaving all other coordinates unchanged. If A[j][j] is zero, leave x[j] unchanged. Return the updated list.

Hint

The exact minimizer along one coordinate comes from setting the partial derivative to zero.

Test cases

case 1

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

expected: [0.25,0]

case 2

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

expected: [0.25,0.5833333333333334]

case 3

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

expected: [1,-1,-0.25]

case 4

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

expected: [1,2]

Starter codePython

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

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