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

« Previous « Start » Next »

4  TOMLAB /BARNLP Solver Reference

The BARNLP solvers are a set of Fortran solvers developed by Boeing Phantom Works. Table 2 lists the solvers included in TOMLAB /BARNLP. The solvers are called using a set of MEX-file interfaces developed as part of TOMLAB. All functionality of the BARNLP solvers are available and changeable in the TOMLAB framework in Matlab.

Detailed descriptions of the TOMLAB /BARNLP solvers are given in the following sections. Extensive TOMLAB m-file help is also available, for example help barnlpTL in Matlab will display the features of the BARNLP solver using the TOMLAB format.

There is also detailed instruction for using the solvers in Section 5.

The TOMLAB /BARNLP package solves nonlinear optimization problems (con) defined as
 
min
x
f(x)
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
cL ≤ c(x) ≤ cU
    (9)
where x, xL, xU ∈ Rn, f(x) ∈ R, A ∈ Rm1 × n, bL,bU ∈ Rm1 and cL,c(x),cU ∈ Rm2.

quadratic programming (qp) problems defined as
 
min
x
f(x) =
1
2
xT F x + cT x
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
    (10)
where c, x, xL, xU ∈ Rn, F ∈ Rn × n, A ∈ Rm1 × n, and bL,bU ∈ Rm1.

constrained nonlinear least squares (cls) problem is defined as
 
min
x
f(x) =
1
2
r(x)T r(x)
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
cL ≤ c(x) ≤ cU
    (11)
where x, xL, xU ∈ Rn, r(x) ∈ RM, A ∈ Rm1 × n, bL,bU ∈ Rm1 and cL,c(x),cU ∈ Rm2.

linear least squares (lls) problems defined as
 
min
x
f(x) =
1
2
|| C x − d ||
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
    (12)
where x, xL, xU ∈ Rn, d ∈ RM, C ∈ RM × n, A ∈ Rm1 × n, bL,bU ∈ Rm1.



4.1  BARNLP - Sparse Barrier Nonlinear Programming

Purpose
barnlpTL solves nonlinear optimization problems defined as

 
min
x
f(x)
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU,
cL ≤ c(x) ≤ cU
    (13)


where x, xL, xU ∈ Rn, f(x) ∈ R, A ∈ Rm1 × n, bL,bU ∈ Rm1 and cL,c(x),cU ∈ Rm2.
Equality constraints are imposed by setting for example cLi = cUi and variables can be fixed by setting xLi = xUi. BARNLP works under the assumption that the objective and constraint functions are twice continuously differentiable, and if this is not true algorithm performance is unpredictable. BARNLP uses a reverse communication format and upon request the user must supply the values of the functions, and their first and second derivatives. The matrix of first derivatives (the Jacobian) and the matrix of second derivatives (Hessian of the Lagrangian) are represented in a sparse format. If analytical information is not given, TOMLAB will estimate by using numerical or automatic differentiation.

METHOD

An interior point or barrier method is used to solve the nonlinear programming (NLP) problem. The barrier algorithm requires an estimate for the Hessian matrix HL. If the user cannot provide this information analytically, then sparse finite difference techniques should be utilized.
WARNING

The objective function and constraints supplied by the user are assumed to be continuous and have continuous first and second derivatives. Non-differentiable functions can cause unpredictable performance in the optimization algorithm. It should be emphasized that discontinuities in the Hessian matrices can significantly degrade the speed of convergence without producing any other obvious difficulties. The following common sources of error should be avoided when evaluating the objective and constraint functions:

(1) non-smooth interpolation of data;

(2) iterative procedures inside the function evaluation process, such as adaptive quadrature or root solving;

(3) discontinuous behavior caused by branching for IF tests;

(4) non-differentiable functions such as ABS, MAX, and MIN.

Calling Syntax
Using the driver routine tomRun:

Prob = ◇Assign( ... );
Result = tomRun('BARNLP', Prob ... );



Description of Inputs
Prob, The following fields are used:
 
x_L, x_U Bounds on variables.
 
A Linear constraint matrix, sparse (recommended) or dense .
b_L, b_U Bounds on linear constraints.
 
c_L, c_U Bounds on nonlinear constraints.
 
ConsPattern Sparsity pattern of the gradient of the nonlinear constraints. One row per constraint, one column per variable.
 
d2LPattern Sparsity pattern of the Hessian of the Lagrangian function. A sparse quadratic n*n matrix is expected.
 
PriLevOpt Print level.
 
BOS Structure with solver specific information. Fields used:
 
