# Nonsmooth Gauss-Seidel minimization (coordinate descent)

I have attempted to implement the coordinate descent algorithm for a separably convex problem of the form

$$\min \sum f_i(x_i) \\ \text{s.t.} \ Ax = b$$

using the augmented Lagrangian $$L(x,\lambda) = \sum f_i(x_i) + \lambda'(Ax-b) + \rho\|Ax-b\|^2$$

Expressing the norm term as $\|Ax-b\|_2^2 = \sum_i \Big[\tilde{A}_{ii}x_i^2 + x_i\sum_{j \neq i}\tilde{A}_{ij}x_j \Big] -2\sum_i x_i\sum_j A_{ij}b_j +b'b$, where $\tilde{A} := A'A$, we can rewrite the Lagrangian as

$$L(x,\lambda) = -\lambda'b + \rho b'b + \sum_{i=1}^n \Big( f_i(x_i) + \rho \tilde{A}_{ii}x_i^2 + x_i\Big[ \lambda' A_i - 2\rho b' A_i + \rho \sum_{j \neq i} \tilde{A}_{ij} x_j \Big ]\Big)$$

Now, as I understand it, we should be able to cyclically minimize $L_i(x_i,\lambda)$ while treating $x_j$ for $j \neq i$ as constant. That is the gist of coordinate descent, right? But I'm just not getting the right results. I've confirmed that I haven't made any mistake in rewriting the $\|Ax-b\|$ term. The minimization solver seems to be correct as well.

This makes me suspect I've made some conceptual error. What is my misunderstanding here?

• What do you mean "the right results", exactly? What are you expecting the algorithm to accomplish, and what are you seeing instead? What is the evidence that the results are not correct? – Michael Grant Aug 3 '15 at 17:00
• After hours of fiddling, it kind of seems that it actually converges after a huge amount of iterations, when keeping $\rho$ constant - incrementing it after each iteration wreaks havoc on convergence. I'm having a lot of trouble diagnosing the issue since it's a 100% from scratch implementation... – Benjamin Lindqvist Aug 3 '15 at 18:15
• Also, it's absolutely gut wrenchingly slow compared to solving via dual subgradient with a primal averaging sequence. I thought it was supposed to be a lot faster. (testing on LP:s with a priori known optima btw) – Benjamin Lindqvist Aug 3 '15 at 18:17