Fenchel-Rockafellar Dualilty to Lagrangian Duality
Shuvomoy Das Gupta
September 27, 2024
This is a short blog to show the connection between Fenchel-Rockafellar
Dualilty to Lagrangian Duality.
Fenchel-Rockafellar duality.
Notation and notions.
• R
n
−
= {y ∈ R
n
| ∀
i∈[1:n]
y
i
≤ 0} and
R
n
+
= {y ∈ R
n
| ∀
i∈[1:n]
y
i
≥ 0}, where
both are closed convex cones.
• A CCP function is closed, convex, and
proper (lower-semicontinuous).
• For a nonempty closed convex set S in
R
n
, its indicator function is:
δ
S
(x) =
(
0, if x ∈ S
∞, else.
• For a nonempty closed convex set S in
R
n
, its support function is:
σ
S
(u) = sup
x∈S
⟨
x | s
⟩
• The conjugate function of a function
ϕ : R
n
→ R is defined as
ϕ
∗
(u) = sup
x∈R
n
(
−ϕ(x) +
⟨
x | u
⟩
)
,
and if ϕ is CCP then ϕ
∗∗
= ϕ.
• For a nonempty closed convex set S in
R
n
,
δ
∗
S
= σ
S
, and σ
∗
S
= δ
S
.
Setup.
Let f be a CCP function on R
n
and g be a CCP function on R
m
. Let
H be a vector-valued map from R
n
to R
m
, and
e
H be another vector-
valued map form R
m
to R
n
such that
∀
x∈R
n
,u∈R
m
⟨
u | H(x)
⟩
=
D
e
H(u) | x
E
,
e.g., if H = A ∈ R
m×n
, A being some m × n matrix, then
e
H = A
⊤
.
Lagrangian associated with Fenchel-Rockafellar Dualilty.
Consider the Lagrangian function:
L(x, u) = f (x) +
⟨
u | H(x)
⟩
− g
∗
(u), (L)
which generates the primal problem
1
1
We have
sup
u∈R
m
L(x, u) = f (x) + g(H(x))
because:
sup
u∈R
m
L(x, u)
= sup
u∈R
m
f (x) +
⟨
u | H(x)
⟩
− g
∗
(u)
= f (x) + sup
u∈R
m
(
−g
∗
(u) +
⟨
u | H(x)
⟩
)
= f (x) + g
∗∗
(
H(x)
)
| {z }
g(H(x))
▷ as g ccp
= f (x) + g(H(x)).
minimize
x∈R
n
sup
u∈R
m
L(x, u)
=
minimize
x∈R
n
f (x) + g
(
H(x)
)
,
(P)
and the dual problem
2
2
We have
inf
x∈R
n
L(x, u) = − f
⋆
−
e
H(u)
− g
∗
(u)
because:
inf
x∈R
n
L(x, u)
= inf
x∈R
n
f (x) +
⟨
u | H(x)
⟩
− g
∗
(u)
= − g
∗
(u) + inf
x∈R
n
(
f (x) +
⟨
u | H(x)
⟩
)
= − g
∗
(u) − sup
x∈R
n
(
− f (x) −
⟨
u | H(x)
⟩
)
= − g
∗
(u) − sup
x∈R
n
− f (x) −
D
e
H(u) | x
E
= − g
∗
(u) − sup
x∈R
n
− f (x) +
D
−
e
H(u) | x
E
= − g
∗
(u) − f
∗
−
e
H(u)
.
maximize
u∈R
n
inf
x∈R
n
L(x, u)
=
maximize
u∈R
m
− f
⋆
−
e
H(u)
− g
∗
(u)
.
(D)
From Fenchel-Rockafellar to Lagrangian duality.
Consider the convex optimization problem:
minimize
x∈R
n
f
0
(x)
subject to f
i
(x) ≤ 0, i = 1, 2, . . . , m,
!
(1)
where f
0
, f
1
, . . . , f
m
are CCP functions.
fe n chel -rocka f ella r duali lty t o lagra n gian dualit y 2
Now define the map,
¯
H : R
n
→ R
m
as
¯
H(x) ≜
f
1
(x)
f
2
(x)
f
3
(x)
.
.
.
f
m
(x)
,
hence a feasible point
˜
x satisfies
¯
H(
˜
x) ∈ R
m
−
.
Then (1) is equivalent to
minimize
x∈R
n
f
0
(x) + δ
R
m
−
(
¯
H(x)
)
(2)
Comparing (2) with (P), in (L) we can set f ← f
0
, H ←
¯
H, and
g ← δ
R
m
−
thus leading to the Lagrangian in this case:
We have σ
R
m
−
(u) = δ
R
m
+
(u) because
σ
R
m
−
(u) = sup
v∈R
m
−
⟨
v | u
⟩
▷ using definition
= sup
v
(
m
∑
i=1
v
i
u
i
| v
i
≤ 0, i ∈ [1 : m]
)
=
m
∑
i=1
sup
v
i
≤0
v
i
u
i
| {z }
0, if u
i
≥ 0
∞, if u
i
< 0
▷ using seperability
= δ
R
m
+
(u). ▷ through observation
L(x, u)
= f
0
(x) +
⟨
u |
¯
H(x)
⟩
− δ
⋆
R
m
−
(u)
= f
0
(x) +
⟨
u |
¯
H(x)
⟩
− σ
R
m
−
(u) ▷ as δ
⋆
S
=σ
S
= f
0
(x) +
⟨
u |
¯
H(x)
⟩
− δ
R
m
+
(u) ▷ as σ
R
m
−
=δ
R
m
+
(see sidenote)
= f
0
(x) +
m
∑
i=1
u
i
f
i
(x) − δ
R
m
+
(u)
and the corresponding dual problem will be:
maximize
u∈R
n
inf
x
f
0
(x) +
m
∑
i=1
u
i
f
i
(x) − δ
R
m
+
(u)
!
=
maximize
u∈R
n
dual function
z }| {
inf
x
f
0
(x) +
m
∑
i=1
u
i
f
i
(x)
!
subject to u
i
≥ 0, i = 1, 2, . . . , m,
which is the classical Lagrangian dual.
