GPU acceleration of ADMM for large-scale quadratic programming

M. Schubiger, G. Banjac and J. Lygeros

Journal of Parallel and Distributed Computing (to appear), May 2020.
BibTeX  Preprint  Code 

@article{SBL:2020,
  author = {M. Schubiger and G. Banjac and J. Lygeros},
  title = {{GPU} acceleration of {ADMM} for large-scale quadratic programming},
  journal = {Journal of Parallel and Distributed Computing (to appear)},
  year = {2020}
}

The alternating direction method of multipliers (ADMM) is a powerful operator splitting technique for solving structured convex optimization problems. Due to its relatively low per-iteration computational cost and ability to exploit sparsity in the problem data, it is particularly suitable for large-scale optimization. However, the method may still take prohibitively long to compute solutions to very large problem instances. Although ADMM is known to be parallelizable, this feature is rarely exploited in real implementations. In this paper we exploit the parallel computing architecture of a graphics processing unit (GPU) to accelerate ADMM. We build our solver on top of OSQP, a state-of-the-art implementation of ADMM for quadratic programming. Our open-source CUDA C implementation has been tested on many large-scale problems and was shown to be up to two orders of magnitude faster than the CPU implementation.

On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization

G. Banjac and J. Lygeros

April 2020.
BibTeX  Preprint 

@article{BL:2020,
  author = {G. Banjac and J. Lygeros},
  title = {On the asymptotic behavior of the {D}ouglas-{R}achford and proximal-point algorithms for convex optimization},
  year = {2020}
}

The authors in (Banjac et al., 2019) recently showed that the Douglas-Rachford algorithm provides certificates of infeasibility for a class of convex optimization problems. In particular, they showed that the difference between consecutive iterates generated by the algorithm converges to certificates of primal and dual strong infeasibility. Their result was shown in a finite dimensional Euclidean setting and for a particular structure of the constraint set. In this paper, we extend the result to Hilbert spaces and a general nonempty closed convex set. Moreover, we show that the proximal-point algorithm applied to the set of optimality conditions of the problem generates similar infeasibility certificates.