Gradient Direct Search Optimization
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 items.
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.
Direct Search Stopping Criteria
Bounds on Variables
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 matices necessary for the final analysis, the process required 217 evaluations of the G function. This measure can be used to compare different search strategies.
Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors