An Extension of the Nested Partitions Method
EBERT BREA
backtracking
operation

is

carried

out

by

the

algorithm
as
a

result

that

the

MINP

method

identified

the

best
function
value

comes

from

the

kth

surrounding

region
at
the

same

kth

counter

iteration,

therefore,

a

geometric
distribution
is

taken

place

in

the

estimation

of

the

proba-
bility
distribution

of

the

MINPMC

states.
Proposition 5
Assume,

without

loss

of

generality
(w.l.o.g.),
Condition

1

and

3

are

met,

and

let

Ni =

ν(> 0)
for
all

i ∈−

{}Mℓ=1σ

be

the

number

of

random

samplings
that
are

taken

from

each

ith

subregion

σi(k)

at

the
κth
iteration,

and

let

N(> 0)

be

the

number

of

random
trial
points

that

are

taken

from

the

surrounding

region
S(σ(k)).
Then
(
p
(k,k+1)
k
=
1,
if

k =

0;
ϕ Mσ γk (1γk)Mσ1,
if

k ∈−N+,
(22)
where:
ϕ =
Mσν
Mσν +N
;
(23a)
γk =
Qn
=1

u()l()
2k+1

+
Qm
=1
l ¯
u()¯l()
2k+1
m
Qn
=1

u()l()
2k

+
Qm
=1
l
u¯()¯l()
2k
m,
∀−

k ∈−N+.
(23b)
Proof.
Let

F−

denote

the

event

that

the

MINP

method
has
identified

that

the

best

value

of

f(z)

has

come

from
the
current

subregion

σ(k),

let

Σi

denote

the

event

that
the
best

value

of

f(z)

has

come

from

any

ith

subregion
σi(k)
at

the

kth

iteration,

then,
p
(k,k+1)
k
=

Pr{Σi,F},

k ∈−N+.
(24)
Using
conditional

probability,

we

have
p
(k,k+1)
k
=

Pr{Σi |−F}Pr{F},

k ∈−N+.
(25)
Under
Condition

3,

we

can

say

that

letting

Pr{F}−=

ϕ
ϕ =
Mσν
Mσν +N
.
(26)
On
the

other

hand,

due

to

Conditions

2

and

3,

and
Sampling
procedure

in

Figures

20

and

21,

and

since
sampling
trial

points

are

taken

from

uniform

random

dis-
tributions
for

each

subregion

and

the

current

surrounding
region
S(σ(k)),

we

can

then

say

that

(22)

is

easily
got
from

a

binomial

distribution

with

Mσ

subregions,
because
a

set

{σi(k)}Mi=1σ

is

generated

by

Partition

pro-
cedure
in

Figure

18

at

each

kth

iteration,

and

parameter
γk
expressed

by
γk =
V[σ˜i(k)]
Vσ(k)]
=
Qn
=1

u()l()
2k+1

+
Qm
=1
l
u¯()¯l()
2k+1
m
Qn
=1

u()l()
2k

+
Qm
=1
l ¯
u()¯l()
2k
m,
(27)
for
all

k ∈−N+,

because

V[σ˜1(k)]

=,···−

,=

V[σM˜

σ(k)],
and
hence

γk

=

V[σ˜i(k)]/Vσ(k)]

for

any

i


{1,...,Mσ},
what

yields
Pr{Σi |−F}−=

Mσ
1
!
γk(1γk)Mσ1,
k ∈−N+.

(28)
By
substituting

(26)

and

(28)

in

(25),

we

obtain
p
(k,k+1)
k
=
ϕMσγk (1γk)Mσ1,

k ∈−N+.

(29)
Besides,
the

event

that

the

MINPMC

visits

the

{D =

1}
state
after

it

has

been

at

the

{D =

0}−

state

always

oc-
curs,
leaving

no

doubt,

because

S(σ(0))

=

,

whereby
p
(0,1)
0
=
1.
Therefore,
we

shall

hereafter

denote,

without

causing

a
loss
of

its

meaning,

Pr{D(k)

=

d(k)}˜

as

Pr{D(k)

=
k}−=
π(k).
We
shall

now

pay

especial

attention

to

the

probability
distribution
estimating

of

the

MINPMC

states,

which
may
be

expressed

by

a

(k+1)ˆ

dimensional

vector

π =
(π(0),...,π(kˆ))t,
which

depicts
π(k)
=
Xkˆ
=0
π()
δ[k ],

k ∈−Z,
(30)
where
δ[k]

:

Z →−

{0,1}−

is

here

called

discrete

impulse
function,
which

is

a

special

case

of

a

2-dimensional
Kronecker
delta

function

δij,

and

a

generalized

-shifted
mathematical
expression

of

δ[k ]

is

given

by
δ[k ]
=

1,
if

k =

;
0,
another

case

of

k ∈−Z.
(31)
Note
that

we

have

used

in

(30)

π(·)

for

denoting

the
probability
distribution

function,

and

this

is

not

to

be
confused
with

the

superscript

argument

notation

π(·)
conventionally
used

for

denoting

the

component

of

a
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
127