OPTIMIZE

OPTIMIZE (LET)

Let Subcommand

Determine the minimum of a function.

Function minimization/maximization has many applications in mathematics and statistics.

Minimization can be either unconstrained or constrained. Constrained minimization limits the domain of the variables that define the function. The OPTIMIZE command currently only supports unconstrained minimization.

Finding the maximum of a function is equivalent to finding the minimum of the negative of a function. Therefore, the OPTIMIZE command can be used to find the maximum of a function as well (simply take the negative of the relevant function).

Multivariate functions may have many local minimum and maximum. Although the goal is typically to find the global minimum (or maximum), most numerical techniques may in fact find a local minimum (or maximum) point. If something is known about the function, specifying better starting values can sometimes alleviate this problem. Specifying starting values is discussed below. There are optimization techniques, such as simulated annealing, that attempt to avoid the problem of finding a local rather than a global minimum. Dataplot does not currently support any of these global optimization techniques.

LET <par> = OPTIMIZE <func> WRT <var> FOR <var> = <lower> <upper>
where <func> is the name of a previously defined function or a functional expression;
            <var> is the variable for which the optimization is being computed;
            <lower> is a number or parameter defining the lower limit for finding the minimum;
            <upper> is a number or parameter defining the upper limit for finding roots;
            <par> is a parameter where the value of <var> at the minimum is stored.

This syntax minimizes a univariate function.

LET <var> = OPTIMIZE <func> WRT <var-list>
where <func> is the name of a previously defined function or a functional expression;
            <var-list> is a list of variables for which the minimization is being computed;
            <var> is a variable where the values of <var-list> at the minimum are stored.

This syntax minimizes a multivariate function.

LET A = OPTIMIZE X**2 + 2*X - 4 WRT X FOR X = -10 10


LET A = OPTIMIZE X**2 +Y**2 - X*Y WRT X Y


LET FUNCTION F1 = X**2 + Y**2 - X*Y
LET A = OPTIMIZE F1 WRT X Y

Univariate optimization is implemented using the FMIN routine from the "Numerical Methods and Software" book by Kahaner, Moler, and Nash. Multivariate optimization is implemented using the UNCMIN package of Schnabel and Weiss.

The FMIN routine was written by R. Brent and uses a combination of golden section search and successive parabolic interpolation.

The UNCMIN package is designed to incorporate a number of different variations of quasi-Newton (also known as variable metric) approaches to unconstrained optimization. See the Dennis and Schnabel or chapter 10 of Numerical Recipes for a more detailed discussion of these issues.

Specifically, the UNCMIN routines allow the following variations of the method.

• You can specify the global strategy to use at each iteration.
  1. Line search
  2. Hookstep trust region
  3. Dogleg trust region
  Although these methods can vary in efficiency and accuaracy for some problems, none of them is superior in general.

• You can specify the type of gradient (first derivative) to compute.
  1. Use an analytic gradient.
  2. Use a numerical approximation based on finite differences.

• You can specify the type of updating for the Hessian matrix at each step.
  1. Use analytic derivatives.
  2. Use a finite difference approximation.
  3. Use BFGS (Broyden-Fletcher-Goldfarb-Shanno) updating (a positive definite secant updating method).
  Generally, BFGS is considered superior to using finite difference approximation.

This results in 18 (3*2*3) methods. This effectively is 15, as using numerical first derivative with analytic updating of the Hessian matrix is unrealistic.

Dataplot only supports numerical approximations for the first derivatives and the Hessian matrix, so this reduces to six methods (three types of global strategy and two types of approximation for the Hessian matrix).

You can use the following command to specify which of the six methods to use in Dataplot:

OPTIMIZATION METHOD <LINE/DOGLEG/HOOK>       <FINITE/BFGS>

The default is LINE and FINITE.

Note that optimization of functions is an area of much mathematical research and there are a number of other approaches to optimization (e.g., Nelder-Meld simplex, conjugate gradient methods) as well (not currently supported in Dataplot). Each of these methods have advantages and disadvantages.

The UNCMIN procedures are intended for to small to moderate size problems. Problems with a large number of variables typically require sparse matrix techniques which are not currently implemented in Dataplot. In general, the UNCMIN routines provide good results for a broad class of problems. However, there will be some problems for which they may not work well.

By default, Dataplot finds the minimum of a function. If you want to find the maximum of a function, you can do one of the following.
1. You can take the negative of your function. That is, if F is your original function, enter
   LET FUNCTION G = -F

   and then use G in the OPTIMIZE command.

2. The following command was added in the September 2015 version

   SET OPTIMIZE <MINIMUM/MAXIMUM>

   where MINIMUM specificies that the function is being minimized and MAXIMUM specifies that the function is being maximized. The default is to find the minimum of the function.

