GlbSolve: Difference between revisions
(Created page with "==Purpose== Solve box-bounded global optimization problems. ''glbSolve ''solves problems of the form <math> \begin{array}{cccccc} \min\limits_{x} & f(x) & & & & \\ s/t & ...") |
No edit summary |
||
(6 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
[[Category:Solvers]] | |||
==Purpose== | ==Purpose== | ||
Line 13: | Line 14: | ||
where <math> | where <math>f \in \mathbb{R}</math> and <math>x,x_{L},x_{U}\in \mathbb{R} ^{n}</math>. | ||
==Calling Syntax== | ==Calling Syntax== | ||
<source lang="matlab"> | |||
Result = glbSolve(Prob,varargin) | Result = glbSolve(Prob,varargin) | ||
Result = tomRun('glbSolve', Prob); | Result = tomRun('glbSolve', Prob); | ||
</source> | |||
==Inputs== | |||
{| class="wikitable" | |||
{| | !''Prob''|| colspan="2" | Problem description structure. The following fields are used: | ||
|- | |- | ||
|||''x_L''||Lower bounds for ''x'', must be given to restrict the search space. | |||''x_L''||Lower bounds for ''x'', must be given to restrict the search space. | ||
Line 36: | Line 37: | ||
|- | |- | ||
|||''PriLevOpt''||Print Level. 0 = silent. 1 = some printing. 2 = print each iteration. | |||''PriLevOpt''||Print Level. 0 = silent. 1 = some printing. 2 = print each iteration. | ||
|- | |-valign="top" | ||
|||''WarmStart''||If true, ''> ''0, glbSolve reads the output from the last run from the mat-file glbSave.mat, and continues from the last run. | |||''WarmStart''||If true, ''> ''0, glbSolve reads the output from the last run from the mat-file glbSave.mat, and continues from the last run. | ||
|- | |- | ||
Line 53: | Line 54: | ||
|||''fGoal''||Goal for function value, if empty not used. | |||''fGoal''||Goal for function value, if empty not used. | ||
|- valign="top" | |- valign="top" | ||
|||''eps_f''||Relative accuracy for function value, '' | |||''eps_f''||Relative accuracy for function value, ''fTol ''== ''eps<sub>f</sub> ''. Stop if ''abs''(''f - fGoal'')''<''= ''abs''(''fGoal'') ''* fTol '', if ''fGoal ''= 0. Stop if ''abs''(''f - fGoal'') ''<''= ''fTol '', if ''fGoal ''== 0. | ||
|- | |- | ||
||| colspan="2" | If warm start is chosen, the following fields saved to ''glbSave.mat ''are also used and contains information from the previous run: | ||| colspan="2" | If warm start is chosen, the following fields saved to ''glbSave.mat ''are also used and contains information from the previous run: | ||
Line 59: | Line 60: | ||
|||''C''||Matrix with all rectangle centerpoints, in [0,1]-space. | |||''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. | |||''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. | |||''E''||Computed tolerance in rectangle selection. | ||
Line 65: | Line 70: | ||
|||''F''||Vector with function values. | |||''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. | |||''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. | |||
|- valign="top" | |- valign="top" | ||
|||''iMin''||The index in D which has lowest function value, i.e. the rectangle which | |||''iMin''||The index in D which has lowest function value, i.e. the rectangle which minimizes (''F - glbfMin''+''E'')''./D ''where ''E ''= ''max''(''EpsGlob*abs''(''glbfMin'')'', ''1''E -''8). | ||
|- | |- | ||
|||''varargin''||Other parameters directly sent to low level routines. | |||''varargin''||Other parameters directly sent to low level routines. | ||
|} | |} | ||
== | ==Outputs== | ||
{| | |||
{| class="wikitable" | |||
!''Result''|| colspan="2"|Structure with result from optimization. The following fields are changed: | |||
|- | |- | ||
|||''x_k''||Matrix with all points giving the function value '' | |||''x_k''||Matrix with all points giving the function value ''f_k''. | ||
|- | |- | ||
|||''f_k''||Function value at optimum. | |||''f_k''||Function value at optimum. | ||
Line 87: | Line 97: | ||
|- | |- | ||
|||''ExitText''||Text string giving ExitFlag and Inform information. | |||''ExitText''||Text string giving ExitFlag and Inform information. | ||
|- | |-valign="top" | ||
|||''ExitFlag''||Exit code. | |||''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. | |||
|- | |-valign="top" | ||
|||''Inform''||Inform code. | |||''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 - fGoal'')''/abs''(''fGoal'') ''<''= ''fTol''. | |||
9 = Max CPU Time reached. | |||
|- | |- | ||
|||''Solver''||Solver used, 'glbSolve'. | |||''Solver''||Solver used, 'glbSolve'. | ||
Line 113: | Line 123: | ||
==Description== | ==Description== | ||
The global optimization routine ''glbSolve ''is an implementation of the DIRECT algorithm | The global optimization routine ''glbSolve ''is an implementation of the DIRECT algorithm. 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 with a modification. ''conhull ''is used to identify all points lying on the convex hull defined by a set of points in the plane. | |||
==M-files Used== | ==M-files Used== | ||
''iniSolve.m'', ''endSolve.m'' | ''iniSolve.m'', ''endSolve.m'' |
Latest revision as of 08:10, 16 January 2012
Purpose
Solve box-bounded global optimization problems. glbSolve solves problems of the form
where and .
Calling Syntax
Result = glbSolve(Prob,varargin)
Result = tomRun('glbSolve', Prob);
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, fTol == epsf . Stop if abs(f - fGoal)<= abs(fGoal) * fTol , if fGoal = 0. Stop if abs(f - fGoal) <= fTol , if fGoal == 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 minimizes (F - glbfMin+E)./D where E = max(EpsGlob*abs(glbfMin), 1E -8). | |
varargin | Other parameters directly sent to low level routines. |
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 - fGoal)/abs(fGoal) <= fTol. 9 = Max CPU Time reached. | |
Solver | Solver used, 'glbSolve'. |
Description
The global optimization routine glbSolve is an implementation of the DIRECT algorithm. 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 with a modification. 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