TELK
OMNIKA,
V
ol.16,
No
.6,
December
2018,
pp
.
2782–2790
ISSN:
1693-6930,
accredited
First
Gr
ade
b
y
K
emenr
istekdikti,
Decree
No:
21/E/KPT/2018
DOI:
10.12928/TELK
OMNIKA.v16i6.11584
2782
Using
Alpha-cuts
and
Constraint
Exploration
Appr
oac
h
on
Quadratic
Pr
ogramming
Pr
ob
lem
Y
osza
Dasril
*1
,
Zahriladha
Zakaria
2
,
and
Ismail
Bin
Mohd
3
1,2
Center
f
or
T
elecomm
unication
Research
&
Inno
v
ation
,
F
aculty
of
Electronics
an
d
Computer
Engineer
ing,
Univ
ersiti
T
eknikal
Mala
ysia
Melaka
(UT
eM),
Hang
T
uah
J
a
y
a,
Mala
ysia
1,3
Center
f
or
Mathematical
Research
(INSPEM)
,
Univ
ersiti
Putr
a
Mala
ysia
(UPM),
Serdang,
M
ala
ysia
*
Corresponding
author
,
e-mail:
y
osza@utem.edu.m
y
1
,
zahr
iladha@utem.edu.m
y
2
,
ismail
a
y
ah
ir
ma@y
ahoo
.com
3
Abstract
In
this
paper
,
w
e
propose
a
computational
procedure
to
find
the
optimal
solution
of
quadr
atic
pro-
g
r
amming
prob
lems
b
y
using
fuzzy
-cuts
and
constr
aint
e
xplor
ation
approach.
W
e
solv
e
the
prob
lems
in
the
or
iginal
f
or
m
without
using
an
y
additional
inf
or
mation
such
as
Lag
r
ange’
s
m
ultiplier
,
slac
k,
sur
plus
and
ar
tificial
v
ar
iab
le
.
In
order
to
find
the
optimal
solution,
w
e
divide
the
calculation
in
tw
o
stages
.
In
the
first
stage
,
w
e
deter
mine
the
unconstr
ained
minimization
of
the
quadr
atic
prog
r
amming
prob
lem
(QPP)
and
chec
k
its
f
easibility
.
By
unconstr
ained
minimization
w
e
identify
the
violated
constr
aints
and
f
ocus
our
searching
in
these
constr
aints
.
In
the
second
stage
,
w
e
e
xplored
the
f
easib
le
region
along
side
the
violated
constr
aints
until
the
optimal
point
is
achie
v
ed.
A
n
umer
ical
e
xample
is
included
in
this
paper
to
illustr
ate
the
capability
of
-cuts
and
constr
aint
e
xplor
ation
to
find
the
optimal
solution
of
QPP
.
K
e
yw
or
ds:
fuzzy
set,
tr
iangular
fuzzy
n
umber
,
f
easib
le
set,
quadr
atic
prog
r
amming,
alpha-cuts
,
positiv
e
definite
.
Cop
yright
c
2018
Univer
sitas
Ahmad
Dahlan.
All
rights
reser
ved.
1.
Intr
oduction
The
theor
y
of
quadr
atic
prog
r
amming
prob
lem
(QPP)
deals
with
pro
b
lems
of
constr
ained
minimization,
where
the
constr
aint
functions
are
linear
and
the
objectiv
e
is
a
positiv
e
definite
quadr
atic
function
[1,
2].
Man
y
engineer
ing
prob
lems
can
be
represented
as
QPP
such
as
in
sensor
netw
or
k
localization,
pr
inciple
component
analysis
and
optimal
po
w
er
flo
w
[3]
and
design
of
digital
filters
.
The
design
aspect
of
digital
filters
that
can
be
handled
b
y
quadr
atic
prog
r
amming
prob
lem
efficiently
is
to
choose
the
par
ameters
of
the
filter
to
achie
v
e
a
specified
type
of
frequency
response
[4].
Although
there
is
a
natur
al
tr
ansition
from
the
theor
y
of
linear
prog
r
amming
to
the
theor
y
of
nonlinear
prog
r
amming
prob
lem,
there
are
some
impor
tant
diff
erences
betw
een
their
optimal
solution.
If
the
optim
um
solution
of
quadr
atic
prog
r
amming
prob
lem
e
xists
then
it
is
either
an
inter
ior
point
or
boundar
y
point
which
is
not
necessar
ily
an
e
xtreme
point
of
the
f
easib
le
region.
The
QPP
model
in
v
olv
es
a
lot
of
par
ameters
whose
v
alues
are
assigned
b
y
e
xper
ts
.
Ho
w
e
v
er
,
both
e
xper
ts
and
decision
mak
ers
frequently
do
not
precisely
kno
w
the
v
alues
of
those
par
ame-
ters
.
Theref
ore
,
it
is
useful
to
consider
the
kno
wledge
of
e
xper
ts
about
the
par
ameters
as
fuzzy
data
[5].
Bellman
and
Zadeh
[6]
proposed
the
concept
of
decision
making
in
fuzzy
en
vironment
while
T
anaka
et
al,
[7]
adopted
this
c
o
ncept
f
or
solving
mathematical
prog
r
amming
prob
lems
.
Zimmer
man
[8]
proposed
the
first
f
or
m
ulation
of
fuzzy
linear
prog
r
amming.
Ammar
and
Khali-
f
ah
[9]
introduced
the
f
or
m
ulation
of
fuzzy
por
tf
olio
optimization
prob
lem
as
a
con
v
e
x
quadr
atic
prog
r
amming
approach
and
ga
v
e
an
acceptab
le
solution
to
such
prob
lem.
The
constr
aint
e
xplo-
r
ation
has
been
proposed
b
y
[10]
where
the
method
is
based
on
the
violated
constr
aints
b
y
the
unconstr
ained
minim
um
of
the
objectiv
e
function
of
QPP
f
or
e
xplor
ing,
locating
and
computing
the
optimal
solution
of
the
QPP
.
In
this
paper
,
w
e
e
xtend
the
concept
o
f
constr
aint
e
xplor
ation
method
to
solv
e
the
QPP
in
fuzzy
en
vironment.
By
using
this
appro
aches
the
fuzzy
optimal
so-
lution
of
the
QPP
occurr
ing
in
the
real
lif
e
situations
can
be
obtained.
This
paper
is
organiz
ed
Receiv
ed
J
une
7,
2018;
Re
vised
October
8,
2018;
Accepted
No
v
ember
12,
2018
Evaluation Warning : The document was created with Spire.PDF for Python.
2783
ISSN:
1693-6930
as
f
ollo
ws
.
In
Section
2,
some
basic
notations
,
definitions
and
ar
ithmetic
oper
ations
betw
een
tw
o
tr
iangular
fuzzy
n
umbers
are
re
vie
w
ed.
In
Section
3,
f
or
m
ulation
of
the
QPP
and
deter
mination
of
the
unconstr
ained
optimal
solution
in
fuzzy
en
vironment
are
discussed.
In
Section
4,
a
method
to
deter
mine
the
optimal
solution
on
the
boundar
y
of
violated
constr
aints
is
descr
ibed.
In
Section
5,
a
ne
w
approaches
or
algor
ithm
f
or
solving
the
QPP
is
proposed.
T
o
illustr
ate
the
capability
of
the
proposed
method,
n
umer
ical
e
xamples
are
solv
ed
in
Section
6.
The
conclusion
ends
this
paper
.
2.
Preliminaries
In
this
section,
some
necessar
y
notations
and
ar
ithmetic
oper
ations
of
fuzzy
set
theor
y
are
re
vie
w
ed.
2.1.
Basic
Definition
Definition
1
[11]
The
char
acter
istic
function
A
of
a
cr
isp
set
A
X
assigns
a
v
a
lue
either
0
or
1
to
each
member
in
X
.
This
funct
ion
can
be
gener
aliz
ed
to
a
function
A
such
that
the
v
alue
assigned
to
the
e
lement
of
the
univ
ersal
set
X
f
alls
within
a
specified
r
ange
i.e
.
A
:
X
!
[0
;
1]
.
The
assigned
v
alue
indicates
the
membership
g
r
ade
of
the
element
in
the
set
A
.
The
function
A
is
called
the
membership
function
and
the
set
A
=
f
(
x;
A
(
x
))
:
x
2
X
g
defined
b
y
A
f
or
each
x
2
X
is
called
a
fuzzy
set.
Definition
2
[12]
A
fuzzy
n
umber
A
=
(
a;
b;
c
)
is
called
a
tr
iangular
fuzzy
n
umber
if
its
membership
function
is
giv
en
b
y
A
(
x
)
=
8
>
<
>
:
(
x
a
)
(
b
a
)
;
a
x
b
(
x
c
)
(
b
c
)
;
b
x
c
0
;
otherwise
;
and
alpha-cuts
corresponding
to
A
=
(
a;
b;
c
)
can
be
wr
itten
as
A
[
]
=
[
a
1
(
)
;
a
2
(
)]
;
2
[0
;
1]
where
a
1
(
)
=
[(
b
a
)
+
a
)]
and
a
2
(
)
=
[
(
c
b
)
+
c
]
.
Definition
3
[12]
A
tr
iangular
fuzzy
n
umber
(
a;
b;
c
)
is
said
to
be
non-negativ
e
fuzzy
n
umber
if
and
only
if
a
>
0
.
Definition
4
Let
A
=
(
a
1
;
b
1
;
c
1
)
and
B
=
(
a
2
;
b
2
;
c
2
)
be
tw
o
tr
iangular
fuzzy
n
umbers
,
then
(a)
(
A
)
(
B
)
iff
a
1
a
2
;
b
1
a
1
b
2
a
2
;
c
1
b
1
c
2
b
2
.
(b)
(
A
)
(
B
)
iff
a
1
a
2
;
b
1
a
1
b
2
a
2
;
c
1
b
1
c
2
b
2
.
(c)
(
A
)
=
(
B
)
iff
a
1
=
a
2
;
b
1
a
1
=
b
2
a
2
;
c
1
b
1
=
c
2
b
2
.
2.2.
Fuzzy
Arithmetic
The
f
ollo
wing
concepts
and
results
ar
e
introduced
in
[11,
13].
Let
A
[
]
=
[
a
;
a
+
]
and
B
[
]
=
[
b
;
b
+
]
be
tw
o
closed,
bounded,
inter
v
a
ls
of
real
n
umbers
.
If
denotes
addition,
sub-
str
action,
m
ultiplication,
or
division,
then
[
a
;
a
+
]
[
b
;
b
+
]
=
[
;
]
where
[
;
]
=
f
a
b
j
a
a
a
+
;
b
b
b
+
g
:
If
is
division,
w
e
m
ust
assume
that
z
ero
does
not
belong
to
[
b
;
b
+
]
.
W
e
ma
y
simplify
the
abo
v
e
equation
as
f
ollo
ws:
1.
Addition
[
a
;
a
+
]
[
b
;
b
+
]
=
[
a
+
b
;
a
+
+
b
+
]
.
TELK
OMNIKA
V
ol.
16,
No
.
6,
December
2018
:
2782
2790
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
2784
2.
Substr
action
[
a
;
a
+
]
[
b
;
b
+
]
=
[
a
b
+
;
a
+
b
]
.
3.
Division
[
a
;
a
+
]
[
b
;
b
+
]
=
[
a
;
a
+
]
[
1
b
+
;
1
b
]
.
4.
Multiplication
[
a
;
a
+
]
[
b
;
b
+
]
=
[
;
]
where
=
min
f
a
b
;
a
b
+
;
a
+
b
;
a
+
b
+
g
and
=
max
f
a
b
;
a
b
+
;
a
+
b
;
a
+
b
+
g
.
Remark
1
Multiplication
ma
y
be
fur
ther
simplified
as
f
ollo
ws
.
F
or
A
=
(
a;
b;
c
)
and
B
=
(
x;
y
;
z
)
be
a
non-negativ
e
tr
iangular
fuzzy
n
umbers
,
then
A
B
=
8
<
:
(
ax;
by
;
cz
)
;
a
0
(
az
;
by
;
cz
)
;
a
<
0
;
c
0
(
az
;
by
;
cx
)
;
c
<
0
Lemma
1
[14].
Suppose
that
f
(
x
)
;
x
2
R
n
is
an
ordinar
y
real
v
alued
function,
and
A
be
the
set
of
all
closed
and
bounded
fuzzy
n
umbers
.
If
r
=
(
r
1
;
r
2
;
r
3
)
2
A
then
r
satisfied:
1.
f
x
j
x
2
<
;
r
(
x
)
=
1
g
6
=
;
2.
if
w
e
define
f
(
r
)
,
S
2
[0
;
1]
f
(
r
)
then
f
(
r
1
)
=
f
(
r
)
=
h
^
x
2
r
f
(
x
)
;
_
x
2
r
f
(
x
)
i
3.
f
(
r
)
2
A
.
3.
Pr
ob
lem
Form
ulation
A
quadr
atic
function
on
R
n
to
be
considered
in
this
paper
,
which
is
defined
b
y
f
(
x
1
;
;
x
n
)
=
1
2
n
X
j
=1
n
X
i
=1
x
i
d
ij
x
j
+
n
X
j
=1
c
j
x
j
(1)
where
q
;
c
i
and
d
ij
;
(
i;
j
=
1
;
:::;
n
)
are
constant
scalar
quantities
.
Equation
(1)
can
be
wr
itten
in
v
ector-matr
ix
notation
as
f
(
x
)
=
1
2
x
T
D
x
+
c
T
x
(2)
in
which
D
=
(
d
ij
)
n
n
;
c
=
(
c
1
;
:::;
c
n
)
T
,
and
x
=
(
x
1
;
:::;
x
n
)
T
.
Without
loss
of
gener
ality
,
w
e
consider
D
to
be
a
positiv
e
definite
symmetr
ic
matr
ix
and
if
D
is
a
positiv
e
definite
,
then
f
(
x
)
,
which
is
giv
en
b
y
(2),
can
be
called
a
positiv
e
definite
quadr
atic
function.
The
set
all
f
easib
le
solutions
,
so-called
the
f
easib
le
region,
which
will
be
considered
in
this
paper
,
is
a
closed
set
defined
b
y
F
=
f
x
j
x
2
(
R
)
n
;
Ax
b;
x
0
g
(3)
where
A
an
(
mxn
)
matr
ix
and
b
is
a
v
ector
in
R
m
.
Since
f
(
x
)
giv
en
b
y
(1)
is
positiv
e
definite
quadr
atic
function,
then
f
(
x
)
is
str
ictly
con
v
e
x
in
x
,
theref
ore
f
(
x
)
attains
a
unique
minim
um
at
x
(0)
=
D
1
c
(4)
Using
Alpha-cuts
and
Constr
aint
Explor
ation
Approach
on
Quadr
atic
Prog
r
amming...
(Y
.
Dasr
il)
Evaluation Warning : The document was created with Spire.PDF for Python.
2785
ISSN:
1693-6930
which
is
called
unconstr
ained
minim
um
of
f
(
x
)
.
As
mentio
n
in
Section
1,
x
(0)
can
be
an
inter
ior
point
or
boundar
y
point
of
f
easib
le
region.
Ho
w
e
v
er
,
there
is
one
more
possibility
that
is
x
(0)
can
be
an
e
xter
ior
point.
Theref
ore
,
if
x
(0)
2
F
,
then
x
(0)
becomes
the
optimal
solution
of
the
QPP
[1].
Another
adv
antage
of
str
ictly
con
v
e
x
proper
ties
of
f
(
x
)
is
that,
if
x
(0)
is
an
e
xter
ior
point,
then
definitely
,
x
,
the
optimal
solution
of
the
considered
prob
lem
is
on
the
boundar
y
of
the
f
easib
le
region.
Theref
ore
,
x
m
ust
be
located
on
one
of
the
activ
e
or
equality
constr
aints
or
on
the
intersection
of
se
v
er
al
activ
e
(equality)
constr
aints
[2,
10].
In
the
con
v
entional
approach,
the
v
alues
of
the
par
ameters
of
QPP
models
m
ust
be
w
ell
defined
and
precise
.
Ho
w
e
v
er
,
in
real
lif
e
w
or
ld
en
vironment
this
is
not
a
realistic
assumption.
In
the
real
prob
lems
there
ma
y
e
xist
uncer
tainty
about
the
par
ameters
.
In
such
a
situation,
the
par
ameters
of
QPP
with
m
fuzzy
constr
aints
and
n
fuzzy
v
ar
iab
les
ma
y
be
f
or
m
ulated
as
f
ollo
ws:
M
inimiz
e
Z
(
x
)
=
1
2
n
X
j
=1
n
X
i
=1
x
i
d
ij
x
j
+
n
X
i
=1
c
i
x
i
(5)
subject
to
m
X
i
=1
n
X
j
=1
a
ij
x
j
m
X
i
=1
b
i
(6)
where
c
=
(
c
i
)
n
1
,
A
=
(
a
ij
)
m
n
,
(
b
)
=
(
b
i
)
m
1
,
D
=
(
d
ij
)
n
n
is
a
positiv
e
definite
and
symmetr
ic
matr
ix
of
fuzzy
n
umbers
and
all
v
ar
iab
les
,
x
=
(
x
1
;
;
x
n
)
are
non-negativ
e
fuzzy
n
umbers
.
Definition
5
[15]
,
An
y
set
of
x
i
which
satisfies
the
set
of
the
constr
aints
in
(6)
is
called
f
easib
le
solution
f
or
(5)-(6).
Let
F
be
the
set
of
all
f
easib
le
solutions
of
(6).
W
e
shall
sa
y
that
x
2
F
is
an
optimal
f
easib
le
solution
f
or
(5)-(6)
if
Z
(
x
)
Z
(
x
)
;
8
x
2
F
.
Remark
2
The
fuzzy
optimal
solution
of
QPP
prob
lem
(5)-(6)
will
be
a
tr
iangle
fuzzy
n
umber
x
[
]
=
[
x
1
(
)
;
x
2
(
)]
if
its
satisfies
the
f
ollo
wing
conditions
.
1.
x
is
a
non-negativ
e
fuzzy
n
umber
2.
A
x
b
3.
x
1
(
)
monotonically
increasing,
0
1
4.
x
2
(
)
monotonically
decreasing,
0
1
5.
x
1
(1)
x
2
(1)
By
using
-cuts
notation
[11],
the
fuzzy
QPP
of
Equation
(5)-(6)
can
be
wr
itten
as
f
ollo
ws:
M
inimiz
e
Z
(
x
)
=
1
2
n
X
j
=1
n
X
i
=1
[(
d
ij
)
;
(
d
+
ij
)
]
x
i
x
j
+
n
X
i
=1
[(
c
i
)
;
(
c
+
i
)
]
x
i
+
[(
q
)
;
(
q
+
)
]
(7)
subject
to
m
X
i
=1
n
X
j
=1
[(
a
ij
)
;
(
a
+
ij
)
]
x
j
m
X
i
=1
[(
b
i
)
;
(
b
+
i
)
]
(8)
all
v
ar
iab
les
are
non-negativ
e
,
and
2
[0
;
1]
.
By
separ
ation
ter
ms
Z
(
)
and
Z
(
)
+
of
Equation
(7),
w
e
ha
v
e
t
w
o
types
of
the
fuzzy
QPP
to
be
solv
ed,
as
f
ollo
ws:
TELK
OMNIKA
V
ol.
16,
No
.
6,
December
2018
:
2782
2790
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
2786
Min
(
Z
(
x
))
=
n
X
i
=1
n
X
j
=1
x
j
d
i;j
x
j
+
n
X
j
=1
c
T
j
x
j
s
.t
m
X
i
=1
n
X
j
=1
a
i;j
x
j
m
X
i
=1
b
i
9
>
>
>
>
>
>
>
=
>
>
>
>
>
>
>
;
(9)
with
all
v
ar
iab
les
are
non
negativ
e
,
and
2
[0
;
1]
,
and
Min
(
Z
(
x
))
+
=
n
X
i
=1
n
X
j
=1
x
+
j
d
i;j
x
+
j
+
n
X
j
=1
c
T
+
j
x
+
j
s
.t
m
X
i
=1
n
X
j
=1
a
i;j
x
+
j
m
X
i
=1
b
+
i
9
>
>
>
>
>
>
>
=
>
>
>
>
>
>
>
;
(10)
with
all
v
ar
iab
les
are
non
negativ
e
,
and
2
[0
;
1]
.
An
y
set
of
x
(
)
=
[
x
(
)
;
x
(
)
+
]
which
satisfies
the
set
of
the
constr
aints
in
(6)
is
called
f
easib
le
solutions
.
Let
F
in
Equation
(3)
be
t
he
set
of
all
f
easib
le
solutions
,
w
e
shall
sa
y
th
at
x
=
[
x
(
)
;
x
(
)
+
]
resides
inside
of
F
is
an
optimal
f
easib
le
solution
pro
vided
Z
(
x
)
Z
(
x
)
f
or
all
x
2
F
.
Since
z
(
x
)
giv
en
b
y
(7)
is
a
positiv
e
definite
quadr
atic
function,
then
z
(
x
)
is
str
ictly
con
v
e
x
in
x
(
x
)
=
[
x
(
)
;
x
(
)
+
]
,
theref
ore
z
(
x
)
attains
a
unique
minim
um
at
n
X
j
=1
d
i;j
x
j
=
n
X
j
=1
c
j
;
and
n
X
j
=1
d
i;j
x
+
j
=
n
X
j
=1
c
+
j
(11)
f
or
(
i
=
1
;
;
m
)
.
If
w
e
denoted
x
(0)
=
[
x
(0)
(
)
;
x
(0)
(
)
+
]
as
the
fuzzy
unconstr
aine
d
minim
um
of
(5)
then
w
e
ha
v
e
x
(0)
=
n
X
j
=1
(
d
i;j
)
1
c
j
;
and
x
(0)
+
=
n
X
j
=1
(
d
i;j
)
1
c
+
j
:
(12)
4.
Sear
c
hing
The
Equality
Constraint
P
oint
This
section
will
descr
ibe
ho
w
to
search
a
point
on
the
equality
constr
aint
which
becomes
a
candidate
of
optimal
solution
to
the
prob
lem
(7)
-
(8).
This
method
will
be
applied
to
the
equality
constr
aint
which
are
violated
b
y
x
(0)
,
which
is
A
T
j
x
j
>
b
i
,
(
i
=
1
;
;
n;
j
=
1
;
;
m
)
.
Let
us
consider
the
constr
aint
of
the
QPP
giv
en
b
y
a
i;
1
x
1
+
a
i;
2
x
2
+
+
a
i;k
x
k
b
i
;
(
k
n
)
(13)
a
j
;
1
x
1
+
a
j
;
2
x
2
+
+
a
j
;k
x
k
b
j
:
(14)
and
their
equality
constr
aints
is
giv
en
b
y
a
i;
1
x
1
+
a
i;
2
x
2
+
+
a
i;k
x
k
=
b
i
;
(15)
a
j
;
1
x
1
+
a
j
;
2
x
2
+
+
a
j
;k
x
k
=
b
j
:
(16)
The
fuzzy
equality
constr
aints
can
be
wr
itten
as
Using
Alpha-cuts
and
Constr
aint
Explor
ation
Approach
on
Quadr
atic
Prog
r
amming...
(Y
.
Dasr
il)
Evaluation Warning : The document was created with Spire.PDF for Python.
2787
ISSN:
1693-6930
a
i;
1
(
x
1
;
x
+
1
)
+
a
i;
2
(
x
2
;
x
+
2
)
+
+
a
i;k
(
x
k
;
x
+
k
)
=
[
b
i
;
b
+
1
]
(17)
a
j
;
1
(
x
1
;
x
+
1
)
+
a
j
;
2
(
x
2
;
x
+
2
)
+
+
a
j
;k
(
x
k
;
x
+
k
)
=
[
b
j
;
b
+
j
]
:
(18)
or
a
i;
1
x
1
+
a
i;
2
x
2
+
+
a
i;k
x
k
=
b
i
;
a
i;
1
x
+
1
+
a
i;
2
x
+
2
+
+
a
i;k
x
+
k
=
b
+
i
;
(19)
a
j
;
1
x
1
+
a
j
;
2
x
2
+
+
a
j
;k
x
k
=
b
j
;
a
j
;
1
x
+
1
+
a
j
;
2
x
+
2
+
+
a
j
;k
x
+
3
=
b
+
j
:
(20)
Clear
ly
,
the
point
b
i
a
1
;
1
(1
!
1
!
k
1
)
;
b
i
a
1
;
2
!
1
;
;
b
i
a
1
;k
!
k
1
(21)
and
b
+
i
a
1
;
1
(1
!
1
!
k
1
)
;
b
+
i
a
1
;
2
!
1
;
;
b
+
i
a
1
;k
!
k
1
(22)
which
lies
on
the
Equation
(15)
is
uniquely
deter
mined
since
there
is
one
to
one
correspondence
betw
een
the
point
and
its
respected
!
i
,
(
i
=
1
;
:::;
k
1)
.
Theref
ore
,
b
y
substituting
the
point
in
Equation
(21)
into
quadr
atic
function
(8),
w
e
can
obtain
the
function
with
!
i
as
the
ind
ependent
v
ar
iab
le
f
rom
which
t
he
unconstr
ained
minim
um
of
f
(
!
i
)
can
be
achie
v
ed
through
minimizing
f
(
!
i
)
with
respect
to
!
i
.
If
!
i
,
(
i
=
1
;
:::;
k
1)
denotes
the
unconstr
ained
minim
um
of
f
(
!
i
)
,
then
w
e
obtain
the
point
b
i
a
1
;
1
(1
!
1
!
k
1
)
;
b
i
a
1
;
2
!
1
;
;
b
i
a
1
;k
!
k
1
(23)
and
b
+
i
a
1
;
1
(1
!
1
!
k
1
)
;
b
+
i
a
1
;
2
!
1
;
;
b
+
i
a
1
;k
!
k
1
(24)
which
ref
ers
to
the
fuzzy
constr
ained
minim
um
of
f
(
x
)
,
subject
to
the
equality
constr
aint
giv
en
b
y
(15)
and
w
e
denoted
b
y
x
i
=
b
i
a
1
;
1
(1
!
1
!
k
1
)
;
b
i
a
1
;
2
!
1
;
;
b
i
a
1
;k
!
k
1
;
b
+
i
a
1
;
1
(1
!
1
!
k
1
)
;
b
+
i
a
1
;
2
!
1
;
;
b
+
i
a
1
;k
!
k
1
(25)
By
the
similar
w
a
y
,
f
or
equation
giv
en
b
y
(18),
w
e
ha
v
e
x
j
=
b
j
a
1
;
1
(1
!
1
!
k
1
)
;
b
j
a
1
;
2
!
1
;
;
b
j
a
1
;k
!
k
1
;
b
+
j
a
1
;
1
(1
!
1
!
k
1
)
;
b
+
j
a
1
;
2
!
1
;
;
b
+
j
a
1
;k
!
k
1
(26)
which
ref
ers
to
the
fuzzy
constr
ained
minim
um
of
f
(
x
)
,
subject
to
the
equality
constr
aint
giv
en
b
y
(16).
5.
The
Outline
of
Algorithm
The
results
sho
wn
in
pre
vious
section
can
be
used
to
obtain
an
algor
ithm
f
or
finding
the
fuzzy
optimal
solution
of
QPP
.
The
br
ief
algor
ithm
is
as
f
ollo
ws:
1.
Compute
x
(0)
,
the
unconstr
ained
minim
um
of
f
(
x
)
b
y
using
(12)
TELK
OMNIKA
V
ol.
16,
No
.
6,
December
2018
:
2782
2790
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
2788
2.
If
x
(0)
satisfies
all
the
constr
aints
pro
vided
b
y
the
prob
lem,
then
stop
,
x
(0)
becomes
the
fuzzy
optimal
solution
of
the
QPP
.
But
if
x
(0)
=
2
F
,
then
push
all
the
inde
x
es
of
the
con-
str
aints
violated
b
y
x
(0)
onto
the
set
S
,
where
S
=
f
j
j
A
T
j
x
>
b
j
;
j
2
f
1
;
;
m
gg
f
or
fur
ther
in
v
estigation.
3.
Compute
x
j
,
the
fuzzy
constr
ained
minim
um
of
f
(
x
)
subject
to
equality
constr
aint
j
where
j
2
S
.
If
x
j
2
F
f
or
one
j
2
S
,
then
x
j
is
the
fuzzy
optimal
solution
of
QPP
and
stop
.
Otherwise
,
search
the
fuzzy
optimal
solution
of
QPP
which
might
be
located
on
the
equality
or
intersection
of
tw
o
and
more
equality
violated
constr
aints
b
y
x
(0)
according
to
the
method
e
xplained
in
[1,
2,
10].
6.
Numerical
Results
An
e
xample
has
bee
n
illustr
ated
to
sho
w
the
capability
of
the
constr
aints
e
xplor
ation
method.
Example
tak
en
from
[16],
where
the
objectiv
e
f
unction
is
to
minimiz
e
the
quadr
atic
function
and
the
constr
aint
functions
consist
of
tw
o
linear
functions
.
The
first
constr
aint
ha
v
e
an
equality
sign
and
the
second
constr
aint
ha
v
e
an
inequalities
sign.
M
inimiz
ed
z
=
(
x
1
1)
2
+
(
x
2
2)
2
(27)
subject
to
x
1
+
x
2
=
1
(28)
x
1
+
x
2
2
(29)
and
(
x
1
;
x
2
)
(0
;
0)
:
(30)
The
fuzzy
QPP
of
the
prob
lem
(27)
-
(30)
with
2
[0
;
1]
can
be
wr
itten
as
M
inimiz
ed
Z
(
x
)
=
(
x
1
1)
2
+
(
x
2
2)
2
(31)
subject
to
x
1
+
x
2
=
1
(32)
x
1
+
x
2
2
(33)
with
all
v
ar
iab
les
are
non-negativ
e
.
According
to
the
algor
ithm
in
Section
5.,
the
optimal
solution
of
the
fuzzy
QPP
is
summa-
r
iz
ed
in
3
steps
as
f
ollo
ws:
Step
1
The
deter
mination
of
unconstr
ained
minim
um.
F
or
this
prob
lem
w
e
ha
v
e
D
=
2
0
0
2
;
c
=
(
4
;
2)
T
;
and
q
=
4
;
(34)
b
y
using
(12),
w
e
get
x
(0)
=
h
+
1
2
;
+
2
i
;
h
3
+
1
2
;
+
3
i
.
Step
2
T
est
the
f
easibility
of
the
x
(0)
.
This
can
be
done
b
y
substituting
x
(0)
to
both
of
the
con-
str
aints
.
Clear
ly
,
x
(0)
violated
constr
aint
(33
).
Theref
ore
,
w
e
are
only
f
ocusing
in
finding
the
optimal
solution
on
the
constr
aint
which
is
giv
en
b
y
equation
(33).
Using
Alpha-cuts
and
Constr
aint
Explor
ation
Approach
on
Quadr
atic
Prog
r
amming...
(Y
.
Dasr
il)
Evaluation Warning : The document was created with Spire.PDF for Python.
2789
ISSN:
1693-6930
Step
3
By
choosing
2
points
on
(33),
usually
the
intersection
of
the
line
(33)
with
the
coordinates
axis
is
chosen.
It
giv
es
the
constr
ained
minim
um
with
respect
to
(33)
as
an
activ
e
constr
aint
and
w
e
denoted
as
x
26
where
x
26
=
h
1
2
8
3
37
2
+
106
73
2
+
2
+
1
;
1
2
4
3
21
2
+
34
21
2
+
2
+
1
i
;
h
(
2)(2
2
13
+
5)
(
+
1)
2
;
(
2)(3
5)(2
5)
(
+
1)
2
i
:
By
using
the
f
easibility
test
in
Step
2,
clear
ly
the
constr
ained
minim
um,
x
26
satisfies
equation
(32)
and
(33)
or
x
26
2
F
.
Then
the
optimal
solution
f
or
the
e
xample
is
x
26
=
x
.
No
w
,
at
=
1
x
=
(
1
2
;
3
2
)
as
an
optimal
solution
of
the
prob
lem,
and
ag
reed
with
the
solution
that
giv
en
b
y
[16].
7.
Conc
lusion
A
quadr
atic
prog
r
amming
prob
lems
(QPP)
is
an
optimization
prob
lem
where
the
objectiv
e
function
is
quadr
atic
function
and
the
constr
aints
are
linear
functions
.
Man
y
engineer
ing
prob
lems
can
be
represented
as
QPP
,
such
as
sensor
netw
or
k
localization,
pr
inciple
component
analysis
and
optimal
po
w
er
flo
w
.
That
is
,
some
pe
rf
or
mance
metr
ic
is
being
optimiz
ed
with
subject
to
design
limits
.
In
this
paper
w
e
solv
e
the
q
uadr
atic
prog
r
amming
prob
lem
b
y
using
-cuts
and
constr
aints
e
xplor
ation
approach.
The
fuzzy
solution
are
char
acter
iz
ed
b
y
fuzzy
n
umbers
,
through
the
use
of
the
concept
of
violation
constr
aints
b
y
the
fuzzy
u
nconstr
ained
and
the
optimal
solution.
By
this
approach,
the
fuzzy
optimal
solution
of
quadr
atic
prog
r
amming
prob
lem
which
is
occurr
ing
in
the
real
lif
e
situation
can
be
easily
obtained.
Ac
kno
wledg
ement.
The
authors
w
ould
lik
e
to
thank
Center
f
or
Research
and
Inno
v
ation
Management
(CRIM),
Center
of
Excellence
,
research
g
r
ant
PJP/2017/FKEKK/HI10/S01532
and
Univ
ersiti
T
eknikal
Mala
ysia
Melaka
(UT
eM)
f
or
their
encour
agement
and
help
in
sponsor
ing
this
research.
Ref
erences
[1]
Ismail
Bin
Mohd
and
Y
osza
bin
Dasr
il.
Constr
aint
e
xp
lor
ation
method
f
or
quadr
atic
prog
r
amming
prob
lem,
Jour
nal
of
Applied
Mathematics
and
Computation
.
2000;
112:161-170.
[2]
Ismail
Bin
Mohd
dan
Y
osza.
Cross-Product
direction
e
xpl
or
ation
approach
f
or
solving
the
quadr
atic
pro-
g
r
amming
prob
lems
.
Jour
nal
ff
Ultr
a
Scientist
of
Ph
ysical
Sciences
.
2000;
12(2):155-162.
[3]
Bose
S
,
Dennise
FG,
Chandy
KM,
and
Lo
w
SH.
Solving
Quadr
atically
Constr
ained
Quadr
atic
Prog
r
ams
on
Acyclic
Gr
aph
with
Application
t
o
Optimal
P
o
w
er
Flo
w
.
IEEE
Xplore:
Proceeding
A
nn
ual
Conf
erence
of
Inf
or
mation
Sciences
and
System
(CISS),
Ne
w
Y
or
k.
2014:
19-21.
[4]
Antonio
u
A,
and
W
u-Sheng
L.
Pr
actical
Op
timization,
Algor
ithms
and
Engineer
ing
Applications
.
Ne
w
Y
or
k:
Spr
inger
.
2007.
[5]
Zadeh
LA,
Fuzzy
sets
.
Jour
nal
of
Inf
or
mation
and
Control
.
1965;
8:338-353.
[6]
Bellman
RE,
and
Zadeh
LA.
Decision
making
in
a
fuzzy
en
vironment.
Jour
nal
of
Management
Science
.
1970;
17:141-164.
[7]
T
anaka
H,
Okuda
T
,
and
Asai
K.
On
fuzzy
mathematical
prog
r
amming.
Jour
nal
of
Cyber
netics
and
Sys-
tem
.
1973;
3:37-46.
[8]
Zimmer
man
HJ
.
Fuzzy
prog
r
amming
and
linear
prog
r
amming
wi
th
se
v
er
al
objectiv
e
functions
.
Jour
nal
of
Fuzzy
Sets
and
System
.
1978;
1:45-55.
[9]
E.
Ammar
and
H.
A
Khalif
ah,
Fuzzy
por
tf
olio
optimization
a
quadr
atic
prog
r
amming
a
pproach,
Jour
nal
of
Chaos
,
Solitons
and
F
r
actals
,
2003;
18:1045-1054
TELK
OMNIKA
V
ol.
16,
No
.
6,
December
2018
:
2782
2790
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
2790
[10]
Ismail
Bin
Mohd
and
Y
osza.
A
note
on
the
violated
constr
aints
approach
f
or
solving
the
quadr
atic
pro-
g
r
amming
prob
lem.
Jour
nal
of
Ultr
a
Scientist
of
Ph
ysical
Sciences
.
1998;
10(2):141-148
[11]
Kaufmann
A,
and
Gupta
MM.
Intro
duction
to
fuzzy
ar
ithmetic:
Theor
y
and
Applications
,
V
an
Nostr
and
Reinhold.
Ne
w
Y
or
k.
1985.
[12]
Liou
TS
,
and
W
ang
MJ
.
Ranking
fuzzy
n
umbers
with
integ
r
al
v
alue
.
Jour
nal
of
Fuzzy
Sets
and
Systems
.
1992;
50:247-255.
[13]
Buc
kle
y
JJ
,
Esf
andiar
E,
and
Thomas
F
.
Fuzzy
mathematics
in
economics
and
engineer
ing.
Ph
ysica-
V
er
lag.
2002.
[14]
Zohan
y
Q,
Zhang,
and
W
an
y
G.
Fuzzy
r
andom
v
ar
iab
le-v
alued
e
xponential
function,
logar
ithmic
func-
tion
and
po
w
er
function.
Jour
nal
of
Fuzzy
Sets
and
Systems
,
1998;
99:311-324.
[15]
Maleki
H.R,
T
ata
M,
and
Ma
shinchi
M.
Linear
prog
r
amming
with
fuzzy
v
ar
iab
les
.
Jour
nal
of
Fuzzy
Sets
and
Systems
.
2000;
109:1026-1092.
[16]
Wismer
D
A,
and
Chattergy
R.
Introduction
to
Nonlinear
Optimization,
Noth-Holland
Pub
.
Compan
y
.
1978.
Using
Alpha-cuts
and
Constr
aint
Explor
ation
Approach
on
Quadr
atic
Prog
r
amming...
(Y
.
Dasr
il)
Evaluation Warning : The document was created with Spire.PDF for Python.