ABOUT THIS PACKAGE:
* DECOPT stands for DEcomposition Convex OPTimization
* This is a software package written in MATLAB that implements several
first-order primal-dual decomposition algorithm for solving the following
constrained convex minimization problem:
min_x { F(x, r) := f(x) + g(r) } (P)
s.t.: A(x) - r = b, l <= x <= u,
where f and g are both proper, closed and convex from R^p to R cap {+inf}
A is a linear operator from R^p to R^n, b in R^n
l and u are the upper and lower bound of x, which can be -inf and +inf.
* DECOPT generally solves many different instances of (P) including the smooth
and nonsmooth problems. It requires to provide the proximal operator of f and g
and the function to evaluate the value of f and g.
It also requires the operator A and its conjugate A^T or matrix A.
Recall that the proximal operator of a proper, closed and convex function f
is defined as:
prox_f(x) := argmin_z{ f(z) + (1/2)|z - x|^2_2 }
Many functions f where their proximal operator can efficiently be computed
(e.g., in a closed form or with a polynomial time algorithm).
* DECOPT has directly been customized for the following problems:
1) L1/L2: The unconstrained L1/L2 LASSO problem:
min_x 0.5*|A*x - b|_2^2 + |W.*x|_1
2) L1/L1: The L1/L1 problem:
min_x |A*x - b|_1 + |W.*x|_1
3) Square-root L1/L2 LASSO problem of the form:
min_x |A*x - b|_2 + |W.*x|
4) L1/L2con: The basis pursuit denoise (BPDN) problem:
min_x |W.*x|_1 s.t. |A*x - b|_2 <= delta
5) L2/L1con: The L1-constrained LASSO problem:
min_x 0.5*|A*x - b|_2^2 s.t. |x|_1 <= delta,
6) BP: The basis pursuit (BP) problem:
min_x |W.*x|_1 s.t. A*x == b.
Here, A is a linear operator (it works both with matrices and operators)
W is the weighted vector (positive vector)
delta is the noise level (positive number)
* DECOPT v.1.0 is developed by Quoc Tran-Dinh at Laboratory for Informations
and Inference System (LIONS), Ecole Polytechnique Federale de Lausanne (EPFL),
Switzerland.
This is the joint work with Volkan Cevher at LIONS/EPFL.
* Copyright 2014 Laboratory for Information and Inference Systems (LIONS)
EPFL Lausanne, 1015-Lausanne, Switzerland.
* See the file LICENSE for full license information.
REFERENCES:
[1]. Q. Tran Dinh, and V. Cevher: Constrained convex minimization via model-based
excessive gap. Proceedings of the annual conference on Neural Information
Processing Systems Foundation (NIPS), Montreal, Canada, (2014).
[2]. Q. Tran Dinh, and V. Cevher. A Primal-Dual Algorithmic Framework for Constrained
Convex Minimization. LIONS Tech. Report EPFL-REPORT-199844, (2014).
INSTALLATION:
* Version: DECOPT now is the version 1.0 — DECOPT-v1.0.
* Download DECOPT-v1.0.zip at http://lions.epfl.ch/software/DECOPT-v1.0.
* Unzip the DECOPT-v1.0.zip file to create the DECOPT folder.
* Open MATLAB, browse to the DECOPT/ folder and run the decopt_setup.m file
to perform the basic installation steps.
* Now you are ready to use DECOPT.
EXAMPLES: The main file of DECOPT is: decoptSolver.m
Type: “help decoptSolver” for more information.
Here are few examples showing how to use DECOPT:
First we generate some synthetic data:
p = 1000; n = 350; k = 100;
indx = randperm(p,k);
x_org = zeros(p, 1);
x_org(indx) = randn(k, 1);
A = randn(n, p);
b = A*x_org + 1e-3*randn(n,1);
Then, we need some options for the algorithms:
param.MaxIters = 3000;
param.RelTolX = 1e-6;
param.Verbosity = 2;
We can also provide the initial point x0 for DECOPT.
For example, we can set: x0 = zeros(p, 1);
1. Solve the basis pursuit problem:
[xopt, output] = decoptSolver('BP', A, b, param, 'x0', x0);
2. If we want to solve the same problem, but using the linear operator, then:
Aopr = @(x)(A*x);
Aadj = @(x)(A’*x);
[xopt, output] = decoptSolver('BP', Aopr, b, param, 'x0', x0, ‘nx’, p, ’AT’, Aadj);
3. We can also define directly the proximal operators of f and g and call the solver:
proxOpers{1} = @(x, gamma, varargin)(proxL1norm(x, gamma));
proxOpers{2} = @(x, gamma, varargin)(projL2norm(x, 1e-12));
proxOpers{3} = @(x, varargin)(norm(x(:), 1));
proxOpers{4} = @(x, varargin)(0);
[xopt, output] = decoptSolver('UserDef', A, b, param, 'x0', x0, 'Prox', proxOpers);
Here, instead of putting A(x) = b, we slightly relax: |A(x) - b| <= 1e-12, which requires
the projection onto the l2-ball |r|_2 <= 1e-12.
CONTACT:
* This code is under development; any comments or bug reports are very welcome.
Contacts:
Quoc TRAN-DINH,
Laboratory for Information and Inference Systems (LIONS),
EPFL STI IEL, Ecole Polytechnique Federale de Lausanne (EPFL),
Station 11, CH1015-Lausanne, Switzerland.
Email: quoc.trandinh@epfl.ch
***