Image Processing Reference
In-Depth Information
Damit haben wir das duale Optimierungsproblem hergeleitet, es lautet:
F
1
(
−
A
∗
w
F
2
(
∈Y
∗
−
)
−
)
Duales Problem:
max
w
w
.
(6.25)
Es bleibt zu klären, ob sich Infimum und Supremum vertauschen lassen, und ob das
Supremum tatsächlich angenommen wird. In anderen Worten: Es ist zu zeigen, ob das
Minimum in (6.24) dem Maximum in (6.25) entspricht. Folgender Satz gibt ein hinrei-
chendes dafür Kriterium an.
Satz 6.68
(Fenchel-Rockafellar-Dualität)
Es seien F
1
:
X
→
→
eigentlich, konvex und unterhalbstetig auf den reellen
Banach-Räumen X und Y. Ferner sei A
:
X
R
,F
2
:
Y
R
∞
∞
→
Y linear, stetig und das Minimierungsproblem
(
)+
(
)
min
u
F
1
u
F
2
Au
∈
X
besitze eine Lösung u
∗
∈
X. Existiert ein Punkt u
0
u
0
Au
0
∈
X, so dass F
1
(
)
<
∞
,F
2
(
)
<
∞
und F
2
stetig in Au
0
ist, so gilt:
F
1
(
−
A
∗
w
F
2
(
max
w
∈Y
∗
−
)
−
w
)=
min
u
F
1
(
u
)+
F
2
(
Au
)
.
∈X
Insbesondere wird das Maximum angenommen.
Beweis.
Da
u
∗
eine Lösung des Minimierungsproblem ist, haben wir sofort 0
∈ ∂
(
+
F
1
u
∗
)
F
2
◦
. Wir wollen nun den Subdifferential-Kalkül aus Satz 6.51 benutzen, stellen
dazu fest, dass nach Voraussetzung
F
2
A
)(
A
in
u
0
◦
stetig ist, also
A
∗
◦
∂
∂
(
F
1
+
F
2
◦
A
)=
∂
F
1
+
∂
(
F
2
◦
A
)=
∂
F
1
+
F
2
◦
A
.
Dies bedeutet insbesondere, dass es ein
w
∗
∈
Y
∗
gibt mit
A
∗
w
∗
∈
∂
u
∗
)
und
w
∗
∈
−
F
1
(
Au
∗
)
A
∗
w
∗
∈ ∂
u
∗
)
(
−
(
∂
F
2
. Formulieren wir nun die Subgradientenungleichung für
F
1
um:
u
∗
)+
−
A
∗
w
∗
,
v
u
∗
≤
F
1
(
−
F
1
(
v
)
∀
v
∈
X
u
∗
)
−−
A
∗
w
∗
,
u
∗
≤
A
∗
w
∗
,
v
⇔
F
1
(
F
1
(
v
)
−−
∀
v
∈
X
A
∗
w
∗
,
u
∗
−
u
∗
)
≥
A
∗
w
∗
,
v
⇔
−
(
∈X
−
−
(
)
F
1
sup
v
F
1
v
F
1
(
−
A
∗
w
∗
)
=
.
w
∗
,
Au
∗
−
Au
∗
)
≥
F
2
(
w
∗
)
(
Analog bekommen wir
F
2
. Addiert man nun beide Unglei-
chungen, ergibt sich
F
1
(
−
A
∗
w
∗
)+
F
2
(
w
∗
)
≤−
A
∗
w
∗
,
u
∗
−
u
∗
)+
w
∗
,
Au
∗
−
Au
∗
)
F
1
(
F
2
(
u
∗
)
−
Au
∗
)
=
−
(
(
F
1
F
2
und damit
u
∗
)+
Au
∗
)
≤−
F
1
(
−
A
∗
w
∗
)
−
F
2
(
w
∗
)
(
(
F
1
F
2
.