PARALLEL GLOBAL OPTIMIZATION ALGORITHMS

 
189 
This paper deals with the following well known global optimization 
problem of finding the global minimum of a function 
Φ(z) of N variables 
over a hyperinterval D: 
 
 
Φ(z*) = min{Φ(z) : z∈D}, (1) 
 
 
D = {z 
∈R
N
 : a
j
 
≤ z
j
 
≤ b
j
, 1< j <N], 
(2)  
 
where 
Φ(z) is multiextremal. If Φ(z) is continuous then, for the function 
 
 
φ(x) = Φ(z(x)),  x∈[a,b], (3) 
 
where  z(x)  is the continuous Peano-type mapping of closed interval [a, b] 
onto the hyperinterval D, we have 
 
 min{
φ(x) : x∈[a,b]} = min{Φ(z) : z∈D }. 
 
Therefore, solving the multidimensional problem (1), (2) is reduced to 
solving the one-dimensional problem 
 
 
φ(x*) = min{φ(x) : x∈[a,b]}, (4) 
 
In addition, if 
Φ(z) is Lipschitzean with a constant K > 0 then φ(x) satis-
fies the Hölder condition 
 
 
|
φ(x′) – φ(x′′)| ≤ H |x′ – x′′|
1/N
,  x′, x′′
∈[a,b], (5) 
 
with a constant H 
≥ 0 (Hölder constant). For N = 1 we will also consider the 
problem (4) where the first derivative 
φ(x′) satisfies the Lipschitz condition 
 
 
|
φ′(x′) – φ′(x′′)| ≤ L |x′ – x′′|,  x′, x′′∈[a,b], (6) 
 
For solving the problems (4)–(5), (4)–(6) it is proposed to use parallel 
characteristical algorithms generalizing sequential characteristical algo-
rithms. A global optimization algorithm is called a parallel characteristical 
algorithm if trial points (i.e. that ones where we evaluate 
φ(x) and for the 
problem (4)–(6) also 
φ′(x)) are chosen according to the following rules. 
Trials of the first n 
≥ 1 iterations are performed in arbitrary 
 
 
K = k(n) = p(l) + p(2) + . . . + p(n) 
 
points of the interval [a, b], where p(i), i 
≥ 1, denotes the number of trials of 
the  i-th iteration. Trial points corresponding to any next Q-th iteration, 

жүктеу/скачать 1,64 Mb.

Достарыңызбен бөлісу: