How to use ForBES

ForBES consist of the MATLAB routine forbes taking as input a problem description and (optionally) some options, and returning the results of the optimization process. We will now describe the structure of the problems that ForBES solves, and how to specify it to the forbes routine.

Examples can be found in the Examples section, or in the demos folder.

You can access the help file of the solver directly from MATLAB in any moment with:

help forbes

Problem structure

The generic formulation of the problems we consider is the following:

\[\begin{split}\mathrm{minimize}\ & f(Cx+d) + g(z)\\ \mathrm{subject\ to}\ & Ax + Bz = b\end{split}\]

Composite problems. Not all the terms need to be present in the above general structure above: if \(A, B, b\) in the constraint are omitted, then it is assumed to be \(x=z\) and the problem takes the composite form

\[\begin{split}\mathrm{minimize}\ & f(Cx+d) + g(x)\end{split}\]

Here \(f\) is assumed to be smooth (i.e. with Lipschitz continuous gradient) and twice continuously differentiable. Function \(g\) is any closed, proper function for which the proximal mapping

\[\begin{split}\mathrm{prox}_{\gamma g}(x)\ &= \mathrm{argmin}_z \left\{g(z) + \tfrac{1}{2\gamma}\|z-x\|^2\right\}\end{split}\]

is efficiently computable (e.g. it has a closed form, or can be computed numerically).

Separable problems. If \(A, B, b\) are specified, then \(C=I\) and \(d=0\), and the problem has the separable form

\[\begin{split}\mathrm{minimize}\ & f(x) + g(z)\\ \mathrm{subject\ to}\ & Ax + Bz = b\end{split}\]

Here \(f\) (if present) is strongly convex, while g is again proper, closed with easily computable proximal mapping. Linear operators \(A,B\) are of appropriate dimension along with vector \(b\) in the constraint.

Calling forbes

The most generic call to forbes is as follows:

out = forbes(f, g, init, aff, constr, opt);
  • f and g define the objective of the problem (see Functions on how to construct them).

  • init is the initial value of \(x\) if there are no equality constraints, or the initial dual variable associated with the constraint \(Ax+Bz=b\) otherwise.

  • aff is a cell array describing the affine terms composed with \(f\):

    aff = {C, d};
    

    If omitted or empty, that is aff = [] or aff = {}, then \(C=I\) and \(d=0\).

  • constr is a cell array describing the linear equality constraints:

    constr = {A, B, b};
    

    If omitted or empty, that is constr = [] or constr = {}, then \(A=I\), \(B=-I\) and \(b=0\).

  • opt is a structure containing options on the algorithm to use, termination criteria, the level of verbosity, and so on. More on this in the Options section below.

Output out will contain the results of the optimization process.

Functions

All the functions involved in the problem can be picked from a library of functions available in the library folder: this contains procedures returning commonly used functions, specified by a list of parameters if needed. The return object can directly be fed to forbes to describe the problem. For example:

f = logLoss(m); % f is the log-logistic function times a coefficient m
g = indPos(); % g is the indicator function of the nonnegative orthant
out = forbes(f, g);

Check out the Library of functions section for more information on the available functions and how to use them and the parameters they require, or the documentation of each of the functions in the library folder.

Options

The following table summarizes the main options of the solver. None of these needs to be specified, each one will be set to a default value if not provided.

Attribute Type Description
opt.tol real Tolerance for optimality
opt.maxit integer Maximum number of iterations
opt.solver string
  • 'minfbe': only handles cases where g is convex
  • 'zerofpr': can handle nonconvex g
opt.method string
  • 'bfgs': BFGS quasi-Newton method
  • 'lbfgs': Limited-memory BFGS
opt.linesearch string
  • 'backtracking': simple backtracking line-search
  • 'backtracking-nm': nonmonotone backtracking
  • 'backtracking-armijo': backtracking enforcing Armijo condition
  • 'lemarechal': line-search enforcing Wolfe conditions