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, x, and the value, f, of the objective function at x. The module must give a return code, rc, that decides whether the optimization process is to be continued or terminated. As long as the module returns rc = 0, the optimization process continues. When the module returns rc \neq 0, 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
1maximum number of iterations (MAXIT)
2maximum number of function calls (MAXFU)
3absolute function criterion (ABSTOL)
4relative function criterion (FTOL)
5relative function criterion (FTOL2)
6absolute function criterion (ABSFTOL)
7FSIZE value used in FTOL criterion
8relative parameter criterion (XTOL)
9absolute parameter criterion (ABSXTOL)
9size of final trust-region radius \rho (COBYLA algorithm)
10XSIZE value used in XTOL criterion



Table 11.4: Termination Criteria for Other Subroutines
Index Description
1maximum number of iterations (MAXIT)
2maximum number of function calls (MAXFU)
3absolute function criterion (ABSTOL)
4relative gradient criterion (GTOL)
5relative gradient criterion (GTOL2)
6absolute gradient criterion (ABSGTOL)
7relative function criterion (FTOL)
8predicted function reduction criterion (FTOL2)
9absolute function criterion (ABSFTOL)
10FSIZE value used in GTOL and FTOL criterion
11relative parameter criterion (XTOL)
12absolute parameter criterion (ABSXTOL)
13XSIZE 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:

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 f^{(k)} = f(x^{(k)})    \leq ABSTOL, while for maximization, termination requires f^{(k)} = f(x^{(k)}) \geq 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, \rho, of a spheric trust region from the start radius, \rho_{beg}, which is controlled with the par[2] argument, to the final radius, \rho_{end}, which is controlled with the tc[9] argument. The default value for tc[9] is \rho_{end} = 1E-4. Convergence to small values of \rho_{end} 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[5] specifies another relative function convergence criterion (FTOL2). Termination requires a small standard deviation of the function values of the n+1 simplex vertices x_0^{(k)},  ... , x_n^{(k)}.
    \sqrt{{1 \over n+1} \sum_l (f(x_l^{(k)}) -    \overline{f}(x^{(k)}))^2 } \leq {ftol2}
    where \overline{f}(x^{(k)}) =    {1 \over n+1} \sum_l f(x_l^{(k)}). If there are a active boundary constraints at x^{(k)}, the mean and standard deviation are computed only for the n+1-a unconstrained vertices. The default is tc[5]=1E-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.
    | f_{hi}^{(k)} - f_{lo}^{(k)} | \leq {absftol}
    The default is tc[6]=0.



  • tc[7] specifies the FSIZE value used in the FTOL termination criterion. The default is tc[7]=0.



  • 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.
    {\max_j | x_j^{lo} - x_j^{hi}| \over    \max(| x_j^{lo}|,| x_j^{hi}|, {xsize})}    \leq {xtol}
    The default is tc[8]=1E-8.



  • tc[9] specifies the absolute parameter convergence criterion (ABSXTOL). Termination requires either a small length, \alpha^{(k)}, of the vertices of a restart simplex or a small simplex size, \delta^{(k)}.
    \alpha^{(k)} & \leq & {absxtol} \    \delta^{(k)} & \leq & {absxtol} \
    where \delta^{(k)} is defined as the L1 distance of the simplex vertex with the smallest function value, y^{(k)}, to the other n simplex points, x_l^{(k)} \neq y.
    \delta^{(k)} = \sum_{x_l \neq y}    \parallel x_l^{(k)} - y^{(k)} \parallel_1
    The default is tc[9]=1E-8.



  • tc[10] specifies the XSIZE value used in the XTOL termination criterion. The default is tc[10]=0.
  • Termination Criteria for Unconstrained and Linearly Constrained Techniques



  • tc[5] specifies another relative gradient convergence criterion (GTOL2). This criterion is used only by the NLPLM subroutine.
    \max_j {| g_j(x^{(k)})| \over \sqrt{f(x^{(k)})    g_{j,j}^{(k)}} } \leq {gtol2}
    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.
    \max_j | g_j(x^{(k)})| \leq {absgtol}
    The default is tc[6]=1E-5.



  • tc[7] specifies the relative function convergence criterion (FTOL). Termination requires a small relative change of the function value in consecutive iterations.
    { | f(x^{(k)}) - f(x^{(k-1)})| \over    \max(| f(x^{(k-1)})|,fsize) } \leq {ftol}
    where fsize is defined by tc[10]. The default is tc[7] =    10^{-{\scriptsize fdigits}}, where FDIGITS is controlled by the par[8] argument. The par[8] argument has a default value of \log_{10}(\epsilon), where \epsilon is the machine precision. Hence, the default for FTOL is \epsilon.



  • tc[8] specifies another function convergence criterion (FTOL2). For least squares problems, termination requires a small predicted reduction of the objective function, df^{(k)} \approx f(x^{(k)}) - f(x^{(k)} + s^{(k)}). The predicted reduction is computed by approximating the objective function by the first two terms of the Taylor series and substituting the Newton step, s^{(k)}=-g^{(k)-1}g^{(k)}, as follows:
    df^{(k)} & = & -g^{(k)t}s^{(k)}-{1 \over 2} s^{(k)t}    g^{(k)} s^{(k)} \    & = & -\frac{1}2 s^{(k)t} g^{(k)} \    & \leq & {ftol2}
    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.
    | f(x^{(k-1)}) - f(x^{(k)})| \leq {absftol}
    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.
    {\max_j | x_j^{(k)} - x_j^{(k-1)}| \over    \max(| x_j^{(k)}|,| x_j^{(k-1)}|,{xsize})}    \leq {xtol}
    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.
    \parallel x^{(k)} - x^{(k-1)} \parallel_2    \leq {absxtol}
    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 x or f 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

    l(x,\lambda) = f(x) - \sum_{i=1}^m \lambda_i c_i(x)
    and its gradient
    \nabla_x l(x,\lambda) =   g(x) - \sum_{i=1}^m \lambda_i \nabla_x c_i(x)
    where m denotes the total number of constraints, g=g(x) is the gradient of the objective function, and \lambda is the vector of Lagrange multipliers. The Kuhn-Tucker conditions require that the gradient of the Lagrange function is zero at the optimal point (x^*,\lambda^*), as follows:
    \nabla_x l(x^*,\lambda^*) = 0



  • tc[6] specifies the ABSGTOL criterion, which requires that the maximum absolute gradient element of the Lagrange function be small.
    \max_j | \{\nabla_x l(x^{(k)},\lambda^{(k)})\}_j |    \leq {absgtol}
    The default is tc[6]=1E-5.



  • tc[8] specifies the FTOL2 criterion, which requires that the predicted function reduction be small.
    | g(x^{(k)}) s(x^{(k)})| + \sum_{i=1}^m |\lambda_i c_i|    \leq {ftol2}
    The default is tc[8]=1E-6. This is the criterion used by the programs VMCWD and VF02AD of Powell (1982b).
  • Previous Page | Next Page | Top of Page