DAKOTA Coliny DIRECT Algorithm

Description
The DIviding RECTangles (DIRECT) is a derivative free global optimization method for solving single objective optimization problems. This algorithm seeks to balance local search and global search. It performs local search in promising regions and perform global search in under-explored regions at the same time. DIRECT uses a fixed penalty factor for constraint violations.

More Information
As shown in Figure 1, DIRECT adaptively subdivides the space of feasible design points so as to guarantee that iterates are generated in the neighborhood of a global minimum in finitely many iterations.

Figure 1 Subdivision steps of DIRECT algorithm (DAKOTA 5.0 Reference Manual, p. 70)

Algorithm selects points for analysis around already evaluated point by dividing design space into smaller rectangles. The selected points once analyzed are compared and points around the best are selected for evaluation. Depending on the results of the evaluation the algorithm selects points in neighborhood of the new best point. This ensures the algorithm is pursuing the local minima. Within the same iteration the algorithm selects points for iteration around the next best point from previous evaluation. This ensures that the algorithm gets the global minimum. The algorithm continues the process and thus continuously reduces the design space to get in the neighborhood of potential global minima.

DIRECT algorithm terminates with the standard MaxFunctionEvaluations and SolutionTarget specifications. Additionally, the MaxBoxsizeLimit specification terminates the algorithm if the size of the largest sub-region falls below this threshold. The MinBoxsizeLimit specification terminates DIRECT algorithm if the size of the smallest sub-region falls below this threshold. In practice, this latter specification is likely to be more effective at limiting DIRECT.s search.

References
DAKOTA Version 5.0 Reference Manual

ConstraintPenalty: DIRECT algorithm treats constraints with a simple penalty scheme that adds ConstraintPenalty times the sum of squares of the constraint violations to the objective function. The default value of ConstraintPenalty is 1000. ConstraintPenalty should be a positive value.

Division: The Division specification determines how DIRECT algorithm subdivides each sub-region of the search space. If division is set to MajorDimension, then the dimension representing the longest edge of the sub-region is subdivided (this is the default). If division is set to AllDimensions, then all the dimensions are simultaneously subdivided. This parameter controls how fast the search space is reduced.

GlobalBalanceParameter: Each sub-region considered by the algorithm has a size, which corresponds to the longest diagonal of the sub-region. The GlobalBalanceParameter controls how much global search is performed by only allowing a sub-region to be subdivided if the size of the sub-region divided by the size of the largest sub-region is at least equal to this option. This thus means that large sub-regions will be divided before smallest sub-regions are refined. Thus this is a very important option to have control on. The option value must be a positive real number closer to or equal to zero.

LocalBalanceParameter: This option provides a tolerance for estimating whether the smallest sub-region can provide a sufficient decrease to be worth subdividing. This is thus the lower limit of the size of a sub-region. This option decides the fate of smallest sub-regions and whether we want to put in effort to further evaluate design points beyond a certain limit. Thus the value should be greater than or equal to 0.

MaxBoxsizeLimit: This limit is the value below which if the size of the largest sub-region falls the algorithm would terminate. This would not be a desired case for termination in normal circumstances and hence this value is set to 0. The option should have a positive real value closer to 0.

MinBoxsizeLimit: This option limits the size of the smallest sub-region of the design space. Any value below this limit would terminate the algorithm. This is most likely supposed to be most efficient in limiting the DIRECT algorithm's search. This option should have a positive real value greater than or equal to 0.

ConvergenceTolerance: The convergence tolerance specification provides a real value for controlling the termination of iteration. This control defines the threshold value on relative change in the objective function that indicates convergence. In case of flat functions algorithm may terminate with this criterion rather than the MinBoxSizeLimit. Option should have a small value greater than 0.

MaxFunctionEvaluations: Function evaluation is the call to Analyzer to evaluate the objective function at the specified points. The maximum number of function evaluations is an integer limit for evaluations that the algorithm can attain. Algorithm can terminate with this criterion if no other criteria are satisfied. A single iteration can contain multiple function evaluations like evaluating neighboring points in the sub-region. MaxFunctionEvaluations must be a positive integer value.

MaxIterations: A single iteration can have multiple function evaluations. This is the integer limit on number of iterations the algorithm can actually run. Option must have a positive integer value.

IntermediateFilesPath: User can specify the location where the intermediate files of optimization should be generated. By default files are written to the user's temporary directory.

Output: This option controls the level of verbosity of messages user can receive from DAKOTA. The options go from Silent to Debug with increasing amount of messages returned from the infrastructure. View Output > Details should show the messages from algorithm. The user can see the objective function values, constraint violations, design variable values, box sizes, number of boxes, etc. for all iterations when Debug is selected for this option. The detailed information can help user analyze the design space and algorithm convergence better.

TabularGraphicsData: Turning this option to true generates a file named dakota_tabular in IntermediateFilesPath directory. This file has the values of design variables, constraints and objective function for each evaluation stored in a tabular format.