ADMM - alternating-direction method of multipliers

Usage

sol = admm(x_0,f1,f2,param);
sol = admm(x_0,f1,f2);
[sol,info,objective] = admm(...);

Input parameters

x_0 Starting point of the algorithm
f1 First function to minimize
f2 Second function to minimize
param Optional parameter

Output parameters

sol Solution
info Structure summarizing informations at convergence

Description

admm (using alternating-direction method of multipliers) solves:

\begin{align*} sol = \min_x f_1(y) + f_2(x) \hspace{1cm} s.t. \hspace{1cm} y=Lx \\\\ \end{align*}

where \(x\) is the optimization variable.

Please read the paper of Boyd "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers" to be able to understand this demonstration file.

f1 is a structure representing a convex function. Inside the structure, there have to be the prox of the function that can be called by f1.proxL and the function itself that can be called by f1.eval. WARNING !!! The proxL of f1 is not the usual prox! But the solution to this problem:

\begin{equation*} prox_{f_1, \gamma }^L(z)=\min_x \frac{1}{2} \|Lx-z\|_2^2 + \gamma f_1(x) \end{equation*}

f2 is a structure representing a convex function. Inside the structure, there have to be the prox of the function that can be called by f2.prox and the function itself that can be called by f2.eval. The prox of f2 is the usual prox:

\begin{equation*} prox_{f_2, \gamma }(z)=\min_x \frac{1}{2} \|x-z\|_2^2 + \gamma f_2(x) \end{equation*}

param a Matlab structure containing solver paremeters. See the function solvep for more information. Additionally it contains those aditional fields:

  • param.L : linear operator that link \(x\) and \(y\): \(y=Lx\). This operator can be given in a matrix form (default Identity) or as a function handle.

References:

P. Combettes and J. Pesquet. Proximal splitting methods in signal processing. Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pages 185--212, 2011.

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1--122, 2011.