An Extension of the Nested Partitions Method
EBERT BREA
by
Brea

[10 ],

and

is

thought

that

by

this

via,

it

could

be
improved
its

performance.
The
rest

of

the

article

is

organized

as

follows.

Next
section
introduces

basic

concepts

and

main

idea

of
the
NP

method

[18, 20] through

a

very

simple

didactic
example
in

R2.

Section

iii

presents

the

theoretical

main
results
of

the

MINP

method,

which

are

based

on

the

NP
method
approach.

A

pseudocode

of

the

MINP

method
is
proposed

in

Section

iv,

whereby

its

procedures

and
functions
have

been

included

in

appendices.

Section
v
addresses

the

main

properties

of

the

MINP

method,
which
has

been

studied

from

a

Markov

chain

viewpoint.
Section
vi

presents

a

software,

which

operates

the

MINP
method
for

taking

r

independent

samplings

of

perfor-
mance
measurements

of

the

MINP

method.

Section
vii
shows

a

set

of

numerical

experiments

for

statistically
analyzing
the

performance

of

the

MINP

method.

Finally,
Section
viii

discusses

advantages

and

disadvantages

of
the
MINP

method,

and

future

research

for

improving
performance
of

the

MINP

method.

A

list

of

mixed

integer
nonlinear
problems

for

testing

the

MINP

method

has
been
included

in

Appendix

A.
ii.
THE NESTED PARTITIONS METHOD
With
the

aim

of

giving

a

didactic

explanation

of

the

NP
method
principles,

consider

the

following

two

dimen-
sional
real

optimization

example.
Example 1
minimize
xR2
f(x)
(2a)
subject
to
(1,1)t −x −
(9,9)t,
(2b)
where
f(x)

:

R2

→−R

is

a

nonlinear

objective

function.
The
feasible

region

given

by

(2b)

is

indubitably

depicted
by
a

square

region

with

both

width

and

height

equal

to

8
units,
such

as

is

shown

in

Figure

1

in

green

color.
Note
that

this

region

is

considered

the

initial

promising
region
σ(0),

because

the

entire

feasible

region

at

least
contains,
and

without

any

discussion,

a

global

solution
of
the

problem.
σ(0)
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
x(1)
x(2)
Figure 1.
Entire feasible region, promising region σ(0)
As
can

be

seen

from

Figure

2,

the

promising

region
σ(0)
is

partitioned

or

divided

into

4

subregions,

yielding
the
set

of

subregions

{σj(0)}4j=1,

and

at

this

iteration
k =
0,

there

exists

no

surrounding

region

to

σ(0),

i.e.,
S(σ(0))
=

.
σ1(0)
σ2(0)
σ3(0)
σ4(0)
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
x(1)
x(2)
Figure 2.
Partitions of promising region σ(0)
According
to

the

NP

method

[18],

the

algorithm

takes
random
trial

points

from

each

jth

subregion,

denoted

by
σj(0),
for

estimating

the

next

promising

region

by

finding
an
index

ˆj,

which

indicates

where

the

best

function

value
has
come

from,

as

it

can

then

be

seen

from

Figure

3

by
a
red

cross

on

σ3(0),

i.e.,

ˆj =

3,

and

hence,

the

next
promising
region

will

be

given

by

the

subregion

σ3(0).
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
118