# TOMLAB  
# REGISTER (TOMLAB)
# LOGIN  
# myTOMLAB
TOMLAB LOGO

« Previous « Start » Next »

11  TOMLAB Solver Reference

Detailed descriptions of the TOMLAB solvers, driver routines and some utilities are given in the following sections. Also see the M-file help for each solver. All solvers except for the TOMLAB  Base Module are described in separate manuals.

11.1  TOMLAB Base Module

For a description of solvers called using the MEX-file interface, see the M-file help, e.g. for the MINOS solver minosTL.m . For more details, see the User's Guide for the particular solver.

11.1.1  clsSolve

Purpose
Solves dense and sparse nonlinear least squares optimization problems with linear inequality and equality constraints and simple bounds on the variables.

clsSolve  solves problems of the form
 
min
x
f(x) =
1
2
r(x)Tr(x)
   
s/t xL ≤ x ≤ xU
  bL ≤ Ax ≤ bU
where x,xL,xU∈ R n, r(x)∈ R N, A∈ Rm1× n and bL,bU∈ R m1.
Calling Syntax
Result = clsSolve(Prob, varargin)
Result = tomRun('clsSolve', Prob);
Description of Inputs
Prob  Problem description structure. The following fields are used:
 
Prob  Problem description structure. The following fields are used:, continued
 
  Solver.Alg  Solver algorithm to be run:
    0: Gives default, the Fletcher - Xu hybrid method;
    1: Fletcher - Xu hybrid method; Gauss-Newton/BFGS.
    2: Al-Baali - Fletcher hybrid method; Gauss-Newton/BFGS.
    3: Huschens method. SIAM J. Optimization. Vol 4, No 1, pp 108-129 jan 1994.
    4: The Gauss-Newton method.
    5: Wang, Li, Qi Structured MBFGS method.
    6: Li-Fukushima MBFGS method.
    7: Broydens method.
 
    Recommendations: Alg=5 is theoretically best, and seems best in practice as well. Alg=1 and Alg=2 behave very similar, and are robust methods. Alg=4 may be good for ill-conditioned problems. Alg=3 and Alg=6 may sometimes fail. Alg=7 tries to minimize Jacobian evaluations, but might need more residual evaluations. Also fails more often that other algorithms. Suitable when analytic Jacobian is missing and evaluations of the Jacobian is costly. The problem should not be too ill-conditioned.
 
  Solver.Method  Method to solve linear system:
    0: QR with pivoting (both sparse and dense).
    1: SVD (dense).
    2: The inversion routine (inv) in Matlab  (Uses QR).
    3: Explicit computation of pseudoinverse, using pinv(Jk).
 
    Search method technique (if Prob.LargeScale = 1, then Method = 0 always): Prob.Solver.Method = 0 Sparse iterative QR using Tlsqr.
 
  LargeScale  If = 1, then sparse iterative QR using Tlsqr is used to find search directions
 
  x_0  Starting point.
  x_L  Lower bounds on the variables.
  x_U  Upper bounds on the variables.
 
  b_L  Lower bounds on the linear constraints.
  b_U  Upper bounds on the linear constraints.
  A  Constraint matrix for linear constraints.
 
  c_L  Lower bounds on the nonlinear constraints.
  c_U  Upper bounds on the nonlinear constraints.
 
  f_Low  A lower bound on the optimal function value, see LineParam.fLowBnd below.
 
  SolverQP  Name of the solver used for QP subproblems. If empty, the default solver is used. See GetSolver.m and tomSolve.m.
 
  PriLevOpt  Print Level.
  optParam  Structure with special fields for optimization parameters, see Table A. Fields used are: bTol , eps_absf , eps_g , eps_Rank , eps_x , IterPrint , MaxIter , PreSolve , size_f , size_x , xTol , wait , and QN_InitMatrix  (Initial Quasi-Newton matrix, if not empty, otherwise use identity matrix).
  LineParam  Structure with line search parameters. Special fields used:
  LineAlg  If Alg=7
    0 = Fletcher quadratic interpolation line search
    3 = Fletcher cubic interpolation line search
    otherwise Armijo-Goldstein line search (LineAlg == 2)
 
    If Alg!=7
    0 = Fletcher quadratic interpolation line search
    1 = Fletcher cubic interpolation line search
    2 = Armijo-Goldstein line search
    otherwise Fletcher quadratic interpolation line search (LineAlg == 0)
 
    If Fletcher, see help LineSearch for the LineParam parameters used. Most important is the accuracy in the line search: sigma - Line search accuracy tolerance, default 0.9.
 
  If LineAlg == 2, then the following parameters are used
  agFac  Armijo Goldsten reduction factor, default 0.1
  sigma  Line search accuracy tolerance, default 0.9
 
  fLowBnd  A lower bound on the global optimum of f(x). NLLS problems always have f(x) values >= 0 The user might also give lower bound estimate in Prob.f_Low clsSolve computes LineParam.fLowBnd as: LineParam.fLowBnd = max(0,Prob.f_Low,Prob.LineParam.fLowBnd) fLow = LineParam.fLowBnd is used in convergence tests.
 
varargin  Other parameters directly sent to low level routines.

Description of Outputs
Result  Structure with result from optimization. The following fields are changed:
 
