Image Processing Reference
In-Depth Information
wann man die Iteration abbrechen kann. Für dieses Problem gibt es verschiedene An-
sätze, einer davon basiert auf der Dualitätslücke (englisch: „duality gap“). Ist nämlich
(
)
u , w
ein Sattelpunkt von L , so gilt
u , w n
u , w n
u n , w
u n , w
inf
u
L
(
)
L
(
)
L
(
u , w
)
L
(
)
sup
w
L
(
)
.
X
Y
F 1 (
A w n
F 2 (
w n
Das Infimum auf der linken Seite stellt gerade
)
)
dar während
u n
Au n
das Supremum auf der rechten Seite dem primalen Funktionalwert F 1
)
entspricht. Die Differenz ist stets nicht negativ und verschwindet genau in den Sattel-
punkten von L . Man definiert also die Dualitätslücke
(
)+
F 2
(
G
: X
×
Y
R
wie folgt:
F 1 (
A w
F 2 (
G (
u , w
)=
F 1 (
u
)+
F 2 (
Au
)+
)+
w
)
.
(6.95)
Damit ist
G
eigentlich, konvex und unterhalbstetig. Insbesondere gilt
) F 1 (
) min
u
) ,
u n , w n
u n
Au n
G (
)+
F 2
(
F 1
(
u
)+
F 2
(
Au
X
) max
w
)
) .
(6.96)
F 1 (
A w
F 2 (
F 1 (
A w n
F 2 (
u n , w n
w n
G (
Y
)
)
w
Ist also die Dualitätslücke klein, so ist die Differenz der Funktionalwerte von u n und
w n zum jeweiligen Optimum der primalen beziehungsweise dualen Aufgabe ebenfalls
klein. Damit bildet, für ein vorgegebene Toleranz
u n , w n
ε >
0, die Bedingung
G (
) < ε
ein sinnvolles Kriterium zum Abbrechen der Iteration.
Konvergiert nun
u , w )
u n , w n
(
)
gegen einen Sattelpunkt
(
, so folgt mit der Unter-
u n , w n
G
lim inf n→ G (
)
halbstetigkeit von
, die Dualitätslücke muss demnach
nicht gegen 0 konvergieren. Es kann aber durchaus der Fall sein, hinreichend dafür sind
zum Beispiel die Stetigkeit von F 1 , F 2 und deren Fenchel-Konjugierte. Dann liefert
nur 0
G
ein
Abbruchkriterium, welches für den primalen-dualen Algorithmus (6.89) unter der Vor-
aussetzung der Konvergenz die Optimalität der primalen und dualen Funktionalwerte
bis auf eine vorgegebene Toleranz garantiert.
6.4.3 Anwendung der primalen-dualen Algorithmen
Wir wollen eine diskrete Version der im letzten Unterabschnitt untersuchten Methode
für die numerische Lösung der vorgestellten Variationsprobleme benutzen. Dazu gilt
es nun, die Minimierungsprobleme entsprechend zu diskretisieren und anschließend
nachzuprüfen, ob die Fenchel-Rockafellar-Dualität gilt, um die Existenz eines Sattel-
punkt des Lagrange-Funktionals zu bekommen. Gelingt es uns schließlich, zu identifi-
zieren, mit welchen Rechenschritten sich das primale-duale Verfahren (6.89) darstellen
lässt, steht uns nach Satz 6.141 ein konvergenter numerischer Algorithmus zur Verfü-
gung. Beginnen wir mit der Diskretisierung der Funktionale.
Wie in Abschnitt 5.4 gehen wir von rechteckigen diskreten Bildern aus, also N
×
M -
Matrizen ( N , M
1). Die diskreten Indizes
(
i , j
)
genügen im Folgenden stets 1
i
N
>
(
)
und 1
j
M . Mit einer „Pixelgröße“ h
0 entspricht so der
i , j
-te Eintrag dem
Search WWH ::




Custom Search