A Python package for typeII Anderson accelerated DouglasRachford splitting (A2DR).
Project description
a2dr
a2dr
is a Python package for solving largescale nonsmooth convex optimization problems with general linear constraints, with separable objective functions accessible through their proximal operators. It exploits the separability of the objective functions and the sparsity in the linear constraints, and utilizes the power of Anderson acceleration to achieve fast and robust convergence and scalability to multiple processors. The current version is 0.2.3.post2
.
It is an implementation of typeII Anderson accelerated DouglasRachford splitting, based on our paper A. Fu, J. Zhang, and S. Boyd (2019).
Installation
To install using pip (recommended), run:
pip install a2dr
To install a2dr
from source, first make sure that you have setuptools
installed. Then follow the steps below:
 Clone the
a2dr
git repository.  Navigate to the toplevel of the cloned directory and run:
python setup.py install
To test the installation with nose, first make sure that you have nose installed. Then run:
nosetests a2dr
The requirements are:
 Matplotlib
 CVXPY
 NumPy
 SciPy
 Python 3.x
Please file an issue on Github if you want Python 2 support.
Problem
a2dr
solves problems of the following form:
minimize f_1(x_1) + ... + f_N(x_N)
subject to A_1x_1 + ... + A_Nx_N = b.
where f_i (i=1,...,N) are convex, closed and proper, and are only accessible through their proximal operators. Notice that f_i can take infinite values, and in particular constraints can be included in the objectives with the help of indicator functions.
Proxaffine forms
The above formulation is also referred to as proxaffine forms in the literature (see e.g., Epsilon). When it is seen as a standard form for generic convex optimization problems, the major advantage of proxaffine forms compared to the more widely used conic forms include:
 Privacy: suitable for peertopeer optimization with privacy requirements.
 In practice, the data and source code that define the proximal oracle can be securely encrypted (e.g., via compilation) so that privacy is preserved. For example, in Python, we can convert the
.py
file containing the proximal operator function into an encrypted.so
file via the Cython extension.
 In practice, the data and source code that define the proximal oracle can be securely encrypted (e.g., via compilation) so that privacy is preserved. For example, in Python, we can convert the
 Compactness: straightforward canonicalization/transformation and lower dimensional representations.
For a bit more detailed introduction to proxaffine forms and the comparisons with conic forms, see our companion slides.
Usage
After installing a2dr
, you can import a2dr
using
import a2dr
This module exposes a function a2dr (the solver), which can be used via a2dr.a2dr
, or directly imported using
from a2dr import a2dr
The function a2dr is called with the command
a2dr_result = a2dr(p_list, A_list=[], b=np.array([]), v_init=None, n_list=None, max_iter=1000, t_init=1/10, eps_abs=1e6, eps_rel=1e8, precond=True, ada_reg=True, anderson=True, m_accel=10, lam_accel=1e8, aa_method='lstsq', D_safe=1e6, eps_safe=1e6, M_safe=int(max_iter/100), verbose=True)
Parameters:
The arguments p_list
, A_list
and b
correspond to the problem data.
p_list
is the list of proximal operators of f_i. Each element ofp_list
is a Python function, which takes as input a vector v and parameter t > 0 and outputs the proximal operator of f_i evaluated at (v,t).A_list
is the list of A_i. The listsp_list
andA_list
must be given in the same order i = 1,...,N.b
is the vector b. Notice thatA_list
andb
are optional, and when omitted, the solver recognizes the problem as one without linear constraints. Also notice that in such cases,A_list
andb
have to be omitted together, and eitherv_init
orn_list
has to be provided to declare the dimension of each x_i.
For information on the other optional hyperparameters, please refer to our companion paper (Algorithm 2) and the source code comments of the function a2dr in solver.py.
Returns:
The returned object a2dr_result
is a dictionary containing the keys 'x_vals'
, 'primal'
, 'dual'
, 'num_iters'
and 'solve_time'
:
 The output
x_vals
is a list of x_1,...,x_N from the iteration with the smallest residuals. primal
anddual
are arrays containing the primal and dual residual norms for the entire iteration process, respectively. The value
num_iters
is the total number of iterations, andsolve_time
is the algorithm runtime.
When the linear equality constraint is infeasible, the solver will print the corresponding flag and return None
for all the outputs.
Other tools
The module a2dr
also comes with several additional tools that facilitates the transformation of the problems into the required input format described above as well as tests and visualization. In particular, it come with a package for proximal operators, which can be imported via
import a2dr.proximal
It also comes with some tests and visualization tools, which can be imported via
import a2dr.tests
Example
We showcase the usage of the solver function a2dr as well as the the tool packages a2dr.proximal
and a2dr.tests
with the following example. More examples can be found in the examples/ directory.
# Nonnegative least squares (see our companion paper for more details) import numpy as np import numpy.linalg from scipy import sparse from a2dr import a2dr from a2dr.proximal import * from a2dr.tests.base_test import BaseTest # Problem data. np.random.seed(1) m, n = 150, 300 density = 0.001 X = sparse.random(m, n, density=density, data_rvs=np.random.randn) y = np.random.randn(m) # Convert problem to standard form. prox_list = [lambda v, t: prox_sum_squares_affine(v, t, F=X, g=y), prox_nonneg_constr] A_list = [sparse.eye(n), sparse.eye(n)] b = np.zeros(n) # Solve with DRS. drs_result = a2dr(prox_list, A_list, b, anderson=False) # Solve with A2DR. a2dr_result = a2dr(prox_list, A_list, b, anderson=True) bt = BaseTest() bt.compare_total(drs_result, a2dr_result)
Citing
If you wish to cite a2dr
, please use the following:
@article{a2dr,
author = {Fu, A. and Zhang, J. and Boyd, S.},
title = {Anderson Accelerated {D}ouglas{R}achford Splitting},
journal = {http://stanford.edu/~boyd/papers/a2dr.html},
year = {2019},
}
@misc{a2dr_code,
author = {Fu, A. and Zhang, J. and Boyd, S.},
title = {{a2dr}: Anderson Accelerated {D}ouglas{R}achford Splitting, version 0.2.3.post2},
howpublished = {\url{https://github.com/cvxgrp/a2dr}},
year = {2020}
}
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size a2dr0.2.3.post2py3noneany.whl (43.4 kB)  File type Wheel  Python version py3  Upload date  Hashes View 
Filename, size a2dr0.2.3.post2.tar.gz (34.8 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for a2dr0.2.3.post2py3noneany.whl
Algorithm  Hash digest  

SHA256  5eb68fbfd88298f33f3242d48cc16d642d3b9911819bff21615699ea81340a45 

MD5  76c35c1473cdd5c30d5c301bb58aef13 

BLAKE2256  da2ee397af0fbf91ef73a6914998b0927684f97227ca4275612100b0ad427ed7 