# YALL1-Group: A solver for group/joint sparse reconstruction

(Difference between revisions)
 Revision as of 19:07, 9 June 2011 (edit) (→Syntax)← Previous diff Revision as of 19:47, 9 June 2011 (edit) (undo)Next diff → Line 24: Line 24: == Input Description == == Input Description == - * '''c''': objective coefficient vector, double type. - :[] (empty array) means uniformly 0 coefficients, and ''scalar'' means all coefficients equal to ''scalar''. - * '''objtype''': 1 (minimization) or -1 (maximization). - * '''A''': constraint coefficient matrix, double type, sparse. - * '''b''': constraint right-hand side vector, double type. - :Gurobi takes a dense vector for this input. If a ''sparse'' vector is specified, it will be converted to ''full'' by Gurobi Mex. - * '''contypes''': constraint types. Char array of '>', '<', '='. - :Warning: '>=' specifies two constraints, not one. - :Example: '>><=' specifies four constraints. The first two constraints have ''greater or equal to'' signs, the third has ''less than or equal to'' sign, and the last is an equality constraint. - :If a single character is specified, all constraints have the corresponding type uniformly. - * '''lb''': variable lower bound, double type, either scalar or vector. - :[] (empty array) means 0 lower bound. -inf means no lower bound. If a scalar is specified, it will be the uniform lower bound for all variables. - * '''ub''': variable upper bound, double type, either scalar or vector. - :[] (empty array) means no (or infinity) upper bound. If a scalar is specified, it will be the uniform upper bound for all variables. - * '''vartypes''': variable types, char array of 'C', 'B', 'I', 'S', 'N'. 'C' for continuous; 'B' for binary; 'I' for integer; 'S' for semi-continuous; 'N' for semi-integer. [] (empty array) means all variables are continuous. - :Example: 'CCCCC' specifies five continuous variables. - :Note that semi-continuous variables are variables that must take a value between their minimum and maximum or zero. - Semi-integer variables are similarly defined. - :If a single character is specified, all variables will be signed to the corresponding type uniformly. - === [http://www.gurobi.com/doc/40/refman/node572.html Gurobi Parameters] === - * '''opts''': optional structure that may have any number of following parameters. - ** '''opts.[any Gurobi parameter]''': See [http://www.gurobi.com/doc/40/refman/node572.html Gurobi Parameters] for their allowed values. - ** '''opts.QP''': Quadratic objective terms. See [http://www.convexoptimization.com/wikimization/index.php/Gurobi_Mex:_A_MATLAB_interface_for_Gurobi#Quadratic_Programming here]. - ** '''opts.SOS''': Special ordered set constraints. See [http://www.convexoptimization.com/wikimization/index.php/Gurobi_Mex:_A_MATLAB_interface_for_Gurobi#SOS_Constraints here]. - ** '''opts.Start''': MIP start vector, or Gurobi's attribute 'Start'. See [http://www.convexoptimization.com/wikimization/index.php/Gurobi_Mex:_A_MATLAB_interface_for_Gurobi#MIP_Start_Vector here]. - ** '''opts.TrapCtrlC''': true (to trap Ctrl-C) or false (not to trap Ctrl-C). - ** '''opts.Display''': screen output level. 0 (no output); 1 (error only); 2 (default output). For complete silence, set '''opts.DisplayInterval=0''' and '''opts.OutputFlag=0''' (to silence Gurobi) and '''opts.Display=0''' (to make Gurobi Mex silent). - ** '''opts.WriteToFile''': char array of the name of the file to which optimization data is written. See Gurobi C-Reference entry [http://www.gurobi.com/doc/40/refman/node39.html GRBwrite] for supported formats. This option helps one verify whether the model is correctly passed to Gurobi. - - == Output Description == - * '''x''': primal solution vector; empty if Gurobi encounters errors or stops early (in this case, check output flag). - * '''val''': optimal objective value; empty if Gurobi encounters errors or stops early. - * '''flag''': value meanings: - ** [ ] (empty 1x1 array) general failure - ** 1 for not started - ** 2 for optimal - ** 3 for infeasible - ** 4 for infeasible or unbounded - ** 5 for unbounded - ** 6 for objective worse than user-specified cutoff - ** 7 for reaching iteration limit - ** 8 for reaching node limit - ** 9 for reaching time limit - ** 10 for reaching solution limit - ** 11 for user interruption - ** 12 for numerical difficulties - ** 13 for suboptimal solution ('''Gurobi 3''' and later) - * '''output''': structure contains the following fields - ** '''output.IterCount''': number of Simplex iterations - ** '''output.Runtime''': running time in seconds - ** '''output.ErrorMsg''': contains Gurobi error message, if any - * '''lambda''': Lagrange multipliers. Because solving MIPs gives no such output, ''do not'' ask for this output for MIPs. - - == Notes == - === Quadratic Programming === - '''Gurobi 4''' and later solve quadratic programs. The quadratic terms in the objective function should be specified by '''opts.QP.qrow''', '''opts.QP.qcol''', and '''opts.QP.qval''', which correspond to the input arguments ''qrow'', ''qcol'', and ''qval'' of [http://gurobi.com/doc/40/refman/node11.html function GRBaddqpterms]. They are all 1D arrays. The first two arguments, ''qrow'' and ''qcol'', specify the row and column indices (starting from 0) of 2nd-order terms such as $x_1^2$ and $x_1 x_2\,$. The third argument, ''qval'', gives their coefficients. An example is given [http://www.convexoptimization.com/wikimization/index.php/Gurobi_Mex:_A_MATLAB_interface_for_Gurobi#Example_5._Quadratic_programming below]. - - ---- - - === SOS Constraints === - SOS stands for [http://www.google.com/search?q=special+ordered+set+SOS Special Ordered Sets]. This mex program uses opts.SOS.weights and opts.SOS.types to pass SOS constraints to Gurobi. '''opts.SOS.weights''' is a ''sparse'' matrix describing the weights of SOS variables, and '''opts.SOS.types''' a 1D array of type int32 or int64 (if sizeof(int) is 4 for your system, then you should use int32; if 8, use int64), which specifies the constraint types. Here is an example with 4 variables and 3 SOS constraints: - - SOS1: x1 = 0 or x2 = 0 - SOS1: x1 = 0 or x3 = 0 - SOS2: (x1, x3, x2, x4) - - The corresponding code for a 32-bit system is - opts.SOS.weights = sparse([ - 1 1 1; - 2 0 3; - 0 2 2; - 0 0 4]); - opts.SOS.types = int32([1 1 2]); - The ''i''th column of '''opts.SOS.weights''' specifies the weights (i.e., orders) of the variables in the ''i''th SOS constraint. - - ---- - - === MIP Start Vector === - To specify an MIP start vector (supported since v1.45), say x = [1 0 3 2], one can use one of the following two ways: - - opts.Start = [1 0 3 2]; - - or - - opts.Start.pos = int32([0 1 2 3]); % use int64 if sizeof(int) is 8 for your system - opts.Start.val = [1 0 3 2]; - - To specify start values for a subset of variables, for example to set x = [? ? -1 2], where ? means undefined, one can choose either one of the following two ways - - GRB_UNDEFINED = 1e101; - opts.Start = [GRB_UNDEFINED GRB_UNDEFINED -1 2]; - - or - - opts.Start.pos = int32([2 3]); % use int64 if sizeof(int) is 8 for your system - opts.Start.val = [-1 2]; - - ---- - - === How to pass a parameter from MATLAB to Gurobi? === - v1.35 and v1.45 support all parameters of '''Gurobi 3''' and '''4''', respectively. However, if you want to specify a new or undocumented Gurobi parameter of your interest, you can DIY very easily. Suppose that we want to set a double-type parameter called '''SecretPara''' in MATLAB and pass it through this mex interface to Gurobi. Because the parameter '''TimeLimit''' has the same (double) type and it is already supported by this mex program, we can copy the code for '''TimeLimit''', replace TimeLimit by SecretPara in the code, and paste it at Line 1250 of v1.35 (or Line 510 of v1.30), just before the mex program checks unrecognized input option fields. After compiling ''gurobi.c'', the modified mex will let you assign a double value to '''opts.SecretPara'''. We compare the code for '''TimeLimit''' and '''SecretPara''' below where the differences are italicized: - - /* Option ''TimeLimit'' */ - field_n = mxGetFieldNumber(IN_OPTS, "''TimeLimit''"); - if (field_n != -1) { - field = mxGetFieldByNumber(IN_OPTS,0,field_n); - bOpts[field_n] = true; - if (!mxIsDouble(field) || mxIsComplex(field) || mxIsEmpty(field)) { - mexPrintf("''Option TimeLimit must be real positive double (0 to inf).''"); - goto QUIT; - } - error = GRBsetdblparam(env, "''TimeLimit''", mxGetScalar(field)); - if (error) goto QUIT; - } - - /* Option ''SecretPara'' */ - field_n = mxGetFieldNumber(IN_OPTS, "''SecretPara''"); - if (field_n != -1) { - field = mxGetFieldByNumber(IN_OPTS,0,field_n); - bOpts[field_n] = true; - if (!mxIsDouble(field) || mxIsComplex(field) || mxIsEmpty(field)) { - mexPrintf("''Option SecretPara must real double (?? through ??).''"); - goto QUIT; - } - error = GRBsetdblparam(env, "''SecretPara''", mxGetScalar(field)); - if (error) goto QUIT; - } - - Note that you must start from a parameter of the ''same'' type (int, double, or string). In case memory allocation is needed, use ''mxCalloc'' and make sure that ''mxFree'' has been called whenever the mex program exits, normally or not. - - == Callbacks == - Callbacks are useful to obtain the progress of Gurobi (e.g., by calling GRBcbget) and to modify its behavior during runtime (e.g., by calling GRBcbcut and GRBcbsolution). - - Gurobi Mex implements a callback function ''mycallback'' to obtain Gurobi's progress messages and print them on the MATLAB screen. The print frequency is set in '''opts.DisplayInterval''' (in seconds). The same function is also used to detect user input Ctrl-C. - - Information for Gurobi callbacks can be found [http://www.gurobi.com/doc/40/refman/node84.html here] in Gurobi's help. An example can be found [http://www.gurobi.com/doc/40/examples/node8.html here]. - - == Examples == - - === Example 1. Linear programming === - This example is borrowed from MATLAB's linprog help. - - Problem: -
-                                                                  min –5 x1 – 4 x2 –6 x3,
-
-                                                                  subject to
-                                                                  x1 – x2 + x3 ≤ 20
-                                                                  3 x1 + 2 x2 + 4 x3 ≤ 42
-                                                                  3 x1 + 2 x2 ≤ 30
-                                                                  0 ≤ x1, 0 ≤ x2, 0 ≤ x3.
-
- MATLAB code: -
-                                                                  c = [-5; -4; -6];
-                                                                  objtype = 1;
-                                                                  A =  sparse([1 -1  1; 3  2  4; 3  2  0]);
-                                                                  b = [20; 42; 30];
-                                                                  lb = zeros(3,1);           % same as lb = [];
-                                                                  ub = [];
-                                                                  contypes = '<<<';
-                                                                  vtypes = [];               % same as vtypes = 'CCC'; [] means 'C...C'
-
-                                                                  clear opts
-                                                                  opts.IterationLimit = 20;
-                                                                  opts.FeasibilityTol = 1e-6;
-                                                                  opts.IntFeasTol = 1e-5;
-                                                                  opts.OptimalityTol = 1e-6;
-                                                                  opts.Method = 1;         % 0 - primal, 1 - dual
-                                                                  opts.Presolve = -1;        % -1 - auto, 0 - no, 1 - conserv, 2 - aggressive
-                                                                  opts.Display = 1;
-                                                                  opts.LogFile = 'test_gurobi_mex_LP.log';     % optional
-                                                                  opts.WriteToFile = 'test_gurobi_mex_LP.mps'; % optional; it can cause a long delay if problem is large
-
-                                                                  [x,val,exitflag,output,lambda] = gurobi_mex(c,objtype,A,b,contypes,lb,ub,vtypes,opts);
-
- Results: -
-                                                                  x' =
-                                                                  0 15 3
-
-                                                                  val =
-                                                                  -78
-
-                                                                  exitflag =
-                                                                  2
-
-                                                                  output =
-                                                                  IterCount: 2
-                                                                  Runtime: 0
-                                                                  ErrorMsg: []
-
-                                                                  lambda' =
-                                                                  0   -1.5000   -0.5000
-
- Log file: ''test_gurobi_mex_LP.log''. MPS file: ''test_gurobi_mex_LP.mps''. - - === Example 2. Integer programming === - This example is borrowed from ''mip1_c.c'' of '''Gurobi 2'''. - - Problem: -
-                                                                  max  x + y + 2z,
-
-                                                                  subject to
-                                                                  x + 2 y + 3 z <= 4
-                                                                  x +   y       >= 1
-                                                                  x, y, z binary.
-
- MATLAB code: -
-                                                                  c = [1; 1; 2];
-                                                                  objtype = -1;              % 1 for minimize, -1 for maximize
-                                                                  A =  sparse([1 2 3; 1 1 0]);
-                                                                  b = [4; 1];
-                                                                  lb = [];
-                                                                  ub = [];
-                                                                  contypes = '<>';
-                                                                  vtypes = 'BBB';
-
-                                                                  clear opts
-                                                                  opts.IterationLimit = 20;
-                                                                  opts.FeasibilityTol = 1e-6;
-                                                                  opts.IntFeasTol = 1e-5;
-                                                                  opts.OptimalityTol = 1e-6;
-                                                                  opts.Method = 1;         % 0 - primal, 1 - dual
-                                                                  opts.Presolve = -1;        % -1 - auto, 0 - no, 1 - conserv, 2 - aggressive
-                                                                  opts.Display = 1;
-                                                                  opts.LogFile = 'test_gurobi_mex_MIP.log';
-                                                                  opts.WriteToFile = 'test_gurobi_mex_MIP.mps';  % this option can cause a long delay if problem is large
-
-                                                                  [x,val,exitflag,output] = gurobi_mex(c,objtype,A,b,contypes,lb,ub,vtypes,opts);
-
- Gurobi does not give lambda (Pi, or Lagrange multipliers) for MIPs, unless model fix is called. - - Results: -
-                                                                  disp('Solution:');disp(x')
-                                                                  disp('Optimal obj value:');disp(val)
-                                                                  disp('Exit flag:');disp(exitflag)
-                                                                  disp('Optimization info:');disp(output)
-
-                                                                  Solution:
-                                                                  1     0     1
-
-                                                                  Optimal obj value:
-                                                                  3
-
-                                                                  Exit flag:
-                                                                  2
-
-                                                                  Optimization info:
-                                                                  IterCount: 0
-                                                                  Runtime: 0
-                                                                  ErrorMsg: []
-
- Log file: ''test_gurobi_mex_MIP.log''. MPS file: ''test_gurobi_mex_MIP.mps''. - - === Example 3. Feasibility test === - Problem: -
-                                                                  Find a solution or report infeasibility of
-
-                                                                  5 x1 + 4 x2        + 5 x4 >= -21
-                                                                  5 x1 + 3 x2 + 1 x3 + 4 x4  = -14
-                                                                  3 x1 + 5 x2 + 2 x3 - 5 x4  =  11
-                                                                  x1,x2,x3,x4 >= 0.
-
- MATLAB code: -
-                                                                  c = [];                    % use [] or 0 for null objective
-                                                                  objtype = -1;              % 1 for minimize, -1 for maximize
-                                                                  A =  sparse([5 4 0 5; 5 3 1 4; 3 5 2 -5]);
-                                                                  b = [-21; -14; 11];
-                                                                  lb = [];                   % stands for 0 lower bound uniformly
-                                                                  ub = [];                   % stands for inf upper bound uniformly
-                                                                  contypes = '>==';
-                                                                  vtypes = [];               % same as vtypes = 'CCCC'
-
-                                                                  clear opts
-                                                                  opts.FeasibilityTol = 1e-6;
-                                                                  opts.Presolve = -1;        % -1 - auto, 0 - no, 1 - conserv, 2 - aggressive
-                                                                  opts.Display = 1;
-                                                                  opts.LogFile = 'test_gurobi_mex_Feasibility.log';
-                                                                  opts.WriteToFile = 'test_gurobi_mex_Feasibility.mps';  % this option can cause a long delay if problem is large
-
-                                                                  [x,val,exitflag,output] = gurobi_mex(c,objtype,A,b,contypes,lb,ub,vtypes,opts);
-
- - Results: -
-                                                                  disp('Solution:');disp(x')
-                                                                  disp('Optimal obj value:');disp(val)
-                                                                  disp('Exit flag:');disp(exitflag)
-
-                                                                  Model is infeasible. No solution will be returned.
-
-                                                                  Solution:
-                                                                  Optimal obj value:
-                                                                  Exit flag:
-                                                                  3
-
- Log file: ''test_gurobi_mex_Feasibility.log''. MPS file: ''test_gurobi_mex_Feasibility.mps''. - - === Example 4. SOS constraint test === - Problem: -
-                                                                  min –3 x1 – 1 x2 – 1 x3,
-
-                                                                  subject to
-                                                                  x1 + x2 + x3 <= 2,
-                                                                  0 <= x1 <= 1, 0 <= x2 <= 1, 0 <= x3 <= 2,
-                                                                  SOS type 1: x1 = 0 or x2 = 0,
-                                                                  SOS type 1: x1 = 0 or x3 = 0.
-
- MATLAB code: -
-                                                                  c = [-3; -1; -1];
-                                                                  objtype = 1;
-                                                                  A =  sparse([1 1 1]);
-                                                                  b = 2;
-                                                                  lb = []; % means 0 lower bound
-                                                                  ub = [1 1 2];
-                                                                  contypes = '<';
-                                                                  vtypes = []; % same as vtypes = 'CCC'
-                                                                  sos.weights = sparse([1 1; 2 0; 0 2]);
-                                                                  sos.types = int32([1 1]);   % Both the SOS constraints are of type 1
-
-                                                                  clear opts
-                                                                  opts.FeasibilityTol = 1e-6;
-                                                                  opts.Presolve = -1;        % -1 - auto, 0 - no, 1 - conserv, 2 - aggressive
-                                                                  opts.Display = 1;
-                                                                  opts.LogFile = 'test_gurobi_mex_Feasibility.log';
-                                                                  opts.WriteToFile = 'test_gurobi_mex_Feasibility.mps';
-
-                                                                  [x,val,exitflag,output] = gurobi_mex(c,objtype,A,b,contypes,lb,ub,vtypes,opts);
-
- - Results: -
-                                                                  Optimal solution found (tolerance 1.00e-04)
-                                                                  Best objective -3.0000000000e+00, best bound -3.0000000000e+00, gap 0.0%
-
-                                                                  Solution:
-                                                                  1     0     0
-
- Log file: ''test_gurobi_mex_SOS.log''. MPS file: ''test_gurobi_mex_SOS.mps''. - - === Example 5. Quadratic programming === - This example appears in MATLAB Help entry for ''quadprog''. - - Problem: -
-                                                                  min 0.5 x0^2 - x0*x1 + x1^2 - 2*x0 - 6*x1,
-
-                                                                  subject to
-                                                                  x0 +  x1 <= 2,
-                                                                  -x0 + 2x1 <= 2,
-                                                                  2x0 +  x1 <= 3,
-                                                                  x0 >= 0, x1 >= 0.
-
- MATLAB code: -
-                                                                  clear opts
-
-                                                                  c = [-2 -6];    % objective linear term
-                                                                  objtype = 1;    % minimization
-                                                                  A =  sparse([1 1; -1 2; 2 1]); % constraint coefficients
-                                                                  b = [2; 2; 3];  % constraint right-hand side
-                                                                  lb = [];        % [] means 0 lower bound
-                                                                  ub = [];        % [] means inf upper bound
-                                                                  contypes = '<<<'; % three <= inequalities
-                                                                  vtypes = [];      % [] means all variables are continuous
-                                                                  opts.QP.qrow = int32([0 0 1]); % indices of x0, x0, x1 as in (0.5 x0^2 - x0*x1 + x1^2); use int64 if sizeof(int) is 8 for your system
-                                                                  opts.QP.qcol = int32([0 1 1]); % indices of x0, x1, x1 as in (0.5 x0^2 - x0*x1 + x1^2); use int64 if sizeof(int) is 8 for your system
-                                                                  opts.QP.qval = [0.5 -1 1];     % coefficients of (0.5 x0^2 - x0*x1 + x1^2)
-
-                                                                  opts.IterationLimit = 200;
-                                                                  opts.FeasibilityTol = 1e-6;
-                                                                  opts.IntFeasTol = 1e-5;
-                                                                  opts.OptimalityTol = 1e-6;
-
-                                                                  [x,val,exitflag,output,lambda] = gurobi_mex(c,objtype,A,b,contypes,lb,ub,vtypes,opts);
-
-                                                                  disp('Solution:');disp(x')
-                                                                  disp('Optimal obj value:');disp(val)
-                                                                  disp('Exit flag:');disp(exitflag)
-                                                                  disp('Optimization info:');disp(output)
-                                                                  disp('Lagrange multiplers:');disp(lambda')
-
- - Results: -
-                                                                  Solution:
-                                                                  0.6667    1.3333
-                                                                  Optimal obj value:
-                                                                  -8.2222
-                                                                  Exit flag:
-                                                                  2
-                                                                  Optimization info:
-                                                                  IterCount: 4
-                                                                  Runtime: 0.0630
-                                                                  ErrorMsg: []
-                                                                  Lagrange multiplers:
-                                                                  -3.1111   -0.4444         0
-

## Revision as of 19:47, 9 June 2011

YALL1-Group is a MATLAB software package for group/joint sparse reconstruction, written by Wei Deng, Wotao Yin and Yin Zhang at Rice University.

## Model

(1) Group-sparse basis pursuit model:

                  Minimize     $LaTeX: \|x\|_{w,2,1}:=\sum_{i=1}^s w_i\|x_{g_i}\|_2,$

subject to   $LaTeX: Ax=b,$


where $LaTeX: A\in \mathbb{R}^{m\times n}\,(m, $LaTeX: b\in \mathbb{R}^m$, $LaTeX: g_i$ is the index set of the $LaTeX: i$-th group, and $LaTeX: w_i\geq0$ is the weight for the $LaTeX: i$-th group.

(2) Jointly-sparse basis pursuit model:

                  Minimize     $LaTeX: \|X\|_{w,2,1}:=\sum_{i=1}^n w_i\|x^i\|_2,$
subject to   $LaTeX: AX=B,$


where $LaTeX: A\in \mathbb{R}^{m\times n}\,(m, $LaTeX: x^i$ is the $LaTeX: i$-th row of matrix $LaTeX: X$, and $LaTeX: w_i\geq0$ is the weight for the $LaTeX: i$-th row.

## Syntax

[x,Out] = YALL1_group(A,b,groups,varargin);