options Structure with options for the BARNLP solver. The user sets fields with names corresponding to the options he/she wishes to change. For example:
 
  Prob.BOS.options.CONTOL = 1E−7
  Prob.BOS.options.ALGOPT = 'FM'
 
  The following keywords are recognized:
 
  CONTOL, OBJTOL, PGDTOL, MAXNFE, NITMIN, IT1MAX, ALFLWR, ALFUPR, LYNPLT, LYNPNT, LYNVAR, NITMAX, IOFLAG, IOFLIN, IOFMFR, IOFPAT, MAXLYN, TOLFIL, TOLKTC, TOLPVT, ALGOPT, KTOPTN, IPOSTO, LYNFNC, SLPTOL, SFZTOL, IOFSHR, IOFSRC, JACPRM, QPOPTN
 
PrintFile Name of file to write general optimization output to. The amount of information to print is controlled by the following options: IOFLAG, IOFLIN, IOFSHR, IOFSRC, IOFMFR, IOFPAT. If no PrintFile is given, but any of the options mentioned above are nonzero, a default PrintFile 'bosout.txt' will be created.
 
OptionSummary Print summary of options to PrintFile, if a PrintFile is given. Different values of OptionSummary means different detail level of option summary:
 
  0 = No option summary
  1 = Prints a short description of important parameters and parameters that are not default values.
  2 = Prints a description of the parameters.
  3 = Prints a full description of the parameters.
 
statv Array of length n with variable status at initial point. This is computed automatically if empty or not present.
 
  0 = Variable strictly feasible.
  1 = Variable lower bound is active.
  2 = Variable upper bound is active.
  3 = Fixed variable.
 
statc Array of length n with constraint status at initial point. This is computed automatically if empty or not present. The value of 4 could be used to make the solver ignore a specific constraint.
 
  0 = Inactive constraint.
  1 = Constraint lower bound is active.
  2 = Constraint upper bound is active.
  3 = Equality.
  4 = Ignored constraint.
 
morereal Number of elements to add to the double 'hold' vector. The default size of 'hold' is 2,000,000 elements, which sometimes is not enough for large problems.
 
moreint Number of elements to add to the integer 'ihold' vector. The minimum size of 'ihold' is 2,000,000 elements, which sometimes is not enough for large problems.
 
  The solver can and does reallocate these vectors by itself, but if reallocation occurs frequently, it is better to give a suitable value here.
 

Description of Outputs
Result, The following fields are used:
 
Result The structure with results (see ResultDef.m).
x_k Optimal point, if one has been found.
f_k Objective function value at x_k.
 
x_0 Starting point.
f_0 Objective function value at x_0.
 
g_k Gradient of f(x) at final point x_k
H_k Hessian of f(x) at final point x_k.
 
Ax Value of linear constraints A*x at x_k.
c_k Value of nonlinear constraints c(x) at x_k.
cJac Gradient of nonlinear constraints.
 
v_k Lagrange multipliers for variables and constraints. Variables in the first n elements, followed by the constraints.
 
xState State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3;
bState State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
cState State of nonlinear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
 
ExitText Text string describing the result of the optimization.
ExitFlag Flag telling if convergence or failure.
Inform Solver information parameter.
 
FuncEv Number of objective function evaluations done.
GradEv Number of objective function gradient evaluations done.
HessEv Number of objective function Hessian evaluations done.
ConstrEv Number of constraint evaluations done.
ConJacEv Number of constraint gradient Jacobian evaluations done.
ConHessEv Number of constraint Hessian evaluations done.
 
Solver Name of the solver.
SolverAlgorithm Description of the solver.
 
BOS.statv Array of length n with variable status at optimal point:
 
  0 = Variable strictly feasible.
  1 = Variable lower bound is active.
  2 = Variable upper bound is active.
  3 = Fixed variable.
 
BOS.statc Array of length n with constraint status at optimal point:
 
  0 = Inactive constraint.
  1 = Constraint lower bound is active.
  2 = Constraint upper bound is active.
  3 = Equality.
  4 = Ignored constraint.
 
BOS.rcv Vector of length n with bound multipliers.
 
BOS.rcc Vector of length m with lagrange multipliers for the constraints.
 

4.2  BARLS - Sparse Barrier Constrained Nonlinear Least Squares

Purpose
barlsTL solves nonlinear optimization problems defined as

 
min
x
f(x) =
1
2
r(x)T r(x)
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU,
cL ≤ c(x) ≤ cU
    (14)
where x, xL, xU ∈ Rn, f(x) ∈ R, A ∈ Rm1 × n, bL,bU ∈ Rm1 and cL,c(x),cU ∈ Rm2.

