Nonlinear Programming Add-in
Gradient Direct Search Optimization
With variables and functions defined, we can
proceed to find the values of the variables
that maximize or minimize the function. This
is the Optimize activity. While there are many
ways to optimize nonlinear functions, we have
only programmed two direct search algorithms.
These are only appropriate for solving unconstrained
problems. We expect in later releases to have
a greater variety of optimization procedures,
some applicable to constrained problems.
Both direct search methods are initiated through
menu item. In this
section we discuss the Gradient Search method.
Selecting the menu item presents
the Optimize dialog illustrated below. The top three fields
are RefEdit fields. These allow the user to specify ranges
on the worksheet by selecting them with the cursor. We prefer
that the the student enter the contents of these fields as
described in this section, but the RefEdit fields offer flexibility
that will sometimes be useful.
The top field on the dialog holds the address of the worksheet
cell where the results of the procedure will be presented.
Again, this is the cell at the top left corner of a range that
may extend considerably to the right and below the cell. The
program will issue a warning if parts of the worksheet are
to be overwritten. The default contents of the Results Location field
is the address of the current cursor location. For this dialog,
the field is not locked. A different address can be entered
manually, or the RefEdit field allows the user to point to
the desired location with the cursor.
The Objective Cell holds the name of the function to
be optimized. The Variable Range holds the name of the
decision variable. Of course, these names must have previously
been defined through the Add Function and Add Variable menu
The remainder of the dialog holds various options.
The Objective frame determines the direction of optimization.
In addition to Maximize and Minimize, we include
the Evaluate button. With this option, the program evaluates
the point currently specified in the Y vector.
The Solution Method frame shows the two
methods currently available. In this section we are discussing
the Gradient direct search method. The Start Solution frame
indicates whether the procedure is to start from a zero vector
or from the current value of the Y vector. Two solution options
are provided. In the Demo option, the program stops at each
step with a description of the current activities of the algorithm.
This is useful for instruction. The Run option goes through
the steps of the algorithm without interruption.
The results presented by the program are determined
by the several check boxes on the dialog. They will be illustrated
through the examples on this page.
The Params button
allows the user to specify stopping criteria and other parameters
for the direct search methods. Direct search algorithms for
nonlinear programming actually look for the optimum with intelligent
trial and error. There are no conditions that identify the
optimum exactly, rather we specify a set of termination criteria
that indicate that the program may be close to the optimum.
Pressing the Params button presents the dialog below.
Here we define the various terms on the dialog.
Most of the entries on the dialog are stopping criteria for
the direct search procedure. Whenever the program reaches a
point that satisfies one of these criteria, it stops. If the Termination
Message option has been chosen, the user can then change
the criteria and allow the search process to continue.
- Step for Numerical Estimation of Derivatives: First
and second derivatives are estimated by finite difference
methods that compute the function for slightly different
values of the decision variables. This is difference between
Direct Search Stopping Criteria
- Gradient Norm: The gradient is the vector of first
derivatives. It's norm is the magnitude of the gradient vector.
One expects this number to be small near the optimum. When
the gradient norm gets smaller than this limit, the program
stops and identifies the point as a stationary point.
- Function Difference: Near the optimum, the difference
between successive values of the objective function will
become small. When the difference is smaller than this number,
the program stops.
- Step Size: At each iteration of a direct search
method, a step is taken in some search direction that will
improve the objective function. Near the optimum, one expects
this step to become smaller and smaller. When the magnitude
of the step falls below the limit specified here, the program
- Number of Steps: At this number of steps, the program
- Search Range: The program uses a Golden Section
line search procedure to find the optimum point along a search
direction. The search direction is given by a vector. The
length of the step is the magnitude of the direction vector
multiplied by the number determined by the Golden Section.
This parameter is the maximum of the latter. In cases where
the direction vector is normalized, as for the gradient search,
the search range gives the length of the maximum search step.
- Number of Evaluations: This is the number of steps
taken by the golden section method. The default value, 25,
gives a range of uncertainty at termination of around 10
raised to the -5 power. This is a very small number.
- Max Iterations at Limit: When the step size is at
the maximum step value 3 times in a row, the program suspects
that the optimum may be unbounded. The program then stops.
Bounds on Variables
- When a component of the search vector goes outside the
range specified here, the program judges that the optimum
may be unbounded. The program warns the student and provides
an opportunity to terminate.
Direct Search with the Gradient Method
The OK button initiates
the direct search procedure. If the Search Steps output
option has been chosen, the progress of the search will be
displayed as below. The example is the G(Y) function defined
earlier. The starting point is the zero value of the decision
vector. At each step we see a yellow area showing the value
of the objective function, outlined in red, and the values
of the decision variables.
The green areas show the direction vector, D(k). For the gradient
search, the search direction is proportional to the gradient.
For minimization the search goes in the negative direction
of the gradient, and for maximization the search goes in the
positive direction. We have normalized the gradient vector
so that its magnitude is 1. The yellow area below the direction
vector is the length of the step that minimizes the objective
function in the search direction. The number below the yellow
area is the number of function evaluations necessary for the
search. In this case the number is 29, the number of iterations
of the golden section search plus the 4 necessary to numerically
estimate the gradient.
When the Termination Message box is checked,
the program stops when one of the stopping criteria is met.
The program presents a summary of the current results and allows
the user to change the criteria. In this case, we select Stop and
the final results are presented.
The extent of the results depends on the options
checked on the Optimization dialog. For the example, all the
options were chosen. The Row Titles option prints the
contents of column D. For some applications, we might what
a series of solutions for different problem parameters. For
a better presentation, show the titles only with the first
run. The Solution option shows the solution shown in
column E. The Gradient Option shows the gradient vector
for the variable values of the current solution. The Hessian matrix
is the matrix of second derivatives. With that option chosen
the program numerically estimates the Hessian matrix, shown
for the example in columns G and H. The Diagonalization option,
transforms the Hessian to obtain a diagonal matrix. This matrix
is used for the analysis.
The Analysis option presents information about
the search process. The first line for the example shows the
termination mechanism. The second line shows the current magnitude
of the gradient vector. The value does not fall below the limit
of 0.001 specified in the parameter list, so the point is judged
to be not a stationary point. The diagonalization is used to
determine the character of the Hessian matrix. In this case
it is positive definite, indicating that the function is convex
at this point. For a stationary point this would indicate a
local minimum. Including the numerical estimates of the gradient
and Hessian matrices necessary for the final analysis, the
process required 217 evaluations of the G function. This measure
can be used to compare different search strategies.