find a global solution to a nonlinear program in Matrix form - Global Optimization Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Toolboxes : Global Optimization : GlobalOptimization/GlobalSolveMatrixForm

GlobalOptimization[GlobalSolve](Matrix Form) - find a global solution to a nonlinear program in Matrix form

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) fx

  

subject to

  

vx0 (nonlinear inequality constraints)

  

wx=0 (nonlinear equality constraints)

  

 blxbu (bounds)

  

where x is the vector of problem variables; fx is a real-valued function of x; vx and wx are vector-valued functions of x; and bl and bu 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, procx,y...end proc, 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 bl,bu 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 1 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

withGlobalOptimization:

Find the global solution to an unconstrained nonlinear minimization problem in Matrix form.

p := proc(V) V[1]^2-V[1]+1 end proc:

bl:=Vector0.,datatype=float:

bu:=Vector1.,datatype=float:

bd:=bl,bu:

GlobalSolve1,p,bd

0.750000000000015099,0.500000122749046

(1)

Consider the objective function xy4x5y and constraints 3x2+2y=6 and 4y2+5x20.

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.

bl:=Vector0.,0.,datatype=float:

bu:=Vector5.,5.,datatype=float:

bd:=bl,bu:

Find the global minimum with GlobalSolve.

GlobalSolve2,p,1,1,nlc,bd

8.44181784096971910,1.156858687889460.992517000973123

(2)

See Also

GlobalOptimization, GlobalOptimization/Computation, GlobalOptimization/MatrixForm, GlobalOptimization/Options, GlobalOptimization[GetLastSolution], GlobalOptimization[GlobalSolve], realcons


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam