Parameter Selection and Pre-Conditioning for a Graph Form Solver

Chapter 4 in Emerging Applications of Control and System Theory, R. Tempo, S. Yurkovich, and P. Misra, Editors, pages 41-62, 2018. The longer version has a full description of numerical examples.

• EACST chapter

• Longer version

• Talk slides

• POGS software

In the paper Block Splitting for Distributed Optimization, Parikh and Boyd describe a method for solving a convex optimization problem, where each iteration involves evaluating a proximal operator and projection onto a subspace. In this paper we address the critical practical issues of how to select the proximal parameter in each iteration, and how to scale the original problem variables, so as to achieve reliable practical performance. The resulting method has been implemented as an open-source software package called POGS (Proximal Graph Solver), that targets multi-core and GPU-based systems, and has been tested on a wide variety of practical problems. Numerical results show that POGS can solve very large problems (with, say, a billion coefficients in the data), to modest accuracy in a few tens of seconds, where similar problems take many hours using interior-point methods.