The NLP Procedure

Computational Resources

Since nonlinear optimization is an iterative process that depends on many factors, it is difficult to estimate how much computer time is necessary to compute an optimal solution satisfying one of the termination criteria. The MAXTIME=, MAXITER=, and MAXFUNC= options can be used to restrict the amount of real time, the number of iterations, and the number of function calls in a single run of PROC NLP.

In each iteration  k, the NRRIDG and LEVMAR techniques use symmetric Householder transformations to decompose the  n x n Hessian (crossproduct Jacobian) matrix  g,

 g = v^t t v \: ,  v { orthogonal} ,     t { tridiagonal}
to compute the (Newton) search direction  s:
 s^{(k)} = - g^{(k-1)} g^{(k)} \: ,  k=1,2,3, ...
The QUADAS, TRUREG, NEWRAP, and HYQUAN techniques use the Cholesky decomposition to solve the same linear system while computing the search direction. The QUANEW, DBLDOG, CONGRA, and NMSIMP techniques do not need to invert or decompose a Hessian or crossproduct Jacobian matrix and thus require fewer computational resources then the first group of techniques.

The larger the problem, the more time is spent computing function values and derivatives. Therefore, many researchers compare optimization techniques by counting and comparing the respective numbers of function, gradient, and Hessian (crossproduct Jacobian) evaluations. You can save computer time and memory by specifying derivatives (using the GRADIENT, JACOBIAN, CRPJAC, or HESSIAN statement) since you will typically produce a more efficient representation than the internal derivative compiler.

Finite-difference approximations of the derivatives are expensive since they require additional function or gradient calls.

Many applications need considerably more time for computing second-order derivatives (Hessian matrix) than for first-order derivatives (gradient). In such cases, a (dual) quasi-Newton or conjugate gradient technique is recommended, which does not require second-order derivatives.

The following table shows for each optimization technique which derivatives are needed (FOD: first-order derivatives; SOD: second-order derivatives), what kinds of constraints are supported (BC: boundary constraints; LIC: linear constraints), and the minimal memory (number of double floating point numbers) required. For various reasons, there are additionally about  7n+m double floating point numbers needed.

Quadratic Programming FOD SOD BC LIC Memory
LICOMP--xx 18n + 3nn
QUADAS--xx 1n + 2nn/2
General OptimizationFODSODBCLICMemory
TRUREGxxxx 4n + 2nn/2
NEWRAPxxxx 2n + 2nn/2
NRRIDGxxxx 6n + nn/2
QUANEWx-xx 1n + nn/2
DBLDOGx-xx 7n + nn/2
CONGRAx-xx 3n
NMSIMP--xx 4n + nn
Least-SquaresFODSODBCLICMemory
LEVMARx-xx 6n + nn/2
HYQUANx-xx 2n + nn/2 + 3m


Notes:

The total amount of memory needed to run an optimization technique consists of the technique-specific memory listed in the preceding table, plus additional blocks of memory as shown in the following table.

  double int long 8byte
Basic Requirement 7n+m n 3n n+m
DATA= data set v-- v
JACOBIAN statement m(n+2)---
CRPJAC statement nn/2---
HESSIAN statement nn/2---
COV= option (2*)nn/2 + n---
Scaling vector n---
BOUNDS statement 2n n--
Bounds in INEST= 2n---
LINCON and TRUREG c(n+1)+nn+ nn/2+4n 3c--
LINCON and other c(n+1)+nn+2nn/2+4n 3c--

Notes:

Previous Page | Next Page | Top of Page