Matroids Matheplanet Forum Index
Forumbereich moderiert von: matroid
Mathematik » Numerik & Optimierung » Fixpunktsatz Gradientenverfahren
Druckversion
Druckversion
Antworten
Antworten
Universität/Hochschule Fixpunktsatz Gradientenverfahren
mathematikerlein Aktiv Letzter Besuch: im letzten Monat
Mitglied seit: 23.06.2020, Mitteilungen: 37
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-10-23

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 09.03.2015, Mitteilungen: 2990, aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, eingetragen 2020-10-23

Hallo,

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

Liebe Grüße



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathematikerlein Aktiv Letzter Besuch: im letzten Monat
Mitglied seit: 23.06.2020, Mitteilungen: 37
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, vom Themenstarter, eingetragen 2020-10-23

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 09.03.2015, Mitteilungen: 2990, aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.3, eingetragen 2020-10-23

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 24.10.2018, Mitteilungen: 1663
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.4, eingetragen 2020-10-23

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$?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathematikerlein Aktiv Letzter Besuch: im letzten Monat
Mitglied seit: 23.06.2020, Mitteilungen: 37
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.5, vom Themenstarter, eingetragen 2020-10-23

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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathematikerlein Aktiv Letzter Besuch: im letzten Monat
Mitglied seit: 23.06.2020, Mitteilungen: 37
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.6, vom Themenstarter, eingetragen 2020-10-24

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

Liebe Grüße



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 09.03.2015, Mitteilungen: 2990, aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.7, eingetragen 2020-10-24

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathematikerlein hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]