linear least squares (lls) problems defined as
 
min
x
f(x) =
1
2
|| C x − d ||
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
    (15)
where x, xL, xU ∈ Rn, d ∈ RM, C ∈ RM × n, A ∈ Rm1 × n, bL,bU ∈ Rm1.

Equality constraints are imposed by setting for example cLi = cUi and variables can be fixed by setting xLi = xUi. BARLS works under the assumption that the residual and constraint functions are twice continuously differentiable, and if this is not true algorithm performance is unpredictable. BARLS uses a reverse communication format and upon request the user must supply the values of the functions, and their first and second derivatives. The matrix of first derivatives (the Jacobian) and the matrix of second derivatives (residual Hessian) are represented in a sparse format. TOMLAB estimates first and second order information when not given. An optional input to the software permits efficient solution of the problem when the residual and constraint functions are linear, i.e. the linear least squares problem. This is currently done automatically by TOMLAB.

METHOD

An interior point or barrier method is used to solve the nonlinear programming (NLP) problem. It is necessary to compute the residual Hessian matrix
V =
ℓ
Σ
i=1
ri∇2 ri −
m
Σ
i=1
λi∇2 ci.
If the user cannot provide this information analytically, the sparse finite difference techniques in TOMLAB will be utilized. Notice that the Hessian of the Lagrangian HL, which is required input for the sparse nonlinear program HDBNLP is related to the residual Hessian by
HL = V + RTR
where R is the ℓ × n residual Jacobian matrix. A sparse tableau form for the KKT linear system is utilized to avoid formation of the normal matrix RTR. This linear system is solved efficiently using the multifrontal method.
WARNING

The residual and constraint functions supplied by the user are assumed to be continuous and have continuous first and second derivatives. Nondifferentiable functions can cause unpredictable performance in the optimization algorithm. It should be emphasized that discontinuities in the Hessian matrices can significantly degrade the speed of convergence without producing any other obvious difficulties. The following common sources of error should be avoided when evaluating the residual and constraint functions:

(1) nonsmooth interpolation of data;

(2) iterative procedures inside the function evaluation process, such as adaptive quadrature or root solving;

(3) discontinuous behavior caused by branching for IF tests;

(4) nondifferentiable functions such as ABS, MAX, and MIN.

NOTES

A linear least squares problem is a special form of the general problem. In particular, it is necessary to compute the vector x = (x1,x2,…,xn) which minimizes the least squares objective function
f(x) =
1
2
(Rx − d)T (Rx − d) =
1
2
∥(Rx − d)∥2
where d is an ℓ-vector of data, subject to the m linear constraints
cL ≤ Gx ≤ cU
and the simple bounds
xL ≤ x ≤ xU.
The ℓ × n residual Jacobian matrix R and the m × n Jacobian matrix G are constant. The residual Hessian matrix V = 0 for this case. Efficient solution of a linear least squares problem should exploit the fact that;

(1) the Jacobian matrices R and G need only be computed once and,

(2) the residual Hessian matrix V does not need to be computed at all.

Calling Syntax
Using the driver routine tomRun:

Prob = ◇Assign( ... );
Result = tomRun('BARLS', Prob ... );



Description of Inputs
Prob, The following fields are used:
 
x_L, x_U Bounds on variables.
 
A Linear constraint matrix.
b_L, b_U Bounds on linear constraints.
 
c_L, c_U Bounds on nonlinear constraints.
 
JacPattern Sparsity pattern of the residual Jacobian. One row per residual, one column per variable.
 
ConsPattern Sparsity pattern of the gradient of the nonlinear constraints. One row per constraint, one column per variable.
 
d2LPattern Sparsity pattern of the Hessian of the Lagrangian function:
 
  d2L = r(x)' * d2r(x) + lam' * d2c(x)
  A sparse quadratic n*n matrix is expected. Note: The J' * J term is not included in the pattern!
 
PriLevOpt Print level in the solver.
 
BOS Structure with solver specific information. Fields used:
 
options Structure with options for the BARLS solver. The user sets fields with names corresponding to the options he/she wishes to change. For example:
 
  Prob.BOS.options.CONTOL = 1E−7
  Prob.BOS.options.ALGOPT = 'FM'
 
  The following keywords are recognized:
 
  CONTOL, OBJTOL, PGDTOL, MAXNFE, NITMIN, IT1MAX, ALFLWR, ALFUPR, LYNPLT, LYNPNT, LYNVAR, NITMAX, IOFLAG, IOFLIN, IOFMFR, IOFPAT, MAXLYN, TOLFIL, TOLKTC, TOLPVT, ALGOPT, KTOPTN, IPOSTO, LYNFNC, SLPTOL, SFZTOL, IOFSHR, IOFSRC, JACPRM, QPOPTN
 