Result  Structure with result from optimization. The following fields are changed:, continued
 
  x_k  Optimal point.
  v_k  Lagrange multipliers (not used).
  f_k  Function value at optimum.
  g_k  Gradient value at optimum.
 
  x_0  Starting point.
  f_0  Function value at start.
 
  r_k  Residual at optimum.
  J_k  Jacobian matrix at optimum.
 
  xState  State of each variable, described in Table 26.
  bState  State of each linear constraint, described in Table 27.
 
  Iter  Number of iterations.
  ExitFlag  Flag giving exit status. 0 if convergence, otherwise error. See Inform .
  Inform  Binary code telling type of convergence:
    1: Iteration points are close.
    2: Projected gradient small.
    3: Iteration points are close and projected gradient small.
    4: Function value close to 0.
    5: Iteration points are close and function value close to 0.
    6: Projected gradient small and function value close to 0.
    7: Iteration points are close, projected gradient small and function value close to 0.
    8: Relative function value reduction low for LowIts=10 iterations.
    11: Relative f(x) reduction low for LowIts iter. Close Iters.
    16: Small Relative f(x) reduction.
    17: Close iteration points, Small relative f(x) reduction.
    18: Small gradient, Small relative f(x) reduction.
    32: Local minimum with all variables on bounds.
    99: The residual is independent of x. The Jacobian is 0.
    101: Maximum number of iterations reached.
    102: Function value below given estimate.
    104: x_k  not feasible, constraint violated.
    105: The residual is empty, no NLLS problem.
  Solver  Solver used.
  SolverAlgorithm  Solver algorithm used.
  Prob  Problem structure used.
 

Description
The solver clsSolve  includes seven optimization methods for nonlinear least squares problems: the Gauss-Newton method, the Al-Baali-Fletcher [3] and the Fletcher-Xu [22] hybrid method, the Hushens TSSM method [53] and three more. If rank problem occur, the solver is using subspace minimization. The line search is performed using the routine LineSearch  which is a modified version of an algorithm by Fletcher [23]. Bound constraints are partly treated as described in Gill, Murray and Wright [31]. clsSolve  treats linear equality and inequality constraints using an active set strategy and a null space method.

M-files Used
ResultDef.m , preSolve.m , qpSolve.m , tomSolve.m , LineSearch.m , ProbCheck.m , secUpdat.m , iniSolve.m , endSolve.m 

See Also
conSolve , nlpSolve , sTrustr 

Limitations
When using the LargeScale  option, the number of residuals may not be less than 10 since the sqr2 algorithm may run into problems if used on problems that are not really large-scale.

Warnings
Since no second order derivative information is used, clsSolve  may not be able to determine the type of stationary point converged to.

11.1.2  conSolve

Purpose
Solve general constrained nonlinear optimization problems.

conSolve  solves problems of the form
 
min
x
f(x)        
s/t xL ≤ x ≤ xU
  bL ≤ Ax ≤ bU
  cL ≤ c(x) ≤ cU
where x,xL,xU∈ Rn, c(x),cL,cU∈ Rm1, A∈ Rm2× n and bL,bU∈ Rm2.
Calling Syntax
Result = conSolve(Prob, varargin)
Result = tomRun('conSolve', Prob);
Description of Inputs
Prob  Problem description structure. The following fields are used:
 
Prob  Problem description structure. The following fields are used:, continued
 
  Solver.Alg  Choice of algorithm. Also affects how derivatives are obtained.
    See following fields and table in § 11.1.2.
    0,1,2: Schittkowski SQP.
    3,4: Han-Powell SQP.
 
  x_0  Starting point.
  x_L  Lower bounds on the variables.
  x_U  Upper bounds on the variables.
 
  b_L  Lower bounds on the linear constraints.
  b_U  Upper bounds on the linear constraints.
  A  Constraint matrix for linear constraints.
 
  c_L  Lower bounds on the general constraints.
  c_U  Upper bounds on the general constraints.
 
  NumDiff  How to obtain derivatives (gradient, Hessian).
  ConsDiff  How to obtain the constraint derivative matrix.
 
  SolverQP  Name of the solver used for QP subproblems. If empty, the default solver is used. See GetSolver.m and tomSolve.m.
 
f_Low  A lower bound on the optimal function value, see LineParam.fLowBnd below. Used in convergence tests, f_k(x_k) <= f_Low. Only a feasible point x_k is accepted.
 
  FUNCS.f  Name of m-file computing the objective function f(x).
  FUNCS.g  Name of m-file computing the gradient vector g(x).
  FUNCS.H  Name of m-file computing the Hessian matrix H(x).
  FUNCS.c  Name of m-file computing the vector of constraint functions c(x).
  FUNCS.dc  Name of m-file computing the matrix of constraint normals ∂ c(x)/dx.
 
  PriLevOpt  Print level.
 
  optParam  Structure with optimization parameters, see Table A. Fields that are used: bTol , cTol , eps_absf , eps_g , eps_x , eps_Rank , IterPrint , MaxIter , QN_InitMatrix , size_f , size_x , xTol  and wait .
 
  LineParam  Structure with line search parameters. See Table 19.
 
  fLowBnd  A lower bound on the global optimum of f(x). The user might also give lower bound estimate in Prob.f_Low conSolve computes LineParam.fLowBnd as: LineParam.fLowBnd = max(Prob.f_Low,Prob.LineParam.fLowBnd).
 
varargin  Other parameters directly sent to low level routines.

Description of Outputs
Result  Structure with result from optimization. The following fields are changed:
 
