GlbSolve
Purpose
Solve box-bounded global optimization problems. glbSolve solves problems of the form
where Failed to parse (unknown function "\MATHSET"): {\displaystyle $f \in \MATHSET{R}$}
and Failed to parse (unknown function "\MATHSET"): {\displaystyle $x,x_{L},x_{U}\in \MATHSET{R} ^{n}$}
.
Calling Syntax
Result = glbSolve(Prob,varargin)
Result = tomRun('glbSolve', Prob);
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
x_L | Lower bounds for x, must be given to restrict the search space. | |
x_U | Upper bounds for x, must be given to restrict the search space. | |
Name | Name of the problem. Used for security if doing warm start. | |
FUNCS.f | Name of m-file computing the objective function f (x). | |
PriLevOpt | Print Level. 0 = silent. 1 = some printing. 2 = print each iteration. | |
WarmStart | If true, > 0, glbSolve reads the output from the last run from the mat-file glbSave.mat, and continues from the last run. | |
MaxCPU | Maximal CPU Time (in seconds) to be used. | |
optParam | Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used: | |
IterPrint | Print iteration \#, \# of evaluated points and best f(x) each iteration. | |
MaxIter | Maximal number of iterations, default max(5000, n * 1000). | |
MaxFunc | Maximal number of function evaluations, default max(10000, n * 2000). | |
EpsGlob | Global/local weight parameter, default 1E-4. | |
fGoal | Goal for function value, if empty not used. | |
eps_f | Relative accuracy for function value, f T ol == epsf . Stop if abs(f - f Goal)<= abs(f Goal) * f T ol , if f Goal = 0. Stop if abs(f - f Goal) <= f T ol , if f Goal == 0. | |
If warm start is chosen, the following fields saved to glbSave.mat are also used and contains information from the previous run: | ||
C | Matrix with all rectangle centerpoints, in [0,1]-space. | |
D | Vector with distances from centerpoint to the vertices. DMin Row vector of minimum function value for each distance. DSort Row vector of all different distances, sorted. | |
E | Computed tolerance in rectangle selection. | |
F | Vector with function values. | |
L | Matrix with all rectangle side lengths in each dimension. Name Name of the problem. Used for security if doing warm start. glbfMin Best function value found at a feasible point. | |
iMin | The index in D which has lowest function value, i.e. the rectangle which mini- mizes (F -glbf M in+E)./D where E = max(EpsGlob*abs(glbf M in), 1E -8). | |
varargin | Other parameters directly sent to low level routines. |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
x_k | Matrix with all points giving the function value f k. | |
f_k | Function value at optimum. | |
Iter | Number of iterations. | |
FuncEv | Number function evaluations. | |
maxTri | Maximum size of any triangle. | |
ExitText | Text string giving ExitFlag and Inform information. | |
ExitFlag | Exit code. | |
0 = Normal termination, max number of iterations /func.evals reached. | ||
1 = Some bound, lower or upper is missing. | ||
2 = Some bound is inf, must be finite. | ||
4 = Numerical trouble determining optimal rectangle, empty set and cannot continue. | ||
Inform | Inform code. | |
0 = Normal Exit. | ||
1 = Function value f is less than fGoal. | ||
2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f - f Goal)/abs(f Goal) <= f T ol. | ||
9 = Max CPU Time reached. | ||
Solver | Solver used, 'glbSolve'. |
Description
The global optimization routine glbSolve is an implementation of the DIRECT algorithm presented in \[14\]. DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore glbSolve runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to restart glbSolve with the final status of all parameters from the previous run, a so called warm start Assume that a run has been made with glbSolve on a certain problem for 50 iterations. Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of glbSolve a flag Prob.WarmStart should be set to one. Then glbSolve is using output previously written to the file glbSave.mat to make the restart. The m-file glbSolve also includes the subfunction conhull (in MEX) which is an implementation of the algorithm GRAHAMHULL in \[65, page 108\] with the modifications proposed on page 109. conhull is used to identify all points lying on the convex hull defined by a set of points in the plane.
M-files Used
iniSolve.m, endSolve.m