Image Processing Reference
In-Depth Information
Das früher entwickelte
Extragradienten-Verfahren
, vorgeschlagen in [88], folgt dem
gleichen Grundsatz, es unterscheidet sich nur dadurch, dass beim Berechnen von
u
n
+1
und
w
n
+1
die Operatoren
A
∗
und
A
jeweils an
w
n
+1
und
u
n
+1
ausgewertet
werden.
•
Arrow-Hurwicz-Verfahren mit linearem primalen Extragradienten
Ein neuerer Ansatz, der vor allem für Probleme in der Bildverarbeitung gut funk-
tioniert [35], basiert auf dem semi-implizitem Arrow-Hurwicz-Verfahren mit ei-
ner primalen „Extragradientenfolge“
u
n
. Statt für diese einen Arrow-Hurwicz-
Schritt ausführen, wird eine geschickt gewählte Linearkombination gebildet (ba-
sierend auf
u
∗
=
(
)
2
u
∗
−
u
∗
).
⎧
⎨
w
n
+1
F
2
)
−
1
w
n
A u
n
=(
+
τ∂
(
+
τ
)
id
,
u
n
+1
)
−
1
u
n
A
∗
w
n
+1
=(
id
+
σ∂
F
1
(
−
σ
)
,
(6.89)
⎩
u
n
+1
2
u
n
+1
u
n
=
−
Man beachte, dass hier, da nur für die primale Variable ein „Extragradient“ erklärt
wird, die Reihenfolge der Aktualisierung der primalen und dualen Variable eine
Rolle spielt, es also wichtig ist, den Schritt für die duale Variable zuerst auszufüh-
ren. Die primale und duale Variable können selbstverständlich vertauscht werden,
in diesem Fall kann man auch von einem dualen Extragradienten sprechen. Der
benötigte Speicherplatz ist vergleichbar mit dem des expliziten Arrow-Hurwicz-
Verfahrens.
Von allen Verfahren weiß man, dass sie unter Annahmen an die Schrittweiten
σ
und
in einem gewissen Sinn konvergieren. Im Vergleich zu den klassischen Arrow-
Hurwicz-Methoden kann dabei bei der modifizierten Arrow-Hurwicz und der Extra-
gradienten-Methode Konvergenz unter schwächeren Annahmen sichergestellt werden,
sie sind daher, trotz des höheren Speicherbedarfs, von praktischem Interesse. Für De-
tails verweisen hier auf die Originalarbeiten und wollen uns nur mit der Konvergenz
des Arrow-Hurwicz-Verfahrens mit linearem primalen Extragradienten näher beschäf-
tigen. Dazu folgen wir der Darstellung in [35] und leiten als erstes eine Abschätzung
für eines Arrow-Hurwicz-Schritt mit vorgegebenen
τ
(
)
u
,
w
her.
Lemma 6.139
Es seien X
,
Y reelle Hilbert-Räume, A
,F
2
∈
Γ
0
(
∈L
(
X
,
Y
)
,F
1
∈
Γ
0
(
X
)
Y
)
und
σ
,
τ
>
0
.
=
×
=(
)
=(
)
×
Bezeichne weiterhin mit Z
X
Y und für Elemente z
u
,
w
, z
u
,
w
in X
Y
2
X
2
Y
=
+
)
Z
=
(
u
,
u
)
X
+
(
w
,
w
)
Y
u
w
2
Z
(
z
,
z
,
z
.
σ
τ
σ
τ
Erfüllt z
,
z
n
,
z
n
+1
,z
n
u
n
,
w
n
und z
n
+1
u
n
+1
,
w
n
+1
∈
=(
)
=(
)
=(
)
Z mit z
u
,
w
die Glei-
chung
u
n
+
1
)
−
1
A
∗
w
u
n
=(
+
σ∂
(
− σ
)
id
F
1
(6.90)
w
n
+1
F
2
)
−
1
w
n
=(
+
τ∂
(
+
τ
)
id
A u
,
