An Extension of the Nested Partitions Method
EBERT BREA
c.
ON

THE

STOPPING

RULE
As
was

mentioned

in

the

introduction,

one

of

the

con-
tributions
of

this

research

has

been

the

inclusion

of

a
new
stopping

rule,

which

is

based

on

the

depth

vector
d(k)
of

the

current

promising

region,

without

considering
any
objective

function

value,

because

our

approach

is
only
based

on

partitioning

scheme,

leaving

for

another
research
the

study

of

stopping

rule

based

on

statistical
viewpoints,
such

as

statistical

considerations

on

the
feasible
global

minimum

function

value

applying

non-
standard
parametric

inference.

A

good

approach

on

non-
standard
parametric

inference

is

introduced

by

Cheng
[23]
,
which

could

be

taken

into

account

for

using

it
together
with

the

concepts

of

order

statistics

presented
by
De

Haan

[24].
Taking
into

account

the

main

pseudocode

of

the

MINP
method
in

Figure

8

on

page

124,

we

can

notice

that

when
d(k +1)
−

d(k)

holds,

and

the

ˆi ∈−

{}Mℓ=1σ

the

algorithm
carries
out

a

new

partitioning

on

the

new

promising
region,
otherwise,

as

a

result

of

that

ˆi =

Mσ +

1,

the
algorithm
backtracks

to

the

entire

feasible

region,

and

it
restarts
the

iteration

counter

by

letting

k be

equal

to

0.
Note
that

the

surrounding

to

the

promising

region

σ(k)
has
been

here

denoted

by

σMσ+1(k),

i.e.,

S(σ(k))

=
σMσ+1(k).
Since
the

MINP

method

estimates

the

current

promising
region
at

each

kth,

the

current

depth

mixed

integer
vector
d(k)

can

be

then

easily

calculated,

for

being
afterward
tested

at

the

end

of

each

kth

iteration,

and

so
verifying
whether

ε −

d(k)

or

not,

whereby

in

the

case
that
ε −

d(k)

the

MINP

method

will

go

to

next

iteration,
otherwise,
the

MINP

method

will

stop.
We
shall

now

focus

on

calculating

the

maximum

num-
ber
of

iteration,

denoted

by

k,ˆ

that

the

MINP

method
needs
for

stopping

the

algorithm,

considering

that

any
backtracking
operation

has

not

been

carried

out

during
the
identification

of

a

global

solution

to

Problem

1.
Due
to

the

fact

that

we

have

still

no

stopping

rule

for

the
MINP
method,

it

is

reasonable

to

enunciate

the

following
condition.
Condition 1
Suppose

that

is

executed

the

iterative

loop
of
the

MINP

method,

that

will

afterward

be

shown

in

Fig-
ure
8,

without

considering

any

stopping

rule

for

globally
solving
Problem

1.
Lemma 1
Assume

Condition

1

holds.

Then

the

ith

real
component
of

the

mixed

integer

depth

d(k)

is

given

by
d(i)(k)
=
u(i)
l(i)
2k
,
i ∈−

{}nℓ=1,k ∈−N,

(7)
where
l,u ∈−Rn ×−Zm

respectively

are

the

lower

and
upper
bound

constrains

given

by

(1b).
Proof.
Due

to

the

fact

that

the

MINP

method

partitions
each
ith

component

of

the

promising

region

into

two
subsets,
the

ith

real

component

is

successively

divided
by
2

at

each

kth,

resulting

the

geometric

series

given
by
(7),

for

each

ith

real

component

of

the

mixed

integer
depth
vector.
Lemma 2
Assume

Condition

1

holds

and

the

ex-
pected
mixed

integer

depth

vector

ε

is

fixed

to
(ǫ,...,ǫ;0,...,0)t.
The

MINP

method

hence

stops

when
max
i∈{1,...,n}
(u(i)
l(i))
2k
< ǫ
(8)
is
met.
Proof. During
the

execution

of

the

algorithm,

successive
divisions
by

two

are

carried

out,

both

to

the

real

and
integer
components,

what

allows

us

to

assert

that

any
integer
component

d¯(i)(k)

for

all

i ∈−

{}mℓ=n+1

of

the
mixed
integer

depth

vector

becomes

0,

faster

than

any
real
component

d(i)(k)

for

all

i ∈−

{}nℓ=1

of

the

mixed
integer
depth

vector.

Besides,

all

integer

components
of
the

mixed

integer

vector

d¯(i)(k)

for

all

i ∈−

{}mℓ=n+1
become
0

in

a

finite

number

of

iteration

k,

whereas

that
the
real

components

d(i)(k)

for

all

i ∈−

{}nℓ=1

approach
to
0

when

k →∞.

Since

Lemma

1

holds,

the

depth
vector
d(k)

will

therefore

be

precede

to

the

expected
mixed
integer

depth

vector

ε,

when

(8)

is

met.
In
what

follows,

we

provide

evidence

that

the

proposed
stopping
rule

successfully

works,

avoiding

an

over

itera-
tions
of

the

algorithm,

when

the

stopping

rule

had

been
met,
as

a

result

that

exists

a

positive

probability

that

is
reached.
Theorem 1
Let

kˆ

=

k⌉−

be

the

closest

integer

greater
than
or

equal

to

k,

assume

Condition

1

holds,

and
the
expected

mixed

integer

vector

ε has

been

fixed

to
(ǫ,...,ǫ;
0,...,0)t.

Then

minimum

number

of

required
iterations
by

the

MINP

method

for

being

stopped,

i.e.,
when
d(k

≺−

ε has

just

been

met,

it

is

given

by
kˆ
=


log2



max
i∈{1,...,n}
(u(i)
l(i))
ǫ





.
(9)
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
122