MultiMin

From TomWiki
Revision as of 10:16, 9 March 2015 by Bjorn (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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


where , , and .

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)

Inputs

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.

3 = tomRun (PrintResult) output from every optimization, print level 1.

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.

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)) <= xEqTol * 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.