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

« Previous « Start » Next »

3  TOMLAB /SRPNLP Solver Reference

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

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

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

The TOMLAB /SPRNLP 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
    (1)
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
    (2)
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
    (3)
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
    (4)
where x, xL, xU ∈ Rn, d ∈ RM, C ∈ RM × n, A ∈ Rm1 × n, bL,bU ∈ Rm1.



3.1  SPRNLP - Sparse Nonlinear Programming

Purpose
sprnlpTL solves nonlinear optimization problems defined as

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


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. SPRNLP works under the assumption that the objective and constraint functions are twice continuously differentiable, and if this is not true algorithm performance is unpredictable. SPRNLP 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

A sequential quadratic programming (SQP) approach is used to solve the nonlinear programming (NLP) problem. The quadratic programming algorithm requires an estimate for the Hessian matrix HL. If the user cannot provide this information analytically, the sparse finite difference techniques in TOMLAB is used. For sparse applications the quadratic programming subproblem is efficiently solved using the sparse Schur-Complement Method. If problem sparsity is not exploited the QP subproblem can be solved efficiently using a dense null-space algorithm.
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('SPRNLP', 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 SPRNLP 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.
 

3.2  SPRLS - Sparse Constrained Nonlinear Least Squares

Purpose
sprlsTL solves constrained nonlinear least squares 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
    (6)
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
    (7)
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. SPRLS works under the assumption that the residual and constraint functions are twice continuously differentiable, and if this is not true algorithm performance is unpredictable. SPRLS 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 solver 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

A sequential quadratic programming (SQP) approach 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 SPRNLP is related to the residual Hessian by
HL = V + RTR
where R is the ℓ × n residual Jacobian matrix. A sparse tableau form for the quadratic programming subproblem is utilized to avoid formation of the normal matrix RTR. This QP subproblem is solved efficiently using the sparse Schur-Complement 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. For this application the user should set ALGOPT = `LLSQ'. Since the linear least squares problem can be solved with a single QP iteration;

(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('SPRLS', 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 SPRLS 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.
 

3.3  SPRQP - Sparse Quadratic Programming

Purpose
sprqpTL 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
    (8)
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. SPRQP 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

A sparse Schur-Complement 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 Schur-complement method is efficient because it is necessary to factor the large sparse symmetric indefinite KT matrix only once. Subsequent changes to the active set of constraints can be computed using a “solve” with the original large sparse system and a solve with the small dense Schur-complement. The multifrontal algorithm is used to factor and solve this large sparse linear system. The original Schur-complement algorithm proposed by Gill, Murray, Saunders, and Wright requires factorization of a linear system including active and inactive inequality constraints and can be exercised by setting the algorithm input KTOPTN to “large.” The default method (corresponding to KTOPTN “small”) factors a linear system which includes only the active constraints.
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. When this occurs the algorithm will terminate and no attempt is made to alter the problem definition. The solver will not solve indefinite quadratic programming problems.

Calling Syntax
Using the driver routine tomRun:

Prob = ◇Assign( ... );
Result = tomRun('SPRQP', 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 SPRQP 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.
 
BOS.cndnum Condition number of KKT system.
 

« Previous « Start » Next »