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
bas
ic
concepts
and
main
idea
of
the
NP
method
[18
, 20]
through
a
very
simple
didactic
example
in
R
2
.
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
x
∈
R
2
f
(
x
)
(2a)
subject
to
(1
,
1)
t
−
x
−
(9
,
9)
t
,
(2b)
where
f
(
x
)
:
R
2
→−
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)
}
4
j
=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
j
th
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É
N
o
25.1
Semestre
octubre-febrero
2022
ISSN
electrónico:
2790-5195
ISSN:
1316-3930
118