MultiMin

From TomWiki

Jump to: navigation, search

Contents

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



\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} \\
&       &       & {x_i \in \mathbb{N} \; \forall i \in I} \\
\end{array}

where x,x_{L},x_{U}\in \mathbb{R}^{n} , c(x),c_{L},c_{U}\in \mathbb{R}^{m_{1}} , A\in \mathbb{R}^{m_{2}\times n} and b_{L},b_{U}\in \mathbb{R}^{m_{2}}.

The variables x \in I , the index subset of 1,...,n 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

ProbProblem description structure. The following fields are used:
xInitEither, 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.
fCutIf initial f(x_0) > fCut, no local optimization is done.
WarmStartIf 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.

RandStateIf 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
xEqTolTolerance 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_LLower bounds for each element in x. If generating random points, -inf elements of x L are set to -10000.
x_UUpper bounds for each element in x. If generating random points, inf elements of x U are set to 10000.
AConstraint matrix for linear constraints.
b_LLower bounds on the linear constraints.
b_UUpper bounds on the linear constraints.
c_LLower bounds on the general constraints.
c_UUpper bounds on the general constraints.
PriLevOpt0 = 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.

GOStructure in Prob, Prob.GO. Fields used:
localSolverThe local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0).
optParamDefines optimization parameters. Fields used:
fGoalGoal for function value f(x), if empty not used. If fGoal is reached, no further local optimizations are done.
eps_fRelative 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.
bTolThe local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0).
MIP.IntVarsStructure 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.
vararginOther parameters directly sent to low level routines.

Outputs

ResultStructure 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:
xOptProb.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)
fOptThe k function values in the local optima xOpt(:,i),i=1,...,k.
InformThe 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.
localTryTotal number of local searches.
IterTotal number of iterations.
FuncEvTotal number of function evaluations.
GradEvTotal number of gradient evaluations.
HessEvTotal number of Hessian evaluations.
ConstrEvTotal number of constraint function evaluations.
ExitTextText string giving ExitFlag and Inform information.
Retrieved from "http://tomwiki.com/MultiMin"
Personal tools