Result  Structure with result from optimization. The following fields are changed:, continued
 
  x_k  Optimal point.
  v_k  Lagrange multipliers.
  f_k  Function value at optimum.
  g_k  Gradient value at optimum.
  H_k  Hessian value at optimum.
 
  x_0  Starting point.
  f_0  Function value at start.
 
  c_k  Value of constraints at optimum.
  cJac  Constraint Jacobian at optimum.
 
  xState  State of each variable, described in Table 26 .
  bState  State of each linear constraint, described in Table 27.
  cState  State of each nonlinear constraint.
 
  Iter  Number of iterations.
  ExitFlag  Flag giving exit status.
  ExitText  Text string giving ExitFlag  and Inform  information.
  Inform  Code telling type of convergence:
    1: Iteration points are close.
    2: Small search direction.
    3: Iteration points are close and Small search direction.
    4: Gradient of merit function small.
    5: Iteration points are close and gradient of merit function small.
    6: Small search direction and gradient of merit function small.
    7: Iteration points are close, small search direction and gradient of merit function small.
    8: Small search direction p and constraints satisfied.
    101: Maximum number of iterations reached.
    102: Function value below given estimate.
    103: Iteration points are close, but constraints not fulfilled. Too large penalty weights to be able to continue. Problem is maybe infeasible.
    104: Search direction is zero and infeasible constraints. The problem is very likely infeasible.
    105: Merit function is infinity.
    106: Penalty weights too high.
  Solver  Solver used.
  SolverAlgorithm  Solver algorithm used.
  Prob  Problem structure used.
 

Description
The routine conSolve  implements two SQP algorithms for general constrained minimization problems. One implementation, Solver.Alg=0,1,2, is based on the SQP algorithm by Schittkowski with Augmented Lagrangian merit function described in [72]. The other, Solver.Alg=3,4, is an implementation of the Han-Powell SQP method.

The Hessian in the QP subproblems are determined in one of several ways, dependent on the input parameters. The following table shows how the algorithm and Hessian method is selected.
Solver.Alg NumDiff AutoDiff isempty(FUNCS.H) Hessian computation Algorithm
0 0 0 0 Analytic Hessian Schittkowski SQP
0 any any any BFGS Schittkowski SQP
1 0 0 0 Analytic Hessian Schittkowski SQP
1 0 0 1 Numerical differences H Schittkowski SQP
1 >0 0 any Numerical differences g,H Schittkowski SQP
1 <0 0 any Numerical differences H Schittkowski SQP
1 any 1 any Automatic differentiation Schittkowski SQP
2 0 0 any BFGS Schittkowski SQP
2  =0 0 any BFGS, numerical gradient g Schittkowski SQP
2 any 1 any BFGS, automatic diff gradient Schittkowski SQP
3 0 0 0 Analytic Hessian Han-Powell SQP
3 0 0 1 Numerical differences H Han-Powell SQP
3 >0 0 any Numerical differences g,H Han-Powell SQP
3 <0 0 any Numerical differences H Han-Powell SQP
3 any 1 any Automatic differentiation Han-Powell SQP
4 0 0 any BFGS Han-Powell SQP
4  =0 0 any BFGS, numerical gradient g Han-Powell SQP
4 any 1 any BFGS, automatic diff gradient Han-Powell SQP

M-files Used
ResultDef.m , tomSolve.m , LineSearch.m , iniSolve.m , endSolve.m , ProbCheck.m .

See Also
nlpSolve , sTrustr 

11.1.3  cutPlane

Purpose
Solve mixed integer linear programming problems (MIP).

cutplane  solves problems of the form
 
min
x
f(x) = cTx    
subject to 0 ≤ x ≤ xU  
      Ax = b,  xj ∈ N  ∀ j ∈ I
where c, x, xU ∈ Rn, A∈ Rm× n and b ∈ Rm. The variables x ∈ I, the index subset of 1,...,n are restricted to be integers.
Calling Syntax
Result = cutplane(Prob); or
Result = tomRun('cutplane', Prob);
Description of Inputs
Prob  Problem description structure. The following fields are used:
 
Prob  Problem description structure. The following fields are used:, continued
 
 
  c  Constant vector.
 
  A  Constraint matrix for linear constraints.
  b_L  Lower bounds on the linear constraints.
  b_U  Upper bounds on the linear constraints.
  x_L  Lower bounds on the variables (assumed to be 0).
  x_U  Upper bounds on the variables.
 
  x_0  Starting point.
 
  QP.B  Active set B_0  at start:
    B(i)=1: Include variable x(i) in basic set.
    B(i)=0: Variable x(i) is set on it's lower bound.
    B(i)=−1: Variable x(i) is set on it's upper bound.
    B empty: lpSimplex  solves Phase I LP to find a feasible point.
 
  Solver.Method  Variable selection rule to be used:
    0: Minimum reduced cost. (default)
    1: Bland's anti-cycling rule.
    2: Minimum reduced cost, Dantzig's rule.
 
  MIP.IntVars  Which of the n variables are integers.
 
  SolverLP  Name of the solver used for initial LP subproblem.
 
  SolverDLP  Name of the solver used for dual LP subproblems.
 
  optParam  Structure with special fields for optimization parameters, see Table A.
    Fields used are: MaxIter , PriLev , wait , eps_f , eps_Rank , xTol  and bTol .

Description of Outputs
Result  Structure with result from optimization. The following fields are changed:
 