PrintFile Name of file to write general optimization output to. The amount of information to print is controlled by the following options: IOFLAG, IOFLIN, IOFSHR, IOFSRC, IOFMFR, IOFPAT. If no PrintFile is given, but any of the options mentioned above are nonzero, a default PrintFile 'bosout.txt' will be created.
 
OptionSummary Print summary of options to PrintFile, if a PrintFile is given. Different values of OptionSummary means different detail level of option summary:
 
  0 = No option summary
  1 = Prints a short description of important parameters and parameters that are not default values.
  2 = Prints a description of the parameters.
  3 = Prints a full description of the parameters.
 
statv Array of length n with variable status at initial point. This is computed automatically if empty or not present.
 
  0 = Variable strictly feasible.
  1 = Variable lower bound is active.
  2 = Variable upper bound is active.
  3 = Fixed variable.
 
statc Array of length n with constraint status at initial point. This is computed automatically if empty or not present. The value of 4 could be used to make the solver ignore a specific constraint.
 
  0 = Inactive constraint.
  1 = Constraint lower bound is active.
  2 = Constraint upper bound is active.
  3 = Equality.
  4 = Ignored constraint.
 
morereal Number of elements to add to the double 'hold' vector. The default size of 'hold' is 2,000,000 elements, which sometimes is not enough for large problems.
 
moreint Number of elements to add to the integer 'ihold' vector. The minimum size of 'ihold' is 2,000,000 elements, which sometimes is not enough for large problems.
 
  The solver can and does reallocate these vectors by itself, but if reallocation occurs frequently, it is better to give a suitable value here.
 
The number of residuals has to be equal to the length of Prob.LS.y.

Description of Outputs
Result, The following fields are used:
 
Result The structure with results (see ResultDef.m).
x_0 Starting point.
x_k Optimal point, if one has been found.
f_k Objective function value at x_k.
r_k Residual values at x_k.
J_k Residual Jacobian matrix at x_k.
 
Ax Value of linear constraints A*x at x_k.
c_k Value of nonlinear constraints c(x) at x_k.
cJac Constraint Jacobian matrix at x_k.
 
xState State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3;
bState State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
cState State of nonlinear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
 
v_k Lagrange multipliers for variables and constraints. Variables in the first n elements, followed by the constraints.
 
ResEv Number of residual evaluations done.
JacEv Number of residual Jacobian evaluations done.
ConstrEv Number of constraint evaluations done.
ConJacEv Number of constraint gradient Jacobian evaluations done.
ConHessEv Number of constraint Hessian evaluations done.
 
ExitText Text string describing the result of the optimization.
ExitFlag Flag telling if convergence or failure.
Inform SPRLS exit status.
 
Solver Name of the solver.
SolverAlgorithm Description of the solver.
 
BOS.statv Array of length n with variable status at optimal point:
 
  0 = Variable strictly feasible.
  1 = Variable lower bound is active.
  2 = Variable upper bound is active.
  3 = Fixed variable.
 
BOS.statc Array of length n with constraint status at optimal point:
 
  0 = Inactive constraint.
  1 = Constraint lower bound is active.
  2 = Constraint upper bound is active.
  3 = Equality.
  4 = Ignored constraint.
 
BOS.rcv Vector of length n with bound multipliers.
 
BOS.rcc Vector of length m with lagrange multipliers for the constraints.
 

4.3  BARQP - Sparse Barrier Quadratic Programming

Purpose
barqpTL solves quadratic programming problems defined as

 
min
x
f(x) =
1
2
xT F x + cT x
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
    (16)
where c, x, xL, xU ∈ Rn, F ∈ Rn × n, A ∈ Rm1 × n, and bL,bU ∈ Rm1.
Equality constraints are imposed by setting bLi = bUi and variables can be fixed by setting xLi = xUi. A linear programming problem can be solved by setting H = 0. BARQP works under the assumption that the quadratic programming problem has a unique, finite solution. Thus, it is assumed that the projected Hessian matrix is positive definite at the solution. The matrix of first derivatives (the Jacobian) and the matrix of second derivatives (Hessian) are represented in a sparse format.

METHOD

An interior point or barrier method is used to solve the quadratic programming (QP) problem. The quadratic programming algorithm requires the Hessian matrix H and the Jacobian matrix A, both which must be specified in a sparse format. The barrier method is efficient because it avoids the computational complexity of active set methods when there are many inequality constraints, by using a log-barrier transformation. The large sparse KKT system is solved efficiently using the multifrontal algorithm. The algorithm incorporates a nonlinear filter for globalization.
WARNING

