Forum:  Numerik & Optimierung
Thema: Fixpunktsatz Gradientenverfahren
Themen-Übersicht
mathematikerlein
Aktiv
Dabei seit: 23.06.2020
Mitteilungen: 61
Themenstart: 2020-10-23 14:11

Hallo, vorliegend ist eine stetig differenzierbare Funktion, die außerdem gleichmäßig konvex ist (mit Konstante $\sigma$). Als Schrittweite für das Gradientenverfahren wird konstant $\gamma$ mit $0<\gamma < 4\sigma / L^2$ gewählt, wobei L die Lipschitz-Konstante ist - der Gradient von f ist global als lipschitz stetig vorausgesetzt. zeigen sollen wir nun, dass die Vorschrift vom Gradientenverfahren für beliebige Iterierte eine strike Kontraktion ist, um danach den Fixpunktsatz anwenden zu können bzgl. Minimum. Der Startpunkt $x_0$ ist dabei beliebig aus $\mathbb{R}^n$ gewählt. Hat jemand Ideen ? Meine Abschätzungen sind anscheinend immer zu grob, da ich nur auf eine Konstante komme, die echt größer als 1 ist...außerdem weiß ich nicht genau, wie ich die gleichmäßige Konvexität ausnutzen soll. So schwierig kann es doch eigentlich nicht sein.

Danke schon mal.
Liebe Grüße


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3153
Herkunft: der Nähe von Schwerin
Beitrag No.1, eingetragen 2020-10-23 17:09

Hallo,

kannst du bitte nochmal schreiben, was gleichmäßig konvexe Funktionen sind?
Schreib bitte trotzdem, was du probiert hast.

Liebe Grüße


mathematikerlein
Aktiv
Dabei seit: 23.06.2020
Mitteilungen: 61
Beitrag No.2, vom Themenstarter, eingetragen 2020-10-23 17:56

Hallo,

Ja.
$f(\lambda x + (1-\lambda)y) + \sigma \lambda (1-\lambda)\| x-y\|^2 \leq \lambda f(x) + (1-\lambda)f(y)$ ($\sigma > 0$)beziehungsweise die äquivalente Charakterisierung : $f(x)-f(y) \geq \nabla f(y) (x-y) + \sigma \| x - y\|^2$.

Ich hätte halt versucht für beliebige Iterierte bzw. einfach bel. $x,y \in \mathbb{R}^n$ zu zeigen, dass $\|\phi (x) - \phi(y)\| = \| x - \gamma \nabla f(x) - (y - \gamma \nabla f(y))\| \leq C \|x-y\|$ mit $0<c<1$ zu zeigen, dabei habe ich in obigem die Dreiecksungl. angewandt und eben die Lipschitz-Stetigkeit des Gradienten und komme nach ein paar wenigen Schritten auf der rechten Seite der Ungleichung zum Ausdruck: $...\leq (1 + \frac{4 \sigma}{L} \|x-y\|)$. Also zu grob und die glm. Konvexität ging eben nicht ein, weil ich nicht weiß wo man die verwenden soll.
Ideen ? 😃
Grüße


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3153
Herkunft: der Nähe von Schwerin
Beitrag No.3, eingetragen 2020-10-23 18:19

Nutze lieber
2020-10-23 17:56 - mathematikerlein in Beitrag No. 2 schreibt:
die äquivalente Charakterisierung : $f(x)-f(y) \geq (\nabla f(y))^T (x-y) + \sigma \| x - y\|^2$.

Bist du dir sicher, dass es $\geq$ ist? Nicht doch lieber $\leq$?

Du sollst anscheinend die Norm von $\phi(y):= y-\gamma \nabla f(y)$ abschätzen. Vielleicht hilft Umstellen nach $\nabla f(y)$ und Einsetzen in die Ungleichung.


zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 1998
Beitrag No.4, eingetragen 2020-10-23 19:07

2020-10-23 18:19 - ochen in Beitrag No. 3 schreibt:
Bist du dir sicher, dass es $\geq$ ist? Nicht doch lieber $\leq$?

Eine konvexe Funktion ist größer als ihre lineare Näherung, daher ist das $\ge$ schon richtig. Wie kommst du auf $\le$?


mathematikerlein
Aktiv
Dabei seit: 23.06.2020
Mitteilungen: 61
Beitrag No.5, vom Themenstarter, eingetragen 2020-10-23 19:13

Hallo,

Danke dir für die Antwort.
Ja, da gehört ganz sicher ein "$\geq$" hin :)
Danke daran hatte ich auch schon gedacht, allerdings ist mir dann nicht klar wie ich die Lipschitz-Stetigkeit des Gradienten verwenden soll, da dann ja alle Terme die einen Gradienten beinhalten weg sind.

Grüße

[Die Antwort wurde nach Beitrag No.3 begonnen.]


mathematikerlein
Aktiv
Dabei seit: 23.06.2020
Mitteilungen: 61
Beitrag No.6, vom Themenstarter, eingetragen 2020-10-24 11:01

Hat niemand Ideen, wie man die Abschätzung hinbekommen könnte ? 😃

Liebe Grüße


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3153
Herkunft: der Nähe von Schwerin
Beitrag No.7, eingetragen 2020-10-24 16:10

2020-10-23 19:07 - zippy in Beitrag No. 4 schreibt:
2020-10-23 18:19 - ochen in Beitrag No. 3 schreibt:
Bist du dir sicher, dass es $\geq$ ist? Nicht doch lieber $\leq$?

Eine konvexe Funktion ist größer als ihre lineare Näherung, daher ist das $\ge$ schon richtig. Wie kommst du auf $\le$?
Sorry, das war falsch von mir.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249954=110
Druckdatum: 2021-04-15 20:15