Result  Structure with result from optimization. The following fields are changed:, continued
 
  x_k  Optimal point.
  f_k  Function value at optimum.
  g_k  Gradient value at optimum, c.
  v_k  Lagrange multipliers.
  QP.B  Optimal active set. See input variable QP.B .
 
  xState  State of each variable, described in Table 26 .
 
  x_0  Starting point.
  f_0  Function value at start.
 
  Iter  Number of iterations.
  FuncEv  Number of function evaluations. Equal to Iter .
  ConstrEv  Number of constraint evaluations. Equal to Iter .
  ExitFlag  0: OK.
    1: Maximal number of iterations reached.
    4: No feasible point x_0  found.
  Inform  If ExitFlag > 0, Inform=ExitFlag.
  Solver  Solver used.
  SolverAlgorithm  Solver algorithm used.
  Prob  Problem structure used.
 

Description
The routine cutplane  is an implementation of a cutting plane algorithm with Gomorov cuts. cutplane  normally uses the linear programming routines lpSimplex  and DualSolve  to solve relaxed subproblems. By changing the setting of the structure fields Prob.Solver.SolverLP  and Prob.Solver.SolverDLP , different sub-solvers are possible to use.

cutplane  can interpret Prob.MIP.IntVars  in two different ways:
  • Vector of length less than dimension of problem: the elements designate indices of integer variables, e.g. IntVars = [1  3  5] restricts x1,x3 and x5 to take integer values only.
  • Vector of same length as c: non-zero values indicate integer variables, e.g. with five variables (x∈ R5), IntVars=[ 1  1  0  1  1 ] demands all but x3 to take integer values.
M-files Used
lpSimplex.m , DualSolve.m 

See Also
mipSolve , balas , lpsimp1 , lpsimp2 , lpdual , tomSolve .

11.1.4  DualSolve

Purpose
Solve linear programming problems when a dual feasible solution is available.

DualSolve  solves problems of the form
 
min
x
f(x) = cTx    
s/t xL ≤ x ≤ xU
      Ax = bU
where x,xL,xU∈ R n, c ∈ Rn, A∈ Rm× n and bU ∈ Rm.

Finite upper bounds on x are added as extra inequality constraints. Finite nonzero lower bounds on x are added as extra inequality constraints. Fixed variables are treated explicitly. Adding slack variables and making necessary sign changes gives the problem in the standard form

 
min
x
fP(x) = cTx  
s/t Ax = b  
  x ≥ 0
and the following dual problem is solved,
 
max
y
fD(y) = bTy
s/t ATy ≤ c
  y urs


with x,c ∈ Rn, A∈ Rm× n and b,y ∈ Rm.
Calling Syntax
= DualSolve(Prob)
Description of Inputs
Prob  Problem description structure. The following fields are used:
 
Prob  Problem description structure. The following fields are used:, continued
 
  QP.c  Constant vector.
 
  A  Constraint matrix for linear constraints.
  b_L  Lower bounds on the linear constraints.
  b_U  Upper bounds on the linear constraints.
 
  x_L  Lower bounds on the variables.
  x_U  Upper bounds on the variables.
  x_0  Starting point, must be dual feasible.
  y_0  Dual parameters (Lagrangian multipliers) at x_0.
 
  QP.B  Active set B_0  at start:
    B(i)=1: Include variable x(i) is in basic set.
    B(i)=0: Variable x(i) is set on its lower bound.
    B(i)=−1: Variable x(i) is set on its upper bound.
 
  Solver.Alg  Variable selection rule to be used:
    0: Minimum reduced cost (default).
    1: Bland's anti-cycling rule.
    2: Minimum reduced cost. Dantzig's rule.
 
  PriLevOpt  Print Level.
 
  optParam  Structure with special fields for optimization parameters, see Table A.
    Fields used are: MaxIter , wait , eps_f , eps_Rank  and xTol .

Description of Outputs
Result  Structure with result from optimization. The following fields are changed:
 
Result  Structure with result from optimization. The following fields are changed:, continued
 
  x_k  Optimal primal solution x .
  f_k  Function value at optimum.
  v_k  Optimal dual parameters. Lagrange multipliers for linear constraints.
 
  x_0  Starting point.
 
  Iter  Number of iterations.
  QP.B  Optimal active set.
  ExitFlag  Exit flag:
    0: Optimal solution found.
    1: Maximal number of iterations reached. No primal feasible solution found.
    2: Infeasible Dual problem.
    4: Illegal step length due to numerical difficulties. Should not occur.
    6: No dual feasible starting point found.
    7: Illegal step length due to numerical difficulties.
    8: Convergence because fk >= QP.DualLimit.
    9: xL(i) > xU(i) + xTol for some i. No solution exists.
Solver  Solver used.
SolverAlgorithm  Solver algorithm used.
 
  c  Constant vector in standard form formulation.
  A  Constraint matrix for linear constraints in standard form.
  b  Right hand side in standard form.
 

Description
When a dual feasible solution is available, the dual simplex method is possible to use. DualSolve  implements this method using the algorithm in [38, pages 105-106]. There are three rules available for variable selection. Bland's cycling prevention rule is the choice if fear of cycling exist. The other two are variants of minimum reduced cost variable selection, the original Dantzig's rule and one which sorts the variables in increasing order in each step (the default choice).

M-files Used
cpTransf.m 

See Also
lpSimplex 

11.1.5  expSolve

Purpose
Solve exponential fitting problems for given number of terms p.
Calling Syntax
Prob = expAssign( ... );
Result = expSolve(Prob, PriLev); or
Result = tomRun('expSolve', PriLev);
Description of Inputs
Prob  Problem created with expAssign.
PriLev  Print level in tomRun call.
 
