YALL1-Group: A solver for group/joint sparse reconstruction
From Wikimization
(→Model) |
(→Model) |
||
Line 6: | Line 6: | ||
(1) Group-sparse basis pursuit model: | (1) Group-sparse basis pursuit model: | ||
- | + | Minimize <math>\|x\|_{w,2,1}:=\sum_{i=1}^s w_i\|x_{g_i}\|_2,</math> | |
- | + | ||
- | Minimize <math>\|x\|_{w,2,1}:=\sum_{i=1}^s w_i\|x_{g_i}\|_2,</math> | + | |
- | subject to <math>Ax=b,</math | + | subject to <math>Ax=b,</math> |
- | + | ||
where <math>A\in \mathbb{R}^{m\times n}\,(m<n)</math>, <math>b\in \mathbb{R}^m</math>, <math>g_i</math> is the index set of the <math>i</math>-th group, and <math>w_i\geq0</math> is the weight for the <math>i</math>-th group. | where <math>A\in \mathbb{R}^{m\times n}\,(m<n)</math>, <math>b\in \mathbb{R}^m</math>, <math>g_i</math> is the index set of the <math>i</math>-th group, and <math>w_i\geq0</math> is the weight for the <math>i</math>-th group. |
Revision as of 19:05, 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.
Contents |
Model
(1) Group-sparse basis pursuit model:
Minimize subject to
where , , is the index set of the -th group, and is the weight for the -th group.
(2) Jointly-sparse basis pursuit model:
Minimize subject to
where , is the -th row of matrix , and is the weight for the -th row.
Syntax
- x = gurobi_mex(c, objtype, A, b, contypes, lb, ub, vartypes);
- x = gurobi_mex(c, objtype, A, b, contypes, lb, ub, vartypes, opts);
- [x,val] = gurobi_mex(...);
- [x,val,flag] = gurobi_mex(...);
- [x,val,flag,output] = gurobi_mex(...);
- [x,val,flag,output,lambda] = gurobi_mex(...);
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.
Gurobi Parameters
- opts: optional structure that may have any number of following parameters.
- opts.[any Gurobi parameter]: See Gurobi Parameters for their allowed values.
- opts.QP: Quadratic objective terms. See here.
- opts.SOS: Special ordered set constraints. See here.
- opts.Start: MIP start vector, or Gurobi's attribute 'Start'. See 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 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 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 and . The third argument, qval, gives their coefficients. An example is given below.
SOS Constraints
SOS stands for 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 ith column of opts.SOS.weights specifies the weights (i.e., orders) of the variables in the ith 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 here in Gurobi's help. An example can be found 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
Example 6. Compressive sensing
See example m-file test_gurobi_mex_CS.m.
Feedback
Wotao Yin would be delighted to hear from you if you find Gurobi Mex useful, or if you have any suggestions, contributions, or bug reports.
How to cite
Wotao Yin. Gurobi Mex: A MATLAB interface for Gurobi, URL: http://convexoptimization.com/wikimization/index.php/gurobi_mex, 2009-2011.
Download, Installation, and Limitations
v1.50 (Gurobi 4) latest version C source code and MATLAB examples.
New features: quadratic programming with no linear constraints. Fixed bugs on handling SOS constraints on 64-bit systems.
History
v1.45 (Gurobi 4) New features: quadratic programming, MIP start vector. Fixed a bug on reporting unsupported options. Dattorro added support for all Gurobi options. Gurobi 4 changed parameter name "LPMethod" to "Method". v1.35 (Gurobi 2&3) New features: support of Special Ordered Sets (SOS) constraints of types 1 and 2; support all Gurobi parameters and a new option TrapCtrlC; detection of unrecognized options. Fixed minor display issues. Dattorro added support for all Gurobi options.
v1.30 Short release for SOS support.
v1.20 New features: Ctrl-C detection, Gurobi 3 support. Improved error and exception handling. Empty array [] is returned if an output argument is not available. Fixed the display interval option.
v1.10 New features: callback, runtime progress output, flexible log file, flexible input types, more options. Part of the code was contributed by Tomáš Strnad. Known bug: print an empty line even if options DisplayInterval and Display are both set to 0. Fix: remove Line 736 of gurobi_mex.c: mexPrintf("\n");
v1.05 Major bug fix: char array of constraint sense has been fixed
v1.04 support writing model to files in various formats such as MPS, REW, LP, ...
v1.03 support log file
v1.02 fixed a memory leak issue
v1.01 update: support output dual solution lambda; allow vartypes to be empty (for all continuous variables).
v1.00 initial version.
Future Release
Please send your suggested features to Wotao Yin.
Install Gurobi Mex in MATLAB
Step 1. Preparation
Refer to Gurobi's installation guide. Make sure that (i) proper environment variables are set, (ii) your copy of Gurobi has a license, and (iii) the license has been successfully validated.
Make sure that your MATLAB has been set up to use a supported external C compiler such as GCC and MS Visual C++. Run mex -setup if necessary. Do not use the built-in lcc, which cannot link with Gurobi's library.
If you use Gurobi 2, uncomment Line 20 of gurobi_mex.c regarding GRB_SUBOPTIMAL.
opts.Method in Gurobi 4 corresponds to parameter opts.LPMethod in Gurobi 2 and 3.
Step 2. Compiling Gurobi Mex
In MATLAB, go to the folder where gurobi_mex.c is saved and call mex as follows:
Step 2a. Windows
mex -O -I"<gurobi include path>" "<gurobi_mex.c>" "<gurobi C library file>" "<MATLAB libut.lib>"
For 64-bit MATLAB, add option "-largeArrayDims".
Example with Gurobi 4, MSVC2008, MATLAB 2009B, and 32-bit Windows
mex -O -I"C:\Gurobi400\win32\include" "C:\folder\gurobi_mex.c" "C:\Gurobi400\win32\lib\gurobi40.lib" "C:\Program Files\MATLAB\R2009b\extern\lib\win32\microsoft\libut.lib"
Missing libut.lib?
Ctrl-C detection requires libut.lib. If it is not found under your copy of MATLAB, you can download one for 32-bit Windows and 64-bit Windows (courtesy of Imre Polik).
Alternatively, libut.lib can be manually generated by creating a .def text file including the following five lines
LIBRARY libut.dll EXPORTS utIsInterruptPending utSetInterruptPending [empty line]
and then calling lib.exe (included in MSVC) like
"C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\lib" /def:libut.def /out:libut.lib /machine:x86
where /machine:x86 should be replaced by /machine:x64 for 64-bit Windows.
Step 2b. Linux/Unix
mex -O -I"<gurobi include path>" "<gurobi_mex.c>" -L"<gurobi lib path>" -l<gurobi C library file> -lut
For 64-bit MATLAB, add option "-largeArrayDims".
Example with Gurobi 3, GCC, MATLAB 2009B, and 64-bit Linux
mex -O -I"/opt/gurobi300/linux64/include" "/home/wotao/gurobi mex/gurobi_mex.c" -L"/opt/gurobi300/linux64/lib" -lgurobi30 -lut -largeArrayDims
Tested platforms
- 64-bit Ubuntu Linux 9.10, 64-bit MATLAB, and gcc.
- 32-bit Windows, 32-bit MATLAB, and gcc (part of free Mingw/GnuMex, alternatively TDM-GCC).
- 32-bit Windows, 32-bit MATLAB, and MSVC 2008 SP1 (the express Edition is free).
- 64-bit Windows, 64-bit MATLAB, and MSVC 2008 SP1 (the express Edition is free). Courtesy of Imre Polik.
For 64-bit MATLAB, Jon Dattorro suggests Microsoft Platform SDK and a bug fix for the linker.
FAQs
compiling is successful, but gurobi_mex cannot run
Solution: check and correct Gurobi license and environment variables
Step 1. Check and validate Gurobi license
Step 2. Check system environment variables for Gurobi
Step 3. Verify MATLAB knows the correct system environment variables by running
>> getenv('GUROBI_HOME') >> getenv('GRB_LICENSE_FILE') >> getenv('PATH') >> getenv('LD_LIBRARY_PATH') % on Unix/Linux/Mac
You may need to restart MATLAB from the terminal to get all environment variables loaded to MATLAB.
"int32" or "int64" errors
Solution: use int32 if sizeof(int) is 4 for your system; use int64 if sizeof(int) is 8. To determine sizeof(int), take the following steps
Step 1. create "check_sizeof_int.c" with the following lines
#include "mex.h" void mexFunction( int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[] ) { mexPrintf("Size of int is %d\n", sizeof(int)); return; }
Step 2. Launch Matlab, run mex check_sizeof_int.c, and then run check_sizeof_int
MATLAB reports "out of memory"
Solution: run clear mex after each call to gurobi_mex
Running out of memory is often the result of memory leaks. However, the interface has been checked numerous times for memory leaks. If there still appears to be a leak, we are not sure if it is with the interface, Gurobi, or MATLAB itself.
License
Creative Commons Attribution-Share Alike 3.0 United States License. Allow commercial use of this work. Permit others to copy, distribute, display, and perform the work, including for commercial purposes. Allow modification, as long as others share alike. Permit others to distribute derivative works only under the same license or one compatible with the one that governs the licensor's work.