|
Calling Sequence
|
|
GlobalSolve(n, p, nc, nlc, bd, opts)
GlobalSolve(n, p, bd, opts)
|
|
Parameters
|
|
n
|
-
|
positive integer; number of variables
|
p
|
-
|
procedure; objective function
|
nc
|
-
|
non-negative integer or list of 2 non-negative integers; number of nonlinear constraints
|
nlc
|
-
|
procedure; nonlinear constraints
|
bd
|
-
|
list; bounds
|
opts
|
-
|
(optional) equation(s) of the form option = value where option is one of evaluationlimit, feasibilitytolerance, initialpoint, maximize, merittarget, method, noimprovementlimit, objectivetarget, optimalitytolerance, penaltymultiplier or timelimit; specify options for the GlobalSolve command
|
|
|
|
|
Description
|
|
•
|
The GlobalSolve command attempts to compute a global solution to a nonlinear program (NLP) over a bounded region. See the following Notes section for a detailed explanation of the solution obtained. An NLP has the following form:
|
|
minimize (or maximize)
|
|
(nonlinear inequality constraints)
|
|
(nonlinear equality constraints)
|
|
where is the vector of problem variables; is a real-valued function of ; and are vector-valued functions of ; and and are vectors. The relations involving vectors are element-wise.
|
|
The global solver optimizes a merit function, incorporating a penalty term for the constraints, and provides both branch-and-bound and adaptive stochastic search methods. The global search phase is followed by a local search phase to refine the solution. No derivatives are required.
|
•
|
This help page describes how to specify the problem in Matrix form. For details about the exact format of the objective function and the constraints, see the GlobalOptimization/MatrixForm help page. The algebraic and operator forms for specifying an NLP are described in the GlobalOptimization[GlobalSolve] help page. The Matrix form is more complex, but leads to more efficient computation.
|
•
|
The solver is designed to search the specified region for a global solution to a non-convex optimization problem. If the optimization problem is convex (for example, a linear program) or a local solution is acceptable, it is recommended that you use the commands for local optimization in the Optimization package. The Optimization package commands, which are more efficient, can compute global solutions to convex problems.
|
•
|
Consider the first calling sequence. The first parameter n is the number of problem variables. The second parameter p is a procedure that takes one input Vector parameter of size n, representing x, and returns the value of f(x).
|
|
The third parameter nc is a list of two non-negative integers representing the number of nonlinear inequality constraints and the number of nonlinear equality constraints. If there are no inequality constraints, nc can be a single integer value. The fourth parameter nlc is a procedure, , that computes the values of the nonlinear constraints. The current point is passed as the Vector x, and the values of v(x) followed by the values of w(x) are returned using the Vector parameter y.
|
|
The fifth parameter bd is a list of lower and upper bounds. In general, bl and bu must be n-dimensional Vectors. The GlobalOptimization/MatrixForm help page describes an alternate way of specifying the Vectors.
|
•
|
If there are no nonlinear constraints, the second calling sequence, in which parameters nc and nlc are omitted, should be used.
|
•
|
Maple returns the solution as a list containing the final minimum (or maximum) value and a Vector representing a point (the extremum).
|
|
|
Options
|
|
|
The opts argument can contain one or more of the following options. These options are described in more detail in the GlobalOptimization/Options help page.
|
|
Some options apply to only the local search phase that follows the global search phase. The descriptions for those options specifically mention local search. Otherwise, the option applies to the global search.
|
•
|
evaluationlimit = posint -- Set the maximum number of merit function evaluations performed during the global search. The global search phase terminates if this limit is reached.
|
•
|
feasibilitytolerance = positive and numeric -- Set the maximum absolute allowable constraint violation in the local search phase.
|
•
|
initialpoint = set(equation), list(equation), or list(numeric) -- Use the provided initial point, which is an n-dimensional Vector.
|
•
|
maximize = truefalse -- Maximize the objective function when m is 'true' and minimize when m is 'false'. The option 'maximize' is equivalent to 'maximize'='true'. The default is 'maximize'='false'.
|
•
|
merittarget = numeric -- Set an acceptable target value for the merit function. If the merit function achieves this value, the global search phase terminates.
|
•
|
method = branchandbound, singlestart, multistart, or reducedgradient -- Set the global search algorithm: branch-and-bound (method=branchandbound), adaptive random search with a single starting point (method = singlestart), or adaptive random search with multiple starting points (method = multistart). Specifying method = reducedgradient omits the global search phase, performing the local search only. The default is method = multistart.
|
•
|
noimprovementlimit = posint -- Set the maximum number of merit function evaluations performed with no improvement in the merit function. The global search phase terminates if this limit is reached.
|
•
|
objectivetarget = numeric -- Set an acceptable target value for the objective function in the local search phase. If the objective function achieves this value, then the local search phase terminates.
|
•
|
optimalitytolerance = positive and numeric -- Set the tolerance for the Kuhn-Tucker optimality conditions in the local search phase.
|
•
|
penaltymultiplier = positive and numeric -- Set the constraint penalty multiplier. The constraint violations in the merit function are weighted by this value, which must evaluate to a positive numeric value.
|
•
|
timelimit = posint -- Set the maximum computation time, in seconds, for the global solver.
|
|
|
Notes
|
|
•
|
For more information on the methods used by the global solver, with suggestions for achieving best performance, see the GlobalOptimization/Computation help page.
|
•
|
The global solver searches for the optimal solution until one of the termination criteria is met. Then either the best available solution is returned or an error is issued stating that a solution could not be obtained. The termination criteria can be set using the options. Otherwise, default values for these options are applied. In particular, the evaluationlimit option must be set to a sufficiently high value for difficult optimization problems or unexpected answers may be produced.
|
•
|
In the case that an error is issued because the time limit has been exceeded, the last solution computed may be retrieved using the GetLastSolution command.
|
•
|
It is highly recommended that you set infolevel[GlobalOptimization] to or higher to display messages describing the progress of the solver. These messages can give indications that the solution might not be optimal and that option values should be adjusted.
|
•
|
The computation is performed in floating-point. Therefore, all data provided must have type realcons and all returned solutions are floating-point, even if the problem is specified with exact values. The solver uses externally called code that works with hardware floats, but it is possible to evaluate the objective function and the constraints in Maple with higher precision. See the GlobalOptimization/Computation help page for details.
|
|
|
Examples
|
|
>
|
|
Find the global solution to an unconstrained nonlinear minimization problem in Matrix form.
>
|
p := proc(V) V[1]^2-V[1]+1 end proc:
|
>
|
|
>
|
|
>
|
|
>
|
|
| (1) |
Consider the objective function and constraints and .
Express the objective function as a procedure.
>
|
p:= proc(V) -4*V[1]+V[1]*V[2]-5*V[2] end proc:
|
Express the constraints in a single procedure with the parameters V and W.
>
|
nlc := proc(V, W)
W[1] := 5*V[1]+4*V[2]^2-20;
W[2] := 3*V[1]^2+2*V[2]-6
end proc:
|
Express the bounds in Matrix form.
>
|
|
>
|
|
>
|
|
Find the global minimum with GlobalSolve.
>
|
|
| (2) |
|
|
|