Nonlinear Optimization Examples |
Termination Criteria
The input argument tc specifies a vector
of bounds corresponding to a set of termination
criteria that are tested in each iteration.
If you do not specify an IML module with the "ptit" argument,
these bounds determine when the optimization process stops.
If you specify the "ptit" argument,
the "tc" argument is ignored.
The module specified by the "ptit"
argument replaces the subroutine that is used
by default to test the termination criteria.
The module is called in each iteration with the current location,
, and the value, , of the objective function at .
The module must give a return code, , that decides whether
the optimization process is to be continued or terminated.
As long as the module returns ,
the optimization process continues.
When the module returns ,
the optimization process stops.
If you use the tc vector, the optimization techniques
stop the iteration process when at least one of the
corresponding set of termination criteria are satisfied.
Table 11.3 and Table 11.4 indicate the criterion
associated with each element of the tc vector.
There is a default for each criterion, and if you
specify a missing value for the corresponding element
of the tc vector, the default value is used.
You can avoid termination with respect to the
ABSFTOL, ABSGTOL, ABSXTOL, FTOL, FTOL2, GTOL, GTOL2,
and XTOL criteria by specifying a value of zero for
the corresponding element of the tc vector.
Table 11.3: Termination Criteria for the NLPNMS Subroutine
Index
|
Description
|
1 | maximum number of iterations (MAXIT) |
2 | maximum number of function calls (MAXFU) |
3 | absolute function criterion (ABSTOL) |
4 | relative function criterion (FTOL) |
5 | relative function criterion (FTOL2) |
6 | absolute function criterion (ABSFTOL) |
7 | FSIZE value used in FTOL criterion |
8 | relative parameter criterion (XTOL) |
9 | absolute parameter criterion (ABSXTOL) |
9 | size of final trust-region radius
(COBYLA algorithm) |
10 | XSIZE value used in XTOL criterion |
Table 11.4: Termination Criteria for Other Subroutines
Index
|
Description
|
1 | maximum number of iterations (MAXIT) |
2 | maximum number of function calls (MAXFU) |
3 | absolute function criterion (ABSTOL) |
4 | relative gradient criterion (GTOL) |
5 | relative gradient criterion (GTOL2) |
6 | absolute gradient criterion (ABSGTOL) |
7 | relative function criterion (FTOL) |
8 | predicted function reduction criterion (FTOL2) |
9 | absolute function criterion (ABSFTOL) |
10 | FSIZE value used in GTOL and FTOL criterion |
11 | relative parameter criterion (XTOL) |
12 | absolute parameter criterion (ABSXTOL) |
13 | XSIZE value used in XTOL criterion |
Criteria Used by All Techniques
The following list indicates the termination criteria
that are used with all the optimization techniques:
- tc[1]
specifies the maximum number of iterations
in the optimization process (MAXIT).
The default values are
NLPNMS: | | MAXIT=1000 |
NLPCG: | | MAXIT=400 |
Others: | | MAXIT=200 |
tc[2]
specifies the maximum number of function
calls in the optimization process (MAXFU).
The default values are
NLPNMS: | | MAXFU=3000 |
NLPCG: | | MAXFU=1000 |
Others: | | MAXFU=500 |
tc[3]
specifies the absolute function
convergence criterion (ABSTOL).
For minimization, termination requires ABSTOL, while for maximization, termination
requires ABSTOL.
The default values are the negative and positive
square roots of the largest double precision value,
for minimization and maximization, respectively.
These criteria are useful when you want to divide a time-consuming
optimization problem into a series of smaller problems.
Termination Criteria for NLPNMS
Since the Nelder-Mead simplex algorithm does not use
derivatives, no termination criteria are available that
are based on the gradient of the objective function.
When the NLPNMS subroutine implements Powell's COBYLA
algorithm, it uses only one criterion other than
the three used by all the optimization techniques.
The COBYLA algorithm is a trust-region method that sequentially
reduces the radius, , of a spheric trust region from
the start radius, , which is controlled with the
par[2] argument, to the final radius, ,
which is controlled with the tc[9] argument.
The default value for tc[9] is 1E-4.
Convergence to small values of can
take many calls of the function and constraint
modules and might result in numerical problems.
In addition to the criteria used by all techniques, the original
Nelder-Mead simplex algorithm uses several other termination
criteria, which are described in the following list:
- tc[4]
specifies the relative function convergence criterion (FTOL).
Termination requires a small relative difference
between the function values of the vertices in the
simplex with the largest and smallest function values.
where FSIZE is defined by tc[7].
The default value is tc, where FDIGITS
is controlled by the par[8] argument.
The par[8] argument has a default
value of , where
is the machine precision.
Hence, the default value for FTOL is .
tc[5]
specifies another relative function
convergence criterion (FTOL2).
Termination requires a small standard deviation
of the function values of the simplex
vertices .
where .
If there are active boundary constraints at
, the mean and standard deviation are
computed only for the unconstrained vertices.
The default is tc1E-6.
tc[6]
specifies the absolute function
convergence criterion (ABSFTOL).
Termination requires a small absolute difference
between the function values of the vertices in the
simplex with the largest and smallest function values.
The default is tc.
tc[7]
specifies the FSIZE value used in
the FTOL termination criterion.
The default is tc.
tc[8]
specifies the relative parameter
convergence criterion (XTOL).
Termination requires a small relative
parameter difference between the vertices
with the largest and smallest function values.
The default is tc1E-8.
tc[9]
specifies the absolute parameter
convergence criterion (ABSXTOL).
Termination requires either a small length,
, of the vertices of a restart
simplex or a small simplex size, .
where is defined as the L1 distance of the
simplex vertex with the smallest function value, ,
to the other simplex points, .
The default is tc1E-8.
tc[10]
specifies the XSIZE value used
in the XTOL termination criterion.
The default is tc.
Termination Criteria for Unconstrained and Linearly
Constrained Techniques
- tc[4]
specifies the relative gradient convergence criterion (GTOL).
For all techniques except the NLPCG subroutine,
termination requires that the normalized
predicted function reduction is small.
where FSIZE is defined by tc[10].
For the NLPCG technique (where a reliable
Hessian estimate is not available),
is used.
The default is tc1E-8.
tc[5]
specifies another relative gradient
convergence criterion (GTOL2).
This criterion is used only by the NLPLM subroutine.
The default is tc[5]=0.
tc[6]
specifies the absolute gradient
convergence criterion (ABSGTOL).
Termination requires that the maximum
absolute gradient element be small.
The default is tc1E-5.
tc[7]
specifies the relative function convergence criterion (FTOL).
Termination requires a small relative change of
the function value in consecutive iterations.
where is defined by tc[10].
The default is tc, where FDIGITS
is controlled by the par[8] argument.
The par[8] argument has a default
value of , where
is the machine precision.
Hence, the default for FTOL is .
tc[8]
specifies another function convergence criterion (FTOL2).
For least squares problems, termination requires a
small predicted reduction of the objective function,
.
The predicted reduction is computed by approximating
the objective function by the first two terms of
the Taylor series and substituting the Newton step,
, as follows:
The FTOL2 criterion is the unscaled
version of the GTOL criterion.
The default is tc[8]=0.
tc[9]
specifies the absolute function
convergence criterion (ABSFTOL).
Termination requires a small change of the
function value in consecutive iterations.
The default is tc[9]=0.
tc[10]
specifies the FSIZE value used in the
GTOL and FTOL termination criteria.
The default is tc[10]=0.
tc[11]
specifies the relative parameter
convergence criterion (XTOL).
Termination requires a small relative
parameter change in consecutive iterations.
The default is tc[11]=0.
tc[12]
specifies the absolute parameter
convergence criterion (ABSXTOL).
Termination requires a small Euclidean distance
between parameter vectors in consecutive iterations.
The default is tc[12]=0.
tc[13]
specifies the XSIZE value used in
the XTOL termination criterion.
The default is tc[13]=0.
Termination Criteria for Nonlinearly Constrained Techniques
The only algorithm available for nonlinearly constrained
optimization other than the NLPNMS subroutine is the NLPQN
subroutine, when you specify the "nlc" module argument.
This method, unlike the other optimization methods,
does not monotonically reduce the value of the
objective function or some kind of merit function
that combines objective and constraint functions.
Instead, the algorithm uses the watchdog technique
with backtracking of Chamberlain et al. (1982).
Therefore, no termination criteria are implemented that are
based on the values or in consecutive iterations.
In addition to the criteria used by all optimization
techniques, there are three other termination criteria
available; these are based on the Lagrange function
and its gradient
where
denotes the total number of constraints,
is the gradient of the objective function,
and
is the vector of Lagrange multipliers.
The Kuhn-Tucker conditions require that the
gradient of the Lagrange function is zero at
the optimal point
, as follows:
- tc[4]
specifies the GTOL criterion, which requires that the
normalized predicted function reduction be small.
where FSIZE is defined by the tc[10] argument.
The default is tc1E-8.
tc[6]
specifies the ABSGTOL criterion, which
requires that the maximum absolute gradient
element of the Lagrange function be small.
The default is tc1E-5.
tc[8]
specifies the FTOL2 criterion, which requires
that the predicted function reduction be small.
The default is tc1E-6.
This is the criterion used by the programs
VMCWD and VF02AD of Powell (1982b).