Prob.SolverL2  Name of solver to use. If empty, TOMLAB selects dependent on license.

Description of Outputs
Result TOMLAB  Result structure as returned by solver selected by input argument Solver .
LS  Statistical information about the solution. See Table 29.

Global Parameters Used


Description
expSolve  solves a cls (constrained least squares) problem for exponential fitting formulates by expAssign. The problem is solved with a suitable or given cls solver.

The aim is to provide a quicker interface to exponential fitting, automating the process of setting up the problem structure and getting statistical data.

M-files Used
GetSolver , expInit , StatLS  and expAssign 

Examples
Assume that the Matlab vectors t , y  contain the following data:
ti 0 1.00 2.00 4.00 6.00 8.00 10.00 15.00 20.00
yi 905.10 620.36 270.17 154.68 106.74 80.92 69.98 62.50 56.29
To set up and solve the problem of fitting the data to a two-term exponential model
f(t) = α1 e−β1 t + α2 e−β2 t,
give the following commands: 
>> p      = 2;                         % Two terms
>> Name   = 'Simple two-term exp fit'; % Problem name, can be anything
>> wType  = 0;                         % No weighting
>> SepAlg = 0;                         % Separable problem
>> Prob = expAssign(p,Name,t,y,wType,[],SepAlg);

>> Result = tomRun('expSolve',Prob,1);
>> x = Result.x_k'

x =
          0.01          0.58         72.38        851.68
The x vector contains the parameters as x=[β1,β2,α1,α2] so the solution may be visualized with 
>> plot(t,y,'-*', t,x(3)*exp(-t*x(1)) + x(4)*exp(-t*x(2)) );


Figure 18: Results of fitting experimental data to two-term exponential model. Solid line: final model, dash-dot: data.


pngs/tomlab017.png

11.1.6  glbDirect

Purpose
Solve box-bounded global optimization problems.

glbDirect  solves problems of the form
 
min
x
f(x)        
s/t xL ≤ x ≤ xU
where f ∈ R and x,xL,xU∈ R n.

glbDirect  is a Fortran MEX implementation of glbSolve .

Calling Syntax
Result = glbDirectTL(Prob,varargin)
Result = tomRun('glbDirect', Prob);
Description of Inputs
Prob  Problem description structure. The following fields are used:
 
Prob  Problem description structure. The following fields are used:, continued
 
  x_L  Lower bounds for x, must be given to restrict the search space.
  x_U  Upper bounds for x, must be given to restrict the search space.
 
  Name  Name of the problem. Used for security if doing warm start.
  FUNCS.f  Name of m-file computing the objective function f(x).
 
  PriLevOpt  Print Level. 0 = Silent. 1 = Errors. 2 = Termination message and warm start info. 3 = Option summary.
 
  WarmStart  If true, >0, glbDirect  reads the output from the last run from Prob.glbDirect.WarmStartInto  if it exists. If it doesn't exist, glbDirect  attempts to open and read warm start data from mat-file glbDirectSave.mat. glbDirect  uses this warm start information to continue from the last run.
 
  optParam  Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used:
 
  IterPrint  Print iteration log every IterPrint iteration. Set to 0 for no iteration log. PriLev must be set to at least 1 to have iteration log to be printed.
  MaxIter  Maximal number of iterations, default 200.
  MaxFunc  Maximal number of function evaluations, default 10000 (roughly).
  EpsGlob  Global/local weight parameter, default 1E-4.
  fGoal  Goal for function value, if empty not used.
  eps_f  Relative accuracy for function value, fTol == epsf. Stop if abs(f−fGoal) <= abs(fGoal) * fTol , if fGoal  =0. Stop if abs(f−fGoal) <= fTol , if fGoal == 0.
  eps_x  Convergence tolerance in x. All possible rectangles are less than this tolerance (scaled to (0,1) ). See the output field maxTri.
 
  glbDirect  Structure in Prob, Prob.glbDirect. Solver specific.
  options  Structure with options. These options have precedence over all other options in the Prob struct. Available options are:
 
    PRILEV: Equivalent to Prob.PrilevOpt. Default: 0
    MAXFUNC: Eq. to Prob.optParam.MaxFunc. Default: 10000
    MAXITER: Eq. to Prob.optParam.MaxIter. Default: 200
    PARALLEL: Set to 1 in order to have glbDirect to call Prob.FUNCS.f with a matrix x of points to let the user function compute function values in parallel. Default: 0
    WARMSTART: Eq. to Prob.WarmStart. Default: 0
    ITERPRINT: Eq. to Prob.optParam.IterPrint. Default: 0
    FUNTOL: Eq. to Prob.optParam.eps_f. Default: 1e-2
    VARTOL: Eq. to Prob.optParam.eps_x. Default: 1e-13
    GLWEIGHT: Eq. to Prob.optParam.EpsGlob. Default: 1e-4
 
  WarmStartInfo  Structure with WarmStartInfo. Use WarmDefDIRECT.m to define it.
 

Description of Outputs
Result  Structure with result from optimization. The following fields are changed:
 
