June 4th 2018

Primal v.s. Primal-Dual

Since 2015, large amount of convex optimziation algorithms arosed in all different kind of context. Among them there are two major class of approaches, primal only method and primal-dual method. Primal-dual method is very fexiable, can solve almost all convex optimzation problems while primal only method can only be applied to some restrictive problem class.

How do the two class of methods compare when you can apply both of them. To try to answer this question, we consider a simple class of problem, $$\min_x \frac{1}{2}\|A x - b\|^2 + \lambda\|x\|_1.$$ And our player are:

proximal gradient (primal only)

FISTA (primal only)

DRS (primal-dual)

ADMM (primal-dual)

Champello-Pock (primal-dual)

We compare them over number of iterations, operations per iterations, run time and theorectical convergence bound. This blog is not intent to make strong statement like primal only method always better than primal-dual method when feasible, but to reveal some interesting behaviors of the two classes of the algorithms.

Widget is loading comments...