Geology Reference
In-Depth Information
with Common Random Numbers (CRN) will be
employed in this study and is briefly reviewed next.
where Ω k is the sample set used at iteration k and
k
n
∈ ℜ ϕ is a vector of mutually independent
random variables that defines the random direction
of simultaneous perturbation for φ k and that satis-
fies the statistical properties given in (Spall, 2003).
A symmetric Bernoulli ±1 distribution is typi-
cally chosen for the components of Δ k . The selec-
tion for the sequences { c k } and { α k } is discussed
in detail in (Kleinmann et al., 1999). A choice that
guarantees asymptotic convergence to ϕ * is
α k = α /( k + w ) β and c k = c 1 / k ζ , where 4ζ - β > 0,
2β - 2ζ > 1, with w, ζ > 0 and 0
Simultaneous Perturbation
Stochastic Approximation
Simultaneous-perturbation stochastic approxi-
mation (SPSA) (Kleinmann et al., 1999; Spall,
2003) is an efficient stochastic search method.
It is based on the observation that one properly
chosen simultaneous random perturbation in all
components of φ provides as much information
for optimization purposes in the long run as a full
set of one at a time changes of each component.
Thus, it uses only two evaluations of the objective
function, in a direction randomly chosen at each
iteration, to form an approximation to the gradi-
ent vector. It also uses the notion of stochastic
approximation (Kushner & Yin, 2003) which
can significantly improve the computational ef-
ficiency of stochastic search applications (Spall,
2003). The latter approximation is performed by
establishing (through proper recursive formulas)
an equivalent averaging across the iterations of the
optimization algorithm, instead of getting higher
accuracy estimates for the objective function at
each iteration, that is averaging over one single
iteration.
The implementation of SPSA takes the itera-
tive form:
< ≤ β . This
selection leads to a rate of convergence that as-
ymptotically approaches k β /2 when CRN is used
(Kleinmann et al., 1999). The asymptotically
optimal choice for β is, thus, 1. In applications
where efficiency using a small number of itera-
tions is sought after, use of smaller values for β
are suggested in (Spall, 2003). For complex design
optimizations, where the computational cost for
each iteration of the algorithm is high, the latter
suggestion should be adopted. Note that the same
set of random numbers is selected for the two
estimates of the objective function at each itera-
tion used to calculate the gradient in Equation 26.
This reduces the variance of the difference of
these estimates thus creating a consistent estima-
tion error (Glasserman & Yao, 1992; Taflanidis
& Beck, 2008) and improving the efficiency of
the estimate in Equation 26 (reduces relative
importance of estimation error). Across the itera-
tions of the optimization algorithm, though, this
sample set is not the same; thus there is no de-
pendence of the optimal solution on it (i.e. the
approach here does not correspond to an exterior
sampling technique).
Regarding the rest of the parameters for the
sequences {c k } and {α k }: w is typically set to 10%
of the number of iterations selected for the algo-
rithm and the initial step c 1 is chosen “close” to
the standard deviation of the prediction error for
the stochastic estimate in Equation 23 . The value
of α can be determined based on the estimate of
1
(
)
α g ,
(25)
ϕ
+ =
ϕ
ϕ
k
1
k
k k
k
k
where φ 1 Φ is the chosen point to initiate the
algorithm and the j th component for the Common
Random Number (CRN) simultaneous perturba-
tion approximation to the gradient vector in the
k th iteration, g k ( φ k , Ω k ), is given by:
(
)
(
)
ˆ
ˆ
C
ϕ
+
c
∆ Ω
,
C
ϕ
c
∆ Ω
,
k
k
k
k
k
k
k
k
g
=
k j
,
2 κ
c
k
,
j
(26)
Search WWH ::




Custom Search