Self-concordant optimization Files

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
***