CGO expDesign

From TomWiki

Jump to: navigation, search

Notice.png

This page is part of the CGO Manual. See CGO Manual.

Contents

Purpose

Computes an initial experimental design for CGO solvers. Note that expDesign should not be called directly, since all inputs are assumed to be correct and no error-checking is done. For direct calls, use expDesignD instead with the same input/output.

Calling syntax

[X, O, F, Fpen, F00, Cc, Cn, nCon, nSample, ExDText, initRS] = expDesign(Percent, nSample, AddMP, nTrial, CLHMethod, SCALE, RandState, PriLev, Prob, varargin)

Description of inputs

NameDescription
PercentType of strategy to get the initial sampled values.
PercentExperimental DesignExD
Corner strategies
900All Corners1
997xL + xU + adjacent corners2
998xU + adjacent corners3
999xL + adjacent corners4
Virtual Corners
mod(Percent,100)% of the box
401-499All Corners17
501-599xL + xU + adjacent corners18
601-699xU + adjacent corners19
701-799xL + adjacent corners20
Deterministic Strategies
0User given initial points5
99Use solver glcDirect6
98Use solver glbDirect6
97Use solver glcSolve6
96Use solver glbSolve6
95Use solver glcFast6
94Use solver glbFast6
Latin Based Sampling
1Maximin LHD 1-norm7
2Maximin LHD 2-norm8
3Maximin LHD Inf-norm9
4Minimal Audze-Eglais10
5Minimax LHD (only 2 dim)11
6Latin Hypercube12
7Orthogonal Samling13
Random Strategies (pp in %)
1ppCircle surrounding14
2ppEllipsoid surrounding15
3ppRectangle surrounding16

Negative values of Percent result in constrained versions of the experimental design methods 7-16. It means that all points sampled are feasible with respect to all given constraints.

For ExD 5,6-12,14-16 user defined points are used.

nSampleNumber of sample points to be used in initial experimental design. nSample is used differently depending on Percent:
(n)Sample:
ExD< 0= 0> 0[ ]
12d
6|n| iterations
7-11d+1d+1max(d + 1,n)(d + 1)(d + 2) / 2
12LATIN(k)
13|n|
14-16d + 1

where LATIN = [21 21 33 41 51 65 65] and k = |nSample|.

Otherwise nSample as input does not matter.

Description of the experimental designs:

ExD 1, All Corners. Initial points is the corner points of the box given by Prob.x_L and Prob.x_U. Generates 2d points, which results in too many points when the dimension is high.

