Information Technology Reference
In-Depth Information
In case of
g
i
(x)
0
, there is no change. If
x
0
is a solution to the constrained
optimized problem:
≤
Minimize
x
∀
i
f(x) subject to g
i
(x)
≤
0
Then there must exist
α
≥
0
∀
i
so that
x
0
satisfies following equations:
i
∂
⎧
n
(
f
(
x
)
+
∑
α
g
(
x
)
=
0
⎪
⎨
i
i
∂
x
(5)
i
=
1
x
=
x
0
⎪
⎩
g
(
x
)
≤
0
i
f
(
x
)
+
∑
α
g
(
x
)
The function
is called Lagrangian denoted
L
. Let
f(X
i
)
be
i
i
i
1
2
|
W
|
and let
g
i
(X)
be
1
-
y
i
(
W
T
⊗
X
i
+ b
),
the constraint in formula III.3.4 becomes:
2
MinimizeL
(
W
,
b
,
λ
))
Maximize
(
(6)
λ
W
,
b
where
1
n
2
T
L
(
W
,
b
,
λ
)
=
|
W
|
+
∑
=
λ
(
−
y
(
W
⊗
X
+
b
))
(7)
i
i
i
2
i
1
The Lagrangian
L
is minimized with respect to the primal variables
W
and
b
and
maximized with respect to the dual variables
λ
. Setting the gradient of
L
w.r.t
W
and
b
to zero, we have
∂
L
(
W
,
b
,
λ
)
⎧
⎧
n
∑
=
0
W
−
λ
y
X
=
0
⎪
⎪
⎨
⎪
⎪
⎨
i
i
i
∂
W
i
=
1
⇔
(8)
∂
L
(
W
,
b
,
λ
)
n
⎪
⎪
⎪
⎪
∑
λ
y
=
0
=
0
i
i
⎩
⎩
∂
λ
i
=
1
Substituting (III.3.8) into (III.3.7) we have:
1
n
n
1
T
i
L
(
λ
)
=
∑
λ
−
∑∑
λ
λ
y
y
X
X
(9)
i
i
j
i
j
j
2
i
=
1
i
==
1
j
1
T
λ =
(
λ
,
λ
,...,
λ
n
)
Where
.
If (9) is re-written in matrix notation then the constrained optimization problem
in (4), (6) leads to dual problem:
1
2
1
I
T
L
(
λ
)
=
λ
I
−
λ
S
λ
Maximize
subject to
λ
≥
0
and
λ
T
y
=
0
(10)
2
Where S is a symmetric
n
x
n
matrix with elements
s
ij
=y
i
y
j
X
i
T
X
j
.
