Efficient Computation in the GlobalOptimization Package
Overview of the Global Solver
Specifying the Optimization Problem
The Floating-Point Environment
Working with the evalhf Command
The global solver, which is based on Optimus technology from Noesis Solutions, attempts to find a global solution to a nonlinear program (NLP) over a bounded region. The global solver searches for a solution until one of its stopping criteria is met.
The solver minimizes (or maximizes) an objective function subject to given constraints. The two main methods are OptimusDEVOL which uses a differential evolution algorithm, and OptimusEGO which implements a hybrid algorithm that uses interpolating response surface models. For information on options that control these methods see the GlobalOptimization/Options help page.
You do not need to provide the derivatives of the objective function or constraints. (The help pages often use the term "constraint" to mean the left-hand side of the relation v⁡x≤0 or w⁡x=0.)
The solver offers two main global search strategies:
The first strategy is based upon a differential evolution algorithm. This is the default algorithm, and is also selected using the method=diffevol option.
The second strategy is a hybrid algorithm which uses interpolating response surface models which are rebuilt after each major iteration. This algorithm is selected using the method=ego option.
This help page provides algorithm and computation details for the global solver used in the GlobalOptimization package. It includes suggestions to help you achieve the most efficient performance.
The quality of a solution depends on the following stopping criteria.
The global solver searches for the optimal solution until one of the stopping criteria is met. The best solution found is then returned. If no solution was found, an error occurs. The stopping criteria can be set using options. Otherwise, default values are used. For more information on these options, see the GlobalOptimization/Options help page.
For difficult problems, it is recommended that you set the evaluationlimit option to a sufficiently high value. Otherwise, suboptimal answers may be produced. Setting infolevel[GlobalOptimization] to 3 or higher displays the evaluationlimit value and the final number of objective function evaluations for both the global and local searches.
The algorithm is stopped if the time limit is reached during the global search. In this case, an error occurs. The last computed solution can be retrieved using the GlobalOptimization[GetLastSolution] command. To set the time limit, use the timelimit option.
The GlobalOptimization[GlobalSolve] command recognizes optimization problems specified in three forms: algebraic form, operator form, and Matrix form. The GlobalOptimization[Interactive] Maplet application recognizes only the algebraic form. The GlobalOptimization/InputForms help page provides a summary of all three forms and links to more information.
While the algebraic and operator forms are easier to use, the Matrix form is most similar to the internal representation used by the solvers. Problems entered in algebraic and operator form are automatically converted to Vectors and Matrices. When Matrix form is used, Vectors and Matrices that do not have appropriate datatype and storage formats are converted to formats with the required properties. To avoid unnecessary conversions, it is recommended that all Vectors and Matrices be constructed with datatype=float.
The GlobalOptimization package global solver uses an external library that performs its computation with hardware floats. The GlobalOptimization commands set the UseHardwareFloats environment variable to true internally.
It is possible for the objective function and constraints to be evaluated with higher precision. When the Digits environment variable is set to a value greater than the value of evalhf(Digits), the evaluation of the procedures you specify is performed at the Digits level. However, the input to the procedures you specify is in hardware precision and the output is converted back to hardware floats for the global search computations.
Computation in hardware floats is generally much more efficient. It is recommended that Digits not be increased above evalhf(Digits) unless evaluation of the objective function and constraints must be done with higher precision.
Care must be taken in the construction of the objective function and constraints to ensure that the hardware floating-point environment can be used whenever possible. (See the previous section, The Floating-Point Environment.) These functions are stored internally as procedures in a format similar to that described in the GlobalOptimization/MatrixForm help page. The procedures accept Vector parameters as input and return computed results using Vector or Matrix output parameters. When the objective functions and constraints are provided in algebraic or operator form, they are converted to the internal form.
By default, Maple evaluates the procedure calls using the evalhf command. Procedures that contain any Maple constructs not supported by evalhf are evaluated using the slower evalf command. For more information on evalhf construct support, see the evalhf and evalhf/function help pages. To see messages indicating whether evalhf or evalf is being used, set infolevel[GlobalOptimization] to 2 or higher.
Operator form procedures are not evaluated by evalhf. It is recommended that you do not use operator form input unless ease-of-use is more important than efficiency.
Setting infolevel[GlobalOptimization] to 1 or higher to display messages describing the option values passed to the solver and details of the computation.
A setting of 1 or higher displays the total number of objective function evaluations.
A setting of 2 or higher displays the maximum constraint violation. It is recommended that you examine the maximum constraint violation value to ensure that it is acceptable. The maximum constraint violation can be set using the feasibilitytolerance option.
The solver fails if either the objective function or one of the constraints evaluates to a non-numeric result. This can happen, for example, if the function is complex over a part of the given region. It is recommended that you add checks within the provided functions if this situation can occur.
The solver also fails if an infeasible or unbounded solution has been found or the time limit is exceeded. An infolevel[GlobalOptimization] setting of 1 or higher displays the current solution, if one is available.
Optimus Users Manual Published and distributed by Noesis Solutions, Gaston Geenslaan 11, B4 - 3001 Leuven, Belgium, 2011.
Download Help Document