Information Technology Reference
In-Depth Information
=
=
where
θ
i
(i
1
,...,l)
are Lagrangian multipliers for the
constraint inequalities and constraint equations.
The
Lagrangian Dual Function f
d
is defined as the minimum value of the La-
grangian over
x
,
1
,...,m)
and
φ
i
(i
f
d
(θ, φ)
=
min
x
L(x, θ, φ).
Suppose the optimal value of the original optimization problem is
f
∗
, obtained at
x
∗
, i.e.,
f
∗
=
f(x
∗
)
. Then
∀
θ
≥
0, considering
g
i
(x)
≤
0 and
h
i
(x)
=
0, we have,
f(x)
+
φ
i
h
i
(x)
m
l
f
∗
.
f
d
(θ, φ)
=
min
x
θ
i
g
i
(x)
+
≤
min
x
f(x)
=
i
=
1
i
=
1
Therefore,
f
d
(θ, φ)
is a lower bound for the optimal value
f
∗
of the original prob-
lem. To find the best (tightest) bound, we can solve the following
Lagrangian Dual
Problem
to approach
f
∗
,
max
θ,φ
f
d
(θ, φ),
s.t.
θ
≥
0
.
It is not difficult to see that the dual problem is equivalent to the original problem.
Suppose the optimal value of the dual problem is
f
d
, obtained at
(θ
∗
,φ
∗
)
, i.e.,
f
d
f
d
(θ
∗
,φ
∗
)
. Generally,
f
d
f
∗
f
∗
. This is called as
weak
=
≤
since
f
d
(θ, φ)
≤
duality
.If
f
d
f
∗
holds, then we claim that
strong duality
holds, indicating that
the best bound obtained from the Lagrange dual function is tight.
It can be proven that strong duality holds if the optimization problem respects
Slater's Condition
. Slater's Condition requires that there exists a point
x
=
∈
dom
f
such that
x
is strictly feasible, i.e.,
g
i
(x) <
0,
∀
i
=
1
,...,m
and
h
i
(x)
=
0,
∀
i
=
1
,...,l
.
21.3.5 KKT Conditions
If a convex optimization problem respects Slater's Condition, we can obtain an op-
timal tuple
(x
∗
,θ
∗
,φ
∗
)
using the Karush-Kuhn-Tucker (KKT) conditions below.
Then
x
∗
is an optimal point for the original problem and
(θ
∗
,φ
∗
)
is an optimal
point for the dual problem.
⎧
⎨
g
i
(x
∗
)
≤
0
,i
=
1
,...,m,
h
i
(x
∗
)
=
0
,i
=
1
,...,l,
θ
i
≥
0
,i
=
1
,...,m,
⎩
θ
i
g
i
(x
∗
)
1
,...,m,
∇
f(x
∗
)
+
i
=
1
θ
i
∇
g
i
(x
∗
)
+
i
=
1
φ
i
∇
h
i
(x
∗
)
=
=
0
,i
=
0
.