The projected Hessian matrix is assumed to be positive definite at the solution, i.e. with the correct active constraints. If this is not true, the software will detect an incorrect value for the matrix inertia and modify the Hessian matrix.

Calling Syntax
Using the driver routine tomRun:

Prob = ◇Assign( ... );
Result = tomRun('BARQP', Prob ... );



Description of Inputs
Prob, The following fields are used:
 
x_L, x_U Bounds on variables.
 
A Linear constraint matrix, sparse (recommended) or dense.
b_L, b_U Bounds on linear constraints.
 
QP.c Linear coefficients in objective function.
 
QP.F Quadratic matrix of size nxn.
 
PriLevOpt Print level in the solver.
 
BOS Structure with solver specific information. Fields used:
 
options Structure with options for the BARQP solver. The user sets fields with names corresponding to the options he/she wishes to change. For example:
 
  Prob.BOS.options.CONTOL = 1E−7
  Prob.BOS.options.ALGOPT = 'FM'
 
  The following keywords are recognized:
 
  CONTOL, OBJTOL, PGDTOL, MAXNFE, NITMIN, IT1MAX, ALFLWR, ALFUPR, LYNPLT, LYNPNT, LYNVAR, NITMAX, IOFLAG, IOFLIN, IOFMFR, IOFPAT, MAXLYN, TOLFIL, TOLKTC, TOLPVT, ALGOPT, KTOPTN, IPOSTO, LYNFNC, SLPTOL, SFZTOL, IOFSHR, IOFSRC, JACPRM, QPOPTN
 
PrintFile Name of file to write general optimization output to. The amount of information to print is controlled by the following options: IOFLAG, IOFLIN, IOFSHR, IOFSRC, IOFMFR, IOFPAT. If no PrintFile is given, but any of the options mentioned above are nonzero, a default PrintFile 'bosout.txt' will be created.
 
OptionSummary Print summary of options to PrintFile, if a PrintFile is given. Different values of OptionSummary means different detail level of option summary:
 
  0 = No option summary
  1 = Prints a short description of important parameters and parameters that are not default values.
  2 = Prints a description of the parameters.
  3 = Prints a full description of the parameters.
 
statv Array of length n with variable status at initial point. This is computed automatically if empty or not present.
 
  0 = Variable strictly feasible.
  1 = Variable lower bound is active.
  2 = Variable upper bound is active.
  3 = Fixed variable.
 
statc Array of length n with constraint status at initial point. This is computed automatically if empty or not present. The value of 4 could be used to make the solver ignore a specific constraint.
 
  0 = Inactive constraint.
  1 = Constraint lower bound is active.
  2 = Constraint upper bound is active.
  3 = Equality.
  4 = Ignored constraint.
 
morereal Number of elements to add to the double 'hold' vector. The default size of 'hold' is 2,000,000 elements, which sometimes is not enough for large problems.
 
moreint Number of elements to add to the integer 'ihold' vector. The minimum size of 'ihold' is 2,000,000 elements, which sometimes is not enough for large problems.
 
  The solver can and does reallocate these vectors by itself, but if reallocation occurs frequently, it is better to give a suitable value here.
 

Description of Outputs
Result, The following fields are used:
 
Result The structure with results (see ResultDef.m).
x_k Optimal point, if one has been found.
f_k Objective function value at x_k.
 
x_0 Starting point.
 
xState State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3;
bState State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
 
v_k Lagrange multipliers for variables and constraints. Variables in the first n elements, followed by the constraints.
 
Ax Value of linear constraints A*x at x_k.
 
ExitText Text string describing the result of the optimization.
ExitFlag Flag telling if convergence or failure.
Inform Solver information parameter.
 
Solver Name of the solver.
SolverAlgorithm Description of the solver.
 
BOS.statv Array of length n with variable status at optimal point:
 
  0 = Variable strictly feasible.
  1 = Variable lower bound is active.
  2 = Variable upper bound is active.
  3 = Fixed variable.
 
BOS.statc Array of length n with constraint status at optimal point:
 
  0 = Inactive constraint.
  1 = Constraint lower bound is active.
  2 = Constraint upper bound is active.
  3 = Equality.
  4 = Ignored constraint.
 
BOS.rcv Vector of length n with bound multipliers.
 
BOS.rcc Vector of length m with lagrange multipliers for the constraints.
 

« Previous « Start » Next »