Antworte auf:  Fixpunktsatz Gradientenverfahren von mathematikerlein
Forum:  Numerik & Optimierung, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3046
Herkunft: der Nähe von Schwerin

 Beitrag No.7, eingetragen 2020-10-24 16:10    [Diesen Beitrag zitieren]

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.


mathematikerlein
Aktiv
Dabei seit: 23.06.2020
Mitteilungen: 56
 Beitrag No.6, eingetragen 2020-10-24 11:01    [Diesen Beitrag zitieren]

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

Liebe Grüße


mathematikerlein
Aktiv
Dabei seit: 23.06.2020
Mitteilungen: 56
 Beitrag No.5, eingetragen 2020-10-23 19:13    [Diesen Beitrag zitieren]

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


zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 1771
 Beitrag No.4, eingetragen 2020-10-23 19:07    [Diesen Beitrag zitieren]

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


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3046
Herkunft: der Nähe von Schwerin

 Beitrag No.3, eingetragen 2020-10-23 18:19    [Diesen Beitrag zitieren]

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.


mathematikerlein
Aktiv
Dabei seit: 23.06.2020
Mitteilungen: 56
 Beitrag No.2, eingetragen 2020-10-23 17:56    [Diesen Beitrag zitieren]

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: 3046
Herkunft: der Nähe von Schwerin

 Beitrag No.1, eingetragen 2020-10-23 17:09    [Diesen Beitrag zitieren]

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: 56
 Themenstart: 2020-10-23 14:11    [Diesen Beitrag zitieren]

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


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 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]