66

1

7

4

# ProximalAlgorithms.jl

Proximal algorithms (also known as "splitting" algorithms or methods) for nonsmooth optimization in Julia.

This package can be used in combination with ProximalOperators.jl (providing first-order primitives, i.e. gradient and proximal mapping, for numerous cost functions) and AbstractOperators.jl (providing several linear and nonlinear operators) to formulate and solve a wide spectrum of nonsmooth optimization problems.

StructuredOptimization.jl provides a higher-level interface to formulate and solve problems using (some of) the algorithms here included.

### Quick start

To install the package, simply issue the following command in the Julia REPL:

``````] add ProximalAlgorithms
``````

Check out these test scripts for examples on how to apply the provided algorithms to problems.

### Implemented Algorithms

Algorithm Function Reference
Douglas-Rachford splitting algorithm `DouglasRachford` [1]
Forward-backward splitting (i.e. proximal gradient) algorithm `ForwardBackward` [2], [3]
Vũ-Condat primal-dual algorithm `VuCondat` [4], [6], [7]
Davis-Yin splitting algorithm `DavisYin` [9]
Asymmetric forward-backward-adjoint algorithm `AFBA` [10]
PANOC (L-BFGS) `PANOC` [11]
ZeroFPR (L-BFGS) `ZeroFPR` [12]
Douglas-Rachford line-search (L-BFGS) `DRLS` [13]

### Contributing

Contributions are welcome in the form of issues notification or pull requests. We recommend looking at already implemented algorithms to get inspiration on how to structure new ones.

### References

[1] Eckstein, Bertsekas, On the Douglas-Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators, Mathematical Programming, vol. 55, no. 1, pp. 293-318 (1989).

[2] Tseng, On Accelerated Proximal Gradient Methods for Convex-Concave Optimization (2008).

[3] Beck, Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems, SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 183-202 (2009).

[4] Chambolle, Pock, A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging, Journal of Mathematical Imaging and Vision, vol. 40, no. 1, pp. 120-145 (2011).

[5] Boyd, Parikh, Chu, Peleato, Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1-122 (2011).

[6] Vũ, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Advances in Computational Mathematics, vol. 38, no. 3, pp. 667-681 (2013).

[7] Condat, A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, Journal of Optimization Theory and Applications, vol. 158, no. 2, pp 460-479 (2013).

[8] Parikh, Boyd, Proximal Algorithms, Foundations and Trends in Optimization, vol. 1, no. 3, pp. 127-239 (2014).

[9] Davis, Yin, A Three-Operator Splitting Scheme and its Optimization Applications, Set-Valued and Variational Analysis, vol. 25, no. 4, pp. 829–858 (2017).

[10] Latafat, Patrinos, Asymmetric forward–backward–adjoint splitting for solving monotone inclusions involving three operators, Computational Optimization and Applications, vol. 68, no. 1, pp. 57-93 (2017).

[11] Stella, Themelis, Sopasakis, Patrinos, A simple and efficient algorithm for nonlinear model predictive control, 56th IEEE Conference on Decision and Control (2017).

[12] Themelis, Stella, Patrinos, Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms, SIAM Journal on Optimization, vol. 28, no. 3, pp. 2274–2303 (2018).

[13] Themelis, Stella, Patrinos, Douglas-Rachford splitting and ADMM for nonconvex optimization: Accelerated and Newton-type algorithms, arXiv preprint (2020).

10/19/2017

2 days ago

106 commits