Result  Structure with result from optimization. The following fields are changed:, continued
 
  x_k  Matrix with optimal points as columns.
  f_k  Function value at optimum.
 
  Iter  Number of iterations.
  FuncEv  Number function evaluations.
  ExitText  Text string giving ExitFlag and Inform information.
  ExitFlag  Exit code.
    0 = Normal termination, max number of iterations /func.evals reached.
    1 = Some bound, lower or upper is missing.
    2 = Some bound is inf, must be finite.
    4 = Numerical trouble determining optimal rectangle, empty set and cannot continue.
  Inform  Inform code.
    1 = Function value f is less than fGoal.
    2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f−fGoal)/abs(fGoal) <= fTol.
    3 = Maximum number of iterations done.
    4 = Maximum number of function evaluations done.
    91= Numerical trouble, did not find element in list.
    92= Numerical trouble, No rectangle to work on.
    99= Other error, see ExitFlag.
 
  glbDirect  Substructure for glbDirect specific result data.
 
  nextIterFunc  If optimization algorithm was stopped because of maximum number of function evaluations reached, this is the number of function evaluations required to complete the next iteration.
  maxTri  Maximum size of any triangles.
  WarmStartInfo  Structure containing warm start data. Could be used to continue optimization where glbDirect stopped.
 
  To make a warm start possible, glbDirect saves the following information in
  the structure Result.glbDirect.WarmStartInfo and file
  glbDirectSave.mat (for internal solver use only):
 
  points  Matrix with all rectangle centerpoints, in [0,1]-space.
  dRect  Vector with distances from centerpoint to the vertices.
  fPoints  Vector with function values.
  nIter  Number of iterations.
  lRect  Matrix with all rectangle side lengths in each dimension.
  Name  Name of the problem. Used for security if doing warm start.
  dMin  Row vector of minimum function value for each distance.
  ds  Row vector of all different distances, sorted.
  glbfMin  Best function value found at a feasible point.
  iMin  The index in D which has lowest function value, i.e. the rectangle which minimizes (F − glbfMin + E)./D where E = max(EpsGlob*abs(glbfMin),1E−8).
  ign  Rectangles to be ignored in the rect. selection procedure.
 

Description
The global optimization routine glbDirect  is an implementation of the DIRECT algorithm presented in [16]. The algorithm in glbDirect  is a Fortran MEX implementation of the algorithm in glbSolve . DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore glbDirect  runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to restart glbDirect  with the final status of all parameters from the previous run, a so called warm start. Assume that a run has been made with glbDirect  on a certain problem for 50 iterations. Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of glbDirect  a flag Prob.WarmStart  should be set to one and WarmDefDIRECT  run. Then glbDirect  is using output previously obtained to make the restart. The m-file glbSolve  also includes the subfunction conhull  (in MEX) which is an implementation of the algorithm GRAHAMHULL in [68, page 108] with the modifications proposed on page 109. conhull  is used to identify all points lying on the convex hull defined by a set of points in the plane.

M-files Used
iniSolve.m , endSolve.m  glbSolve.m .

11.1.7  glbFast

Purpose
Solve box-bounded global optimization problems.

glbFast  solves problems of the form
 
min
x
f(x)        
s/t xL ≤ x ≤ xU
where f ∈ R and x,xL,xU∈ R n.

glbFast  is a Fortran MEX implementation of glbSolve .

Calling Syntax
Result = glbFast(Prob,varargin)
Result = tomRun('glbFast', Prob);
Description of Inputs
Prob  Problem description structure. The following fields are used:
 
Prob  Problem description structure. The following fields are used:, continued
 
  x_L  Lower bounds for x, must be given to restrict the search space.
  x_U  Upper bounds for x, must be given to restrict the search space.
 
  Name  Name of the problem. Used for security if doing warm start.
  FUNCS.f  Name of m-file computing the objective function f(x).
 
  PriLevOpt  Print Level. 0 = silent. 1 = Warm Start info 2 = A header printed.
 
  WarmStart  If true, >0, glbFast reads the output from the last run from the mat-file glbFastSave.mat, and continues from the last run..
 
  optParam  Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used:
 
  IterPrint  Print iteration #, # of evaluated points and best f(x) each iteration.
  MaxIter  Maximal number of iterations, default max(5000,n*1000).
  MaxFunc  Maximal number of function evaluations, default max(10000,n*2000).
  EpsGlob  Global/local weight parameter, default 1E-4.
  fGoal  Goal for function value, if empty not used.
  eps_f  Relative accuracy for function value, fTol == epsf. Stop if abs(f−fGoal) <= abs(fGoal) * fTol , if fGoal  =0. Stop if abs(f−fGoal) <= fTol , if fGoal == 0.
  eps_x  Convergence tolerance in x. All possible rectangles are less than this tolerance (scaled to (0,1) ). See the output field maxTri.
 
  If restart is chosen, the following fields in glbFastSave.mat  are also used
  and contains information from the previous run (for internal solver use only).
 
  C  Matrix with all rectangle centerpoints, in [0,1]-space.
  D  Vector with distances from centerpoint to the vertices.
  E  Computed tolerance in rectangle selection.
  F  Vector with function values.
  Iter  Number of iterations.
  L  Matrix with all rectangle side lengths in each dimension.
  Name  Name of the problem. Used for security if doing warm start.
  dMin  Row vector of minimum function value for each distance.
  ds  Row vector of all different distances, sorted.
  glbfMin  Best function value found at a feasible point.
  iMin  The index in D which has lowest function value, i.e. the rectangle which minimizes (F − glbfMin + E)./D where E = max(EpsGlob*abs(glbfMin),1E−8).
  ignoreIdx  Rectangles to be ignored in the rect. selection procedure.
 
varargin  Other parameters directly sent to low level routines.

Description of Outputs
Result  Structure with result from optimization. The following fields are changed:
 