ExD 2, Lower and Upper Corner point + adjacent points. Initial points are 2 * d + 2 corners: the lower left corner xL and its d adjacent corners xL + (xUi - xLi * ei, i = 1, ..., d and the upper right corner xU and its d adjacent corners xU - (xUi - xLi * ei, i = 1, ..., d

ExD 3. Initial points are the upper right corner xU and its d adjacent corners xU - (xUi - xLi * ei , i = 1, ..., d

ExD 4. Initial points are the lower left corner xL and its d adjacent corners xL + (xUi - xLi * ei , i = 1, ..., d

ExD 5. User given initial points, given as a matrix in CGO.X. Each column is one sampled point. If d = length(Prob.x_L), then size(X,1) = d, size(X,2) >= d + 1. CGO.F should be defined as empty, or contain a vector of corresponding f (x) values. Any CGO.F value set as NaN will be computed by solver routine.

ExD 6. Use determinstic global optimization methods to find the initial design. Current methods available (all DIRECT methods), dependent on the value of Percent:

Percentmethod
99glcDirect
98glbDirect
97glcSolve
96glbSolve
95glcFast
94glbFast

If a DIRECT solver already computed the needed points, the warm start file (e.g. glcDirectSave.mat for glcDirect) or the warm start structure in Result."solvername".WarmStartInfo is given in input field CGO.glXFile.

ExD 7-11. Optimal Latin Hypercube Designs (LHD) with respect to different norms. The following norms and designs are available:

PercentLHD
1Maximin 1-Norm
2Maximin 2-Norm
3Maximin Inf-Norm
4Audze-Eglais Norm
5Minimax 2-Norm

All designs taken from: http://www.spacefillingdesigns.nl/

Constrained versions will try bigger and bigger designs up to M = max(10 * d, nTrial) different designs, stopping when it has found nSample feasible points.

ExD 12. Latin hypercube space-filling design. For nSample < 0, k = |nSample| should in principle be the problem dimension. The number of points sampled is:

k 2 3 4 5 6>6
Points213341516565

k : 2 3 4 5 6 > 6

Points : 21 33 41 51 65 65

The call made is:

X = daceInit(abs(nSample),Prob.x_L,Prob.x_U);

Set nSample = [] to get (d+1)*(d+2)/2 sampled points:

d 1 2 3 4 5 6 7 8 910
Points 3 61015212836455566

This is a more efficient number of points to use.

If CGO.X is nonempty, these points are verified as in ExD 5, and treated as already sampled points. Then nSample additional points are sampled, restricted to be close to the given points.

Constrained version of Latin hypercube only keep points that fulfill the linear and nonlinear constraints. The algorithm will try up to M = max(10 * d, nTrial) points, stopping when it has found nSample feasible points (d + 1 points if nSample < 0).

For pure integer programming (IP) problems with 1 or more linear equalities, a special function mipFeasible generates part of the design solving a set of LP problems. At least as many infeasible points as number of linear equalities are sampled, which is necessary.

ExD 13. Orthogonal Sampling, LH with subspace density demands.

ExD 14,15 and 16. Random strategies, the |Percent| value gives the percentage size of an ellipsoid, circle or rectangle around the so far sampled points that new points are not allowed in. Range 1%-50%. Recommended values 10% - 20%.

If CGO.X is nonempty, these points are verified as in ExD 5, and treated as already sampled points. Then nSample additional points are sampled, restricted to be close to the given points.

AddMPIf = 1, add the midpoint as extra point in the corner strategies. Default AddMP=1 if any corner strategy.
nTrialFor CLH, the method generates M = max(10 * d, nTrial) trial points, and evaluates them until nSample feasible points are found.

In the random designs, nTrial is the maximum number of trial points randomly generated for each new point to sample.

CLHMethodDifferent search strategies for finding feasible LH points. First of all, the least infeasible point is added. Then the linear feasible points are considered. If more points are needed still, the nonlinear infeasible points are added.

1 - Take the sampled infeasible points in order.

2 - Take a random sample of the infeasible points.

3 - Use points with lowest constraint error (cErr).

SCALE0 - Original search space.

1 - Transform search space to unit cube.

RandStateIf >= 0, rand('state',RandState) is set to initialize the pseudo-random generator.

If < 0, rand('state', 100*clock) is set to give a new set of random values each run.

If isnan(RandState), the random state is not initialized.


PriLevPrint Level, if > 0 print 1 line information, if >1 more info.
ProbProblem structure
Fields used in Prob:
x_LLower bounds for each element in x.
x_ULower bounds for each element in x.
b_LLower bounds for the linear constraints.
b_UUpper bounds for the linear constraints.
ALinear constraint matrix
c_LLower bounds for the nonlinear constraints.
c_UUpper bounds for the nonlinear constraints.
optParamStructure which defines optimization parameters.
Fields used in Prob.optParam:
bTolLinear constraint tolerance
cTolNonlinear constraint tolerance
CGODefines user given points. Could also contain function values.

If ExD == 12, 14-16 these points are included into the design.

Fields used in Prob.CGO:
XA matrix of initial x values. One column for every x value.

If ExD = 5, size(X,2) >= dim(x)+1 needed.

FA vector of initial f(x) values. If any element is set to NaN it will be computed.
CcOptionally a matrix of costly nonlinear constraint values Cc(x).

Each column Cc(:,i) is the constraint evaluated for x = X(:,i); If nonempty, then size(Cc,2) == size(X,2) must hold. If any element in column i is NaN, the vector Cc_i(x) = Cc(:,i) will be recomputed.

glxFile Name of DIRECT solver warm start file or warm start structure.
varargin Additional parameters that are sent to the costly f(x).
MIPDefines integer optimization parameters.
Fields used in Prob.MIP:
IntVarsIndex vector with indices for integer variables.


Description of outputs

NameDescription
XMatrix with sampled points (in unit space if SCALE == 1).
OMatrix with sampled points (in original space).
FVector with function values (penalty added for costly Cc(x)).
FpenVector with function values + additional penalty if infeasible using the linear constraints and noncostly nonlinear c(x).
F00Vector of pure function values, before penalties.
CcMatrix with costly constraint values, Cc(x)
nConNumber of noncostly constraint evaluations calling Cn(x).
nSampleCorrected value of nSample.
ExDText String with experimental design information.
initRSState of random number generator immidiately after initialization. If no initialization is done, its current value is saved instead.
Personal tools