Minimization routines can sometimes settle on a local rather global minimum. If you have some knowledge of the function, you can sometimes solve this problem by setting the values of the function parameters using the LET command.

The followng example shows how to specify the starting values.

LET FUNCTION F1 = X**2 + Y**2 - X*Y
LET X = 0.1
LET Y = 0.1
LET A = OPTIMIZE F1 WRT X Y

The primary limitation of the OPTIMIZE command for statistical applications is that Dataplot's function library does not currently support a summation function. This prevents the OPTIMIZE command from being used for most maximum likelihood problems. Maximum likelihood estimation is the primary application of function minimization in statistics. This limitation is currently under investigation.

The 2016/09 version of Dataplot introduced a new feature called "function blocks". This feature allows you to use various LET subcommands in defining your function. Specifically, this allows us to now define many of the functions that are needed in many statistical applications. To see how function blocks are defined and used, enter HELP FUNCTION BLOCKS. This gives several examples of using function blocks with the OPTIMIZE command.

Function minimization can be a numerically difficult problem. For this reason, a number of options can be provided to help improve the performance of the minimization code. Dataplot will provide defaults for each of these. However, if you have some knowledge of the function being minimized, specifying one or more of these parameters may help.

The following parameters can be specified when minimizing a function:

• LET OPTSCALE = (default = 1.0)

  OPTSCALE is used to provide an estimate of the scale of the minimization function. If know, Specifying the scalei may help provide better numerical results

• LET OPTMSG = (default = 8)

  OPTMSG can be used to control the output and certain checks. Normally, this option is only used for debugging purposes.

• LET OPTITER = (default = 150)

  OPTITER is used to specify the maximum number of iterations.

• LET OPTDLT = (default = 0)

  OPTDLT specifies the trust region radius.

• LET OPTRDTL = (default = R1MACH(4)**(1/3))

  OPTRDTL specifies the tolerance at which the gradient is considered close enough to zero to terminate the algorithm.

• LET OPTSPMX = (default = 0)

  OPTSTPMX specifies the value of zero to trip default maximum.

• LET OPTSTPTL = (default = 0)

  OPTSTPTL specifies the tolerance at which successive iterations are considered close enough to terminate the algorithm.

Note that default values of 0 imply that the UNCMIN will determine the default and this default may be dependent on the particular function being optimized.

The optimized value of the function is saved in the internal parameter OPTVALUE.

For multivariate optimization, the following information is written to files.

DPST1F.DAT - The gradients (derivatives) of each variable.
DPST2F.DAT - The Hessian matrix.

None

None

MATRIX SIMPLEX SOLUTION	=	Solve linear programming problem using simplex algorithm.
ROOTS	=	Find the roots of a univariate function.
NUMERICAL DERIVATIVE	=	Compute the derivative of a function.
INTEGRAL	=	Compute the integral of a function.
RUNGE KUTTA	=	Runge Kutta differential equation solver.
INTERPOLATE	=	Interpolate a function.
3D-PLOT	=	Generate a 3D plot.
CONTOUR PLOT	=	Generate a countor plot.

Kahaner, Moler, and Nash (1989), "Numerical Methods and Software", Prentice-Hall.

R. P. Brent (1973), "Algorithms for Minimization Without Derivatives", Prentice-Hall.

J. E. Dennis, Jr. and Dennis B. Schnabel (1996), "Numerical Methods for Unconstrained Optimization and Nonlinear Equations", SIAM.

R. B. Schnabel, J. E. Koontz, and B. E. Weiss (1982), "A Modular System of Algorithms for Unconstrained Optimization", Report Cu-CS-240-82, Computer Science Department, University of Colorado.

Press, Teukolsky, Vetterling, and Flannery (1992), "Numerical Recipes in Fortran: The Art of Scientific Programming", 2nd, ed., Cambridge University Press.

Maximum Likelihood Estimation

1996/05
2015/09: Added support for function blocks.
2015/09: Added the SET OPTIMIZE <MINIMUM/MAXIMUM> command.

LET FUNCTION F = X**2 + 2*X - 4
PLOT F FOR X = -10 0.01 10
LET A = OPTIMIZE F WRT X FOR X = -10 10
LET X = DATA A
LET Y = F
LET OPTVALUE = Y(1)
JUSTIFICATION CENTER
MOVE 50 5
TEXT MINIMUM OF ^OPTVALUE AT X = ^A

LET FUNCTION F = X**2 + Y**2 -X*Y
3D-PLOT F FOR X = -3 0.1 3 FOR Y = -3 0.1 3
OPTIMIZATION METHOD LINE BFGS
LET XPTS = OPTIMIZE F WRT X Y
LET X1 = XPTS(1)
LET Y1 = XPTS(2)
JUSTIFICATION CENTER
MOVE 50 5
TEXT MINIMUM OF ^OPTVALUE AT X = ^X1 AND Y = ^Y1