Result  Structure with result from optimization. The following fields are changed:, continued
 
  x_k  Matrix with all points giving the function value f_k.
  f_k  Function value at optimum.
 
  Iter  Number of iterations.
  FuncEv  Number function evaluations.
  maxTri  Maximum size of any triangle.
  ExitText  Text string giving ExitFlag and Inform information.
  ExitFlag  Exit code.
    0 = Normal termination, max number of iterations /func.evals reached.
    1 = Some bound, lower or upper is missing.
    2 = Some bound is inf, must be finite.
    4 = Numerical trouble determining optimal rectangle, empty set and cannot continue.
  Inform  Inform code.
    1 = Function value f is less than fGoal.
    2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f−fGoal)/abs(fGoal) <= fTol.
    3 = Maximum number of iterations done.
    4 = Maximum number of function evaluations done.
    91= Numerical trouble, did not find element in list.
    92= Numerical trouble, No rectangle to work on.
    99= Other error, see ExitFlag.
  Solver  Solver used, 'glbFast'.
 

Description
The global optimization routine glbFast  is an implementation of the DIRECT algorithm presented in [16]. The algorithm in glbFast  is a Fortran MEX implementation of the algorithm in glbSolve . DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore glbFast  runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to restart glbFast  with the final status of all parameters from the previous run, a so called warm start. Assume that a run has been made with glbFast  on a certain problem for 50 iterations. Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of glbFast  a flag Prob.WarmStart  should be set to one. Then glbFast  is using output previously written to the file glbFastSave.mat  to make the restart. The m-file glbSolve  also includes the subfunction conhull  (in MEX) which is an implementation of the algorithm GRAHAMHULL in [68, page 108] with the modifications proposed on page 109. conhull  is used to identify all points lying on the convex hull defined by a set of points in the plane.

M-files Used
iniSolve.m , endSolve.m  glbSolve.m .

11.1.8  glbSolve

Purpose
Solve box-bounded global optimization problems.

glbSolve  solves problems of the form
 
min
x
f(x)        
s/t xL ≤ x ≤ xU
where f ∈ R and x,xL,xU∈ R n.
Calling Syntax
Result = glbSolve(Prob,varargin)
Result = tomRun('glbSolve', Prob);
Description of Inputs
Prob  Problem description structure. The following fields are used:
 
Prob  Problem description structure. The following fields are used:, continued
 
  x_L  Lower bounds for x, must be given to restrict the search space.
  x_U  Upper bounds for x, must be given to restrict the search space.
 
  Name  Name of the problem. Used for security if doing warm start.
  FUNCS.f  Name of m-file computing the objective function f(x).
 
  PriLevOpt  Print Level. 0 = silent. 1 = some printing. 2 = print each iteration.
 
  WarmStart  If true, >0, glbSolve reads the output from the last run from the mat-file glbSave.mat, and continues from the last run.
 
  MaxCPU  Maximal CPU Time (in seconds) to be used.
 
  optParam  Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used:
 
  IterPrint  Print iteration #, # of evaluated points and best f(x) each iteration.
  MaxIter  Maximal number of iterations, default max(5000,n*1000).
  MaxFunc  Maximal number of function evaluations, default max(10000,n*2000).
  EpsGlob  Global/local weight parameter, default 1E-4.
  fGoal  Goal for function value, if empty not used.
  eps_f  Relative accuracy for function value, fTol == epsf. Stop if abs(f−fGoal) <= abs(fGoal) * fTol , if fGoal  =0. Stop if abs(f−fGoal) <= fTol , if fGoal == 0.
 
  If warm start is chosen, the following fields saved to glbSave.mat  are also used
  and contains information from the previous run:
 
  C  Matrix with all rectangle centerpoints, in [0,1]-space.
  D  Vector with distances from centerpoint to the vertices.
  DMin  Row vector of minimum function value for each distance.
  DSort  Row vector of all different distances, sorted.
  E  Computed tolerance in rectangle selection.
  F  Vector with function values.
  L  Matrix with all rectangle side lengths in each dimension.
  Name  Name of the problem. Used for security if doing warm start.
  glbfMin  Best function value found at a feasible point.
  iMin  The index in D which has lowest function value, i.e. the rectangle which minimizes (F − glbfMin + E)./D where E = max(EpsGlob*abs(glbfMin),1E−8).
 
varargin  Other parameters directly sent to low level routines.

Description of Outputs
Result  Structure with result from optimization. The following fields are changed:
 
Result  Structure with result from optimization. The following fields are changed:, continued
 
  x_k  Matrix with all points giving the function value f_k.
  f_k  Function value at optimum.
 
  Iter  Number of iterations.
  FuncEv  Number function evaluations.
  maxTri  Maximum size of any triangle.
  ExitText  Text string giving ExitFlag and Inform information.
  ExitFlag  Exit code.
    0 = Normal termination, max number of iterations /func.evals reached.
    1 = Some bound, lower or upper is missing.
    2 = Some bound is inf, must be finite.
    4 = Numerical trouble determining optimal rectangle, empty set and cannot continue.
  Inform  Inform code.
    0 = Normal Exit.
    1 = Function value f is less than fGoal.
    2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f−fGoal)/abs(fGoal) <= fTol.
    9 = Max CPU Time reached.
  Solver  Solver used, 'glbSolve'.
 

Description
The global optimization routine glbSolve  is an implementation of the DIRECT algorithm presented in [16]. DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore glbSolve  runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to restart glbSolve  with the final status of all parameters from the previous run, a so called warm start Assume that a run has been made with glbSolve  on a certain problem for 50 iterations. Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of glbSolve  a flag Prob.WarmStart  should be set to one. Then glbSolve  is using output previously written to the file glbSave.mat  to make the restart. The m-file glbSolve  also includes the subfunction conhull  (in MEX) which is an implementation of the algorithm GRAHAMHULL in [68, page 108] with the modifications proposed on page 109. conhull  is used to identify all points lying on the convex hull defined by a set of points in the plane.

M-files Used
iniSolve.m , endSolve.m 

11.1.9  glcCluster

Purpose
Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.

glcCluster  solves problems of the form
 
min
x
f(x)        
s/t xL ≤ x ≤ xU
  bL ≤ Ax ≤ bU
  cL ≤ c(x) ≤ cU
      xi ∈ N   ∀ i ∈ I
where x,xL,xU∈ Rn, c(x),cL,cU∈ Rm1, A∈ Rm2× n and bL,bU∈ Rm2.

The variables x ∈ I, the index subset of 1,...,n are restricted to be integers.
Calling Syntax
Result = glcCluster(Prob, maxFunc1, maxFunc2, maxFunc3, ProbL)
Result = tomRun('glcCluster', Prob, PriLev) (driver call)
Description of Inputs
Prob  Problem description structure. The following fields are used:
 
Prob  Problem description structure. The following fields are used:, continued
 
  A  Constraint matrix for linear constraints.
  b_L  Lower bounds on the linear constraints.
  b_U  Upper bounds on the linear constraints.
 
  c_L  Lower bounds on the general constraints.
  c_U  Upper bounds on the general constraints.
 
  x_L  Lower bounds for x, must be given to restrict the search space.
  x_U  Upper bounds for x, must be given to restrict the search space.
 
  FUNCS.f  Name of m-file computing the objective function f(x).
  FUNCS.c  Name of m-file computing the vector of constraint functions c(x).
 
  PriLevOpt  Print level. 0=Silent. 1=Some output from each glcCluster phase. 2=More output from each phase. 3=Further minor output from each phase. 6=Use PrintResult( ,1) to print summary from each global and local run. 7 = Use PrintResult( ,2) to print summary from each global and local run. 8 = Use PrintResult( ,3) to print summary from each global and local run.
 
  WarmStart  If true, >0, glcCluster warm starts the DIRECT solver. The DIRECT solver will utilize all points sampled in last run, from one or two calls, dependent on the success in last run. Note: The DIRECT solver may not be changed if doing WarmStart mat-file glcFastSave.mat, and continues from the last run.
 
  Name  Name of the problem. glcCluster  uses the warmstart capability in glcFast  and needs the name for security reasons.
 
  GO  Structure in Prob , Prob.GO . Fields used:
  maxFunc1  Number of function evaluations in 1st call to glcFast. Should be odd number (automatically corrected). Default 100*dim(x) + 1.
  maxFunc2  Number of function evaluations in 2nd call to glcFast.
  maxFunc3  If glcFast is not feasible after maxFunc1 function evaluations, it will be repeatedly called (warm start) doing maxFunc1 function evaluations until maxFunc3 function evaluations reached.
  ProbL  Structure to be used in the local search. By default the same problem structure as in the global search is used, Prob (see below). Using a second structure is important if optimal continuous variables may take values on bounds. glcFast used for the global search only converges to the simple bounds in the limit, and therefore the simple bounds may be relaxed a bit in the global search. Also, if the global search has difficulty fulfilling equality constraints exactly, the lower and upper bounds may be slightly relaxed. But being exact in the local search. Note that the local search is using derivatives, and can utilize given analytic derivatives. Otherwise the local solver is using numerical derivatives or automatic differentiation. If routines to provide derivatives are given in ProbL, they are used. If only one structure Prob is given, glcCluster uses the derivative routines given in the this structure.
  localSolver  Optionally change local solver used ('snopt' or 'npsol' etc.).
 
  DIRECT  DIRECT subsolver, either glcSolve or glcFast (default).
 
  localTry  Maximal number of local searches from cluster points. If <= 0, glcCluster stops after clustering. Default 100.
 
  maxDistmin  The minimal number used for clustering, default 0.05.
 
  optParam  Structure with special fields for optimization parameters, see Table A.
    Fields used are: PriLev , cTol , IterPrint , MaxIter , MaxFunc ,
    EpsGlob , fGoal , eps_f , eps_x .
 
  MIP.IntVars  Structure in Prob, Prob.MIP. If empty, all variables are assumed non-integer (LP problem). If length(IntVars) >1 ==> length(IntVars) == length(c) should hold. Then IntVars(i) ==1 ==> x(i) integer. IntVars(i) ==0 ==> x(i) real. If length(IntVars) < n, IntVars is assumed to be a set of indices. It is advised to number the integer values as the first variables, before the continuous. The tree search will then be done more efficiently.
 
varargin  Other parameters directly sent to low level routines.

Description of Outputs
Result  Structure with result from optimization. The following fields are changed:
 
Result  Structure with result from optimization. The following fields are changed:, continued
 
  x_k  Matrix with all points giving the function value f_k.
  f_k  Function value at optimum.
  c_k  Nonlinear constraints values at x_k.
 
  Iter  Number of iterations.
  FuncEv  Number function evaluations.
  maxTri  Maximum size of any triangle.
  ExitText  Text string giving ExitFlag and Inform information.
 
  Cluster  Subfield with clustering information
  x_k  Matrix with best cluster points.
  f_k  Row vector with