MultiMin: Difference between revisions
(Created page with "==Purpose== multiMin solves general constrained mixed-integer global optimization problems. It tries to find all local minima by a multi-start method using a suitable nonline...") |
No edit summary |
||
Line 1: | Line 1: | ||
[[Category:Solvers]] | |||
{{cleanup|Clean this article.}} | |||
==Purpose== | ==Purpose== | ||
Revision as of 08:22, 11 July 2011
{{#switch: | left =
{{#switch:{{#if: | {{{smallimage}}} | }} | none =| #default =
}} {{#if:{{#if: | {{{smallimageright}}} | }} | {{#ifeq:{{#if: | {{{smallimageright}}} | }}|none | | }} }}{{
#switch:left | left =| #default = }} {{#if:{{#if: | {{{smallimage}}} | }} | {{#if: | {{{smallimage}}} | }} | [[File:{{#switch:caution | critical = Ambox speedy deletion.png | important = Ambox deletion.png | warning = Ambox content.png | caution = Cleanup.png | move = Ambox move.png | protection = Ambox protection.png | notice | #default = Cleanup.png }} | {{#switch:left | left = 20x20px | #default = 40x40px }} |link=|alt=]] }}{{#switch:left | left =| #default = | {{#if:
| {{{smalltext}}} | Cleanup is needed}} | {{#switch:left
| left = {{#if: | {{{smallimageright}}} | }}| #default = {{#if:
}}| {{{smallimageright}}} |}} |
| #default =
{{#switch: | none =| #default =
}}{{#if: | {{#ifeq:|none
|| }} }}
{{
#switch: | left =| #default = }} {{#if: | | [[File:{{#switch:caution | critical = Ambox speedy deletion.png | important = Ambox deletion.png | warning = Ambox content.png | caution = Cleanup.png | move = Ambox move.png | protection = Ambox protection.png | notice | #default = Cleanup.png }} | {{#switch: | left = 20x20px | #default = 40x40px }} |link=|alt=]] }}{{#switch: | left =| #default = | Cleanup is needed Clean this article. |
{{#switch:
| left =| #default = |
}}
Purpose
multiMin solves general constrained mixed-integer global optimization problems. It tries to find all local minima by a multi-start method using a suitable nonlinear programming subsolver.
multiMin solves problems of the form
Failed to parse (unknown function "\multicolumn"): {\displaystyle \begin{array}{cccccc} \min\limits_{x} & f(x) & & & & \\ s/t & x_{L} & \leq & x & \leq & x_{U} \\ & b_{L} & \leq & Ax & \leq & b_{U} \\ & c_{L} & \leq & c(x) & \leq & c_{U} \\ & & & \multicolumn{3}{c}{x_i \in \MATHSET{N} \; \forall i \in I} \\ \end{array} }
where Failed to parse (unknown function "\MATHSET"): {\displaystyle x,x_{L},x_{U}\in \MATHSET{R}^{n}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle A\in \MATHSET{R}^{m_{2}\times n}} and Failed to parse (unknown function "\MATHSET"): {\displaystyle b_{L},b_{U}\in \MATHSET{R}^{m_{2}}} .
The variables , the index subset of are restricted to be integers.
The integer components of every x_0 is rounded to the nearest integer value inside simple bounds, and these components are fixed during the nonlinear local search.
If generating random points and there are linear constraints, multiMin checks feasibility with respect to the linear constraints, and for each initial point tries 100 times to get linear feasibility before accepting the initial point.
Calling Syntax
Result = multiMin(Prob, xInit)
Result = tomRun('multiMin', Prob, PriLev) (driver call)
Description of Inputs
3 = tomRun (PrintResult) output from every optimization, print level 1.Prob | Problem description structure. The following fields are used: | |
xInit | Either, 1x1 number - The number of random initial points, default 10\*Prob.N dxm matrix - Every column is an initial point (of length d=Prob.N). May also be set as Prob.xInit. | |
fCut | If initial f(x_0) > fCut, no local optimization is done. | |
WarmStart | If true, > 0, multiMin assumes the field multiMin defined with the output from a previous run on the same problem. See the Output fields of Result.multiMin. Use WarmDefGLOBAL to set the correct fields in the Prob structure. Nec- essary fields are fOpt and xOpt. If any of the other fields are missing, the corresponding variables are initialized to 0. These other fields are: localTry, Iter, FuncEv, GradEv, HessEv, ConstrEv Inform (is set to zeros(length(fOpt,1) if not defined). | |
In WarmDefGLOBAL the Result structure for the optimal run will be fed back to multiMin as Prob.multiMin.ResOpt In case this field is not defined, and no better point is found during the runs, a special call to the localSolver is used to generate a proper Result structure. | ||
RandState | If WarmStart and isscalar(xInit), RandState is used as follows: If > 0, rand('state',RandState) is set to initialize the pseudo-random generator if < 0, rand('state',sum(100\*clock)) is set to give a new set of random values each run if RandState == 0, rand('state',) is not called Default RandState = -1 | |
xEqTol | Tolerance to test if new point x_k already defined as optimum: norm(xk - xOpt(:, i)) <= xEqTol * max(1, norm(xk)) If test fulfilled x_k is assumed to be too close to xOpt(:,i) Default xEqTol = 1E-5 | |
x_L | Lower bounds for each element in x. If generating random points, -inf elements of x L are set to -10000. | |
x_U | Upper bounds for each element in x. If generating random points, inf elements of x U are set to 10000. | |
A | Constraint matrix for linear constraints. | |
b_L | Lower bounds on the linear constraints. | |
b_U | Upper bounds on the linear constraints. | |
c_L | Lower bounds on the general constraints. | |
c_U | Upper bounds on the general constraints. | |
PriLevOpt | 0 = silent. | |
1 = Display one row for each unique local minima found. The minima are sorted, lowest value first (possibly the global minima) | ||
The following 4 information values are displayed: | ||
1. Order \# | ||
2. Function value f(x) at local minima | ||
3. Point x at local minima. Only up to 10 values are displayed | ||
4. Inform value returned from local Solver (normally 0) | ||
2 = One row of output from each multiMin local optimization trial | ||
The following 6 information values are displayed: | ||
1. Step \# | ||
2. Text Old (previously found local minima), FAIL (solver failed to verify local minima) or blank (solver success, new local minima found) | ||
3. Inform value from local solver | ||
4. f(x_0) - function value f(x_0) for initial x_0 | ||
5. f(x) - best f(x) value found in this local search | ||
6. x - point for which best f(x) value was found in this local search. Only up to 10 values are displayed. | ||
4 = tomRun (PrintResult) output from every optimization, print level 2. For constrained problems output of sum(-constr-) and information if optimal point was accepted w.r.t. feasibility. | ||
5 = tomRun (PrintResult) output from every optimization, print level 3. | ||
GO | Structure in Prob, Prob.GO. Fields used: | |
localSolver | The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0). | |
optParam | Defines optimization parameters. Fields used: | |
fGoal | Goal for function value f(x), if empty not used. If fGoal is reached, no further local optimizations are done. | |
eps_f | Relative accuracy for function value, fTol == eps_f. Stop if abs(f-fGoal) <= abs(fGoal) \* fTol , if fGoal = 0. Stop if abs(f-fGoal) <= fTol , if fGoal ==0. | |
bTol | The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0). | |
MIP.IntVars | Structure in Prob, Prob.MIP. If empty, all variables are assumed non-integer (LP problem). If length(I ntV ars) > 1 ==> length(I ntV ars) == length(c) should hold. Then I ntV ars(i) == 1 ==> x(i) integer. I ntV ars(i) == 0 ==> x(i) real. If length(I ntV ars) < n, IntVars is assumed to be a set of indices. It is advised to number the integer values as the first variables, before the continuous. The tree search will then be done more efficiently. | |
varargin | Other parameters directly sent to low level routines. |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
The following fields in Result are changed by multiMin before return: | ||
ExitFlag | = 0 normal output, of if fGoal set and found. | |
= 1 A solution reaching the user defined fGoal was not found | ||
The Solver, SolverAlgorithm and ExitText fields are also reset. | ||
A special field in Result is also returned, Result.multiMin: | ||
xOpt | Prob.N x k matrix with k distinct local optima, the test being norm(xk -xOpt(:, i)) <= xEqT ol * max(1, norm(xk )) that if fulfilled assumes x k to be to closeto xOpt(:,i) | |
fOpt | The k function values in the local optima xOpt(:,i),i=1,...,k. | |
Inform | The Inform value returned by the local solver when finding each of the local optima xOpt(:,i); i=1,...,k. The Inform value can be used to judge the validity of the local minimum reported. | |
localTry | Total number of local searches. | |
Iter | Total number of iterations. | |
FuncEv | Total number of function evaluations. | |
GradEv | Total number of gradient evaluations. | |
HessEv | Total number of Hessian evaluations. | |
ConstrEv | Total number of constraint function evaluations. | |
ExitText | Text string giving ExitFlag and Inform information. |