minConf

Mark Schmidt (2008)

minConf is a set of Matlab functions for optimization of differentiable real-valued multivariate functions subject to simple constraints on the parameters. On many problems, the functions included in minConf will be able to solve problems more efficiently than Matlab's fmincon function, while the functions in minConf can solve problems with a much larger number of variables, and they use line searches that are robust to several common function pathologies.

Methods

There are a variety of methods available. These are described below. In all cases, you need to provide a function handle funObj that computes the function value and gradient of the function to be minimized, an initial guess x, and a structure options containing any non-default options you want to use. Depending on the method used, you will also need to pass in some additional parameters that describe the constraints.

minConf_TMP(funObj,x,LB,UB,options): Previously minFuncBC in the minFunc package, this function implements a two-metric projection method for optimization with upper and/or lower bounds on the values of the variables:
```
min_x f(x), subject to LB <= x <= UB
```
The default options use a quasi-Newton strategy, where limited-memory BFGS updates are used in computing the step direction, and a backtracking line search is used to find a step satisfying an Armijo condition along the projection arc. You can change the number of L-BFGS corrections to store for the quasi-Newton update (options.corrections), and whether or not to use skipping or damping of the L-BFGS updates (options.damped). If funObj returns the Hessian of the objective function as its third output argument, you can use the Hessian explicitly if you set options.method to newton. To use this function, you need to specify the vectors LB and UB giving the lower/upper bounds on the variables. The elements of LB/UB can be set to -inf/inf if variables are unconstrained below/above.
Some examples of its usage can be found here.
minConf_SPG(funObj,x,funProj,options): This function implements a spectral projected gradient (SPG) method for optimizing over a (closed) convex set X:
```
min_x f(x), subject to x is in X
```
The default options use a Barzilai-Borwein scaling of the gradient, and use a non-monotone Armijo line search along the feasible direction to find the next iterate. The number of iterations to remember in the non-monotone line search can be changed (options.memory), as can the type of Barzilai-Borwein scaling (options.bbType), whether to backtrack along the projection arc (options.curvilinear), whether to compute an additional projection at each iteration to test optimality (options.testOpt), whether or not to use the Barzilai-Borwein scaling (options.useSpectral), and whether or not to project the initial parameters (options.feasibleInit). To use this function, you need to specify a function funProj that computes the projection onto the convex set:
```
funProj(x) = argmin_y ||x - y||_2, subject to y is in X
```
Included with minConf are some examples of projection functions: boundProject computes the projection when the convex set consists of simple bound constraints, projectSimplex computes the projection onto the probability simplex, and linearProject uses quadprog to project onto general linear constraints (LB <= x <= UB, Aeq*x=beq, and/or A*x + b >= 0).
minConf_PQN(funObj,x,funProj,options): This function implements a projected quasi-Newton method for minimizing over a (closed) convex set X:
```
min_x f(x), subject to x is in X
```
The default options use limited-memory BFGS quasi-Newton updates to form a quadratic approximation to the function, use minConf_SPG to minimize this quadratic approximation over the set, and use an Armijo backtracking line search along the feasible direction to find the next iterate. You can change the number of BFGS corrections to store (options.corrections), the number of iterations of SPG to run (options.SPGiters), the optimality tolerance for the SPG sub-routine (options.SPGoptTol), whether to initialize the SPG sub-routine with the Barzilai-Borwein step (options.bbInit), the maximum number of projections (options.maxProject), and whether or not to use quadratic interpolation to initialize the step length in the line search (options.adjustStep).
There is also a separate webpage dedicated to this method here, and some examples of its usage can be found here.

Options

All of the methods above allow the user to specify the values of the following options:

options.verbose: Specifies the level of verbosity of the program's output. The default value is 2, which outputs status information after each iteration. Setting it to 3 will output more information, 1 will only output the final status, and setting it to 0 will produce no output. Lower levels of verbosity will make the code run faster, but makes the progress of the methods less transparent.
options.numDiff: Specifies how the gradient vector is computed. The default value is 0, which means that funObj is expected to return the gradient vector as its second argument. Setting it to 1 will use finite differencing to approximate the gradient, and setting it to 2 will use complex differentials to compute the gradient.
options.optTol: Specifies the optimality tolerance threshold. If any measure of progress or optimality falls below this threshold, the algorithm terminates. The default is .000001.
options.maxIter: Specifies the maximum number of times that the function can be evaluated. The default is 500.
options.suffDec: Specifies the sufficient decrease parameter in the Armijo condition. This value must be in the range (0,1), and the default is .0001.
options.interp: Specifies whether (safeguarded) cubic polynomial interpolation will be used to set the step sizes in the line search. The default is 1, so cubic polynomial interpolation is used. Setting it to 0 will use step size halving in the line search.

Download

The complete set of .m files (and compiled .mex files for many operating systems) for the current version of minConf are available here.

Citations

If you use this software in a publication, please cite the work using one of the following:

M. Schmidt, E. van den Berg, M. Friedlander, K. Murphy. Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm. AISTATS, 2009.
M. Schmidt. minConf: projection methods for optimization with simple constraints in Matlab. http://www.cs.ubc.ca/~schmidtm/Software/minConf.html, 2008.

Example

The function example_minConf shows how to use the three different minConf functions to solve a non-negative least squares problem. Further examples of using minConf_TMP can be found here and of minConf_PQN can be found here (minConf_SPG could be used in place of minConf_PQN for all these examples).

Other issues

To apply the minConf functions to a function that takes more than one argument, you can use an anonymous function:

anonFunc = @(x)funObj(x,arg1,arg2);
minConf_TMP(anonFunc,x,LB,UB,options);

If the .zip file does not contain a .mex version of lbfgsC.mex*** for your operating system, you will need to run mexAll before using minConf_TMP or minConf_PQN (please e-mail me the compiled mex file so I can include in the .zip file).

To reference minConf in a publication, please include my name and a link to this website. You may also want to include the function used and the date, since I may update the software in the future.

Mark Schmidt > Software > minConf