Newton- Verfahren im R^n < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:20 Fr 10.01.2020 | | Autor: | NathanR |
| Aufgabe | Seien $n, p [mm] \in \mathbb{N}$ [/mm] mit $ p < n$. Seien $f: [mm] \mathbb{R}^{n} \rightarrow \mathbb{R}$ [/mm] und $g: [mm] \mathbb{R}^{n} \rightarrow \mathbb{R}^{p}$ [/mm] glatte Funktionen mit der Eigenschaft, dass die zweite Ableitung (nach der ersten Komponente) der Lagrangefunktion $L: [mm] \mathbb{R}^{n} \times \mathbb{R}^{p} \rightarrow \mathbb{R}$, [/mm] die durch
$L(x, [mm] \mu) [/mm] := f(x) + [mm] \mu^{T} [/mm] g(x)$
gegeben ist, positiv definit auf dem Kern von $g'$ ist.
Sei [mm] $x^{*}$ [/mm] eine Lösung des Minimierungsproblems
[mm] $f(x^{*}) [/mm] = min [mm] \{ f(x): x \in \mathbb{R}^{n}, g(x) = 0 \}$.
[/mm]
Der Punkt [mm] $x^{*}$ [/mm] heißt regulär, falls die Gradienten [mm] $\{ \nabla g_{1}(x^{*}), \ldots, \nabla g_{p}(x^{*}) \}$ [/mm] linear unabhängig sind.
In der nichtlinearen Optimierung wird bewiesen, dass -- falls [mm] $x^{*}$ [/mm] regulär und ein lokales Minimum von $f$ ist ---, es eindeutig bestimmte Lagrange - Multiplikatoren [mm] $\mu^{} \in \mathbb{R}^{p}$ [/mm] gibt, so dass [mm] $(x^{*}, \mu^{*}) \in \mathbb{R}^{n} \times \mathbb{R}^{p}$ [/mm] die Bedingungen
[mm] $\nabla_{x} L(x^{*}, \mu^{*}) [/mm] = 0$
[mm] $g(x^{*}) [/mm] = 0$ (1)
erfüllen. Dieses System besteht aus $n + p$ Unbekannten und $n + p$ Gleichungen.
a) Zeigen Sie, dass die Iterationsvorschrift des Newton - Verfahrens zur Lösung des Systems (1) gegeben ist durch
[mm] $\begin{pmatrix}
\nabla^{2}_{x} L(x^{k}, \mu^{k}) & \nabla g(x^{k}) \\
\nabla g(x^{k})^{T} & 0 \\
\end{pmatrix} \cdot \left(\begin{array}{c}x^{ k + 1} - x^{k}\\ \mu^{k + 1} - \mu^{k}\end{array}\right) [/mm] = [mm] \left(\begin{array}{c}- \nabla_{x} L(x^{k}, \mu^{k})\\ - g(x^{k})\end{array}\right) \in \mathbb{R}^{n} \times \mathbb{R}^{p} [/mm] $,
wobei [mm] $(x^{k}, \mu^{k})$ [/mm] die aktuelle Iterierte bezeichnet für $k [mm] \in \mathbb{N}_{0}$.
[/mm]
b) Zeigen Sie, dass das Newton - Verfahren aus dem ersten Teil durchführbar ist, d.h.: Zeigen Sie, dass die im Newton - Vrfahren vorkommende Matrix invertierbar ist.
c) Seien nun [mm] $f(x_{1}, x_{2}) [/mm] = [mm] x_{1} [/mm] + [mm] x_{2} [/mm] $ und [mm] $g(x_{1}, x_{2}) [/mm] = [mm] x_{1}^{2} [/mm] + [mm] x_{2}^{2} [/mm] - 2$ gegeben.
Bestimmen Sie die Tupel [mm] $(x^{}, \mu^{})$ [/mm] als Lösung des Systems (1)$. |
Ich habe mir gestern Mittag die Aufgabe angeschaut, aber ich komme bei dieser Aufgabe überhaupt nicht, daher bräuchte ich Hilfe oder Tipps, damit ich auf einen Ansatz komme. Wäre euch dabei sehr dankbar.
Mir sind einige Sachen unklar, daher habe ich ein paar Fragen.
1. Frage
_______
Wir haben die Funktionen $f: [mm] \mathbb{R}^{n} \rightarrow \mathbb{R}$ [/mm] und
$g: [mm] \mathbb{R}^{n} \rightarrow \mathbb{R}^{p}$.
[/mm]
Ist $g$ ein Vektorfeld, dessen Komponenten die Nebenbedingungen sind, die die Funktion $f$ erfüllen muss?
Falls, das so ist, dann müssen die Komponenten des Vektors [mm] $\mu$ [/mm] die Lagrangemultiplikatoren sein.
Außerdem ist dann [mm] $\mu \in \mathbb{R}^{p}$, [/mm] sonst könnte man nicht das reelle Standardskalarprodukt [mm] $\mu^{T} [/mm] g(x)$ berechnen.
2. Frage
_______
Was meint man mit "mit der Eigenschaft, dass die zweite Ableitung (nach der ersten Komponente) der Lagrangefunktion $L$" ?
Es gibt doch keine Ableitung nach der ersten Komponente, sondern eine partielle Ableitung nach der ersten Komponente.
Oder wie ist das zu verstehen ?
Und mit [mm] $\nabla_{x} L(x^{*}, \mu^{*} [/mm] )$ meint man die erste Komponente des Gradienten $ [mm] L(x^{*}, \mu^{*} [/mm] )$ ?
3. Frage
_______
Was genau erreiche ich mit der Iterationsvorschrift
[mm] \begin{pmatrix}
\nabla^{2}_{x} L(x^{k}, \mu^{k}) & \nabla g(x^{k}) \\
\nabla g(x^{k})^{T} & 0 \\
\end{pmatrix} \cdot \left(\begin{array}{c}x^{ k + 1} - x^{k}\\ \mu^{k + 1} - \mu^{k}\end{array}\right) [/mm] = [mm] \left(\begin{array}{c}- \nabla_{x} L(x^{k}, \mu^{k})\\ - g(x^{k})\end{array}\right) [/mm] $ ?
Das habe ich nicht ganz verstanden.
Ich bräuchte zunächst ein Tipp bzw. einen Ansatz für die a), damit ich die Aufgabe bearbeiten kann. Mir fällt leider nichts dazu ein...
Die b) und c) sehen nicht so schwierig aus. Die bekomme ich vielleicht selber hin! Aber bei der a) habe ich, wie gesagt, keine Ahnung...
Bin froh über jede Hilfe.
Euer Nathan
|
|
| |
|
Hiho,
Tipp vorweg: [mm] $x^\*$ [/mm] machst du mit x^\*
> 1. Frage
> _______
> Ist [mm]g[/mm] ein Vektorfeld, dessen Komponenten die
> Nebenbedingungen sind, die die Funktion [mm]f[/mm] erfüllen muss?
Ja.
Wobei du von der Vorstellung als "Vektorfeld" wegkommen solltest. Dass das so notiert wird, liegt nur an der Übersichtlichkeit. Dazu gleich mehr.
>
> Falls, das so ist, dann müssen die Komponenten des Vektors
> [mm]\mu[/mm] die Lagrangemultiplikatoren sein.
Ja.
> Außerdem ist dann [mm]\mu \in \mathbb{R}^{p}[/mm], sonst könnte
> man nicht das reelle Standardskalarprodukt [mm]\mu^{T} g(x)[/mm]
> berechnen.
Ja.
Nochmal vereinfacht und zusammengefasst: Du möchtest also f(x) minimieren und hast (erstmal) eine Nebenbedingung [mm] $g_1(x)$, [/mm] die dazugehörige Lagrange-Funktion würde lauten:
[mm] $L(x,\mu_1) [/mm] = f(x) + [mm] \mu_1g_1(x)$
[/mm]
Nun kommt noch eine zweite Nebenbedingung [mm] $g_2(x)$ [/mm] hinzu, dann erhältst du als Lagrange-Funktion:
[mm] $L(x,\mu_1,\mu_2) [/mm] = f(x) + [mm] \mu_1g_1(x) [/mm] + [mm] \mu_2g_2(x)$
[/mm]
Nun haben wir insgesamt $p$ Nebenbedingungen und bekommen entsprechend:
[mm] $L(x,\mu_1,\ldots,\mu_p) [/mm] = f(x) + [mm] \underbrace{\sum_{k=1}^p \mu_kg_k(x)}_{\mu^Tg(x)} [/mm] = f(g) + [mm] \mu^Tg(x) [/mm] = [mm] L(x,\mu)$ [/mm]
mit [mm] $\mu [/mm] = [mm] \vektor{\mu_1 \\ \vdots \\ \mu_p}$ [/mm] und $g(x) = [mm] \vektor{g_1(x) \\ \vdots \\ g_p(x)}$
[/mm]
> 2. Frage
> _______
>
>
> Was meint man mit "mit der Eigenschaft, dass die zweite
> Ableitung (nach der ersten Komponente) der Lagrangefunktion
> [mm]L[/mm]" ?
>
> Es gibt doch keine Ableitung nach der ersten Komponente,
> sondern eine partielle Ableitung nach der ersten
> Komponente.
>
> Oder wie ist das zu verstehen ?
Natürlich gibt es eine Ableitung der ersten Komponente.
Definiere für ein festes [mm] $\mu$ [/mm] einfach [mm] $h_\mu(x) [/mm] := [mm] L(x,\mu)$, [/mm] dann ist h: [mm] $\IR^n \to \IR$ [/mm] und ich kann doch die Ableitung von $h$ bilden, was dann mit $Dh(x)$ bezeichnet wird und einfach die Jacobi-Matrix darstellt.
Die zweite Ableitung von h wäre dann $D^2h(x)$ aka die Hesse-Matrix.
> Und mit [mm]\nabla_{x} L(x^{*}, \mu^{*} )[/mm] meint man die erste
> Komponente des Gradienten [mm]L(x^{*}, \mu^{*} )[/mm] ?
Hm nein.
Man meint den Gradienten, wenn man nur x als variabel betrachtet und [mm] $\mu$ [/mm] fix ist.
Also mit obiger Notation ist [mm] $\nabla_{x} L(x^{\*}, \mu^{\*} [/mm] ) = [mm] \nabla h_{\mu^\*}(x)$
[/mm]
> 3. Frage
> _______
> Was genau erreiche ich mit der Iterationsvorschrift
>
> [mm]\begin{pmatrix}
\nabla^{2}_{x} L(x^{k}, \mu^{k}) & \nabla g(x^{k}) \\
\nabla g(x^{k})^{T} & 0 \\
\end{pmatrix} \cdot \left(\begin{array}{c}x^{ k + 1} - x^{k}\\ \mu^{k + 1} - \mu^{k}\end{array}\right)[/mm]
> = [mm]\left(\begin{array}{c}- \nabla_{x} L(x^{k}, \mu^{k})\\ - g(x^{k})\end{array}\right)[/mm]
> $ ?
Das ist einfach das Newton-Verfahren um obiges Problem (1) zu lösen.
Dass das aber so ist, sollst du in a) zeigen.
Also gehe nun wie folgt vor:
1.) In (1) geht es ja darum die Nullstelle einer bestimmten Funktion bestimmen (welcher?).
Die kannst du bekanntlich mit dem Newton-Verfahren machen.
Wie sieht das Newton-Verfahren in diesem Fall erst mal aus?
2.) Zeige durch Umformen, dass das in 1.) aufgestellte Verfahren der Gleichung in a) genügt.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:45 Sa 11.01.2020 | | Autor: | NathanR |
Hallo 
Okay, ich fasse nochmal die Voraussetzungen für mich zusammen, damit ich einen besseren Überblick habe.
________________________________________________________________________________________________________________________________________________________
Seien $n, p [mm] \in \mathbb{N}$ [/mm] mit $ p < n$.
Dazu seien noch $f: [mm] \mathbb{R}^{n} \rightarrow \mathbb{R}, (x_{1}, \ldots, x_{n}) \mapsto f(x_{1}, \ldots, x_{n})$ [/mm] und $g: [mm] \mathbb{R}^{n} \rightarrow \mathbb{R}^{p}, (x_{1}, \ldots, x_{n}) \mapsto g(x_{1}, \ldots, x_{n}) [/mm] = [mm] \left(\begin{array}{c}g_{1} (x_{1}, \ldots, x_{n})\\ \vdots \\ g_{p} (x_{1}, \ldots, x_{n})\end{array}\right)$ [/mm] glatte Funktionen.
Dabei sind die Komponenten [mm] $g_{i}(x_{1}, \ldots, x_{n})\quad [/mm] (i = 1, [mm] \ldots, [/mm] p)$ die Nebenbedingungen (die schon nach 0 umgestellt sind ? ) , die die Funktion $f$ erfüllen muss.
Diese Funktionen erfüllen die Eigenschaft, dass die zwweite Ableitung (nach der ersten Komponente) der Lagrangefunktion
$L: [mm] \mathbb{R}^{n} \times \mathbb{R}^{p} \rightarrow \mathbb{R}, (x_{1}, \ldots, x_{n}, \mu_{1}, \ldots, \mu_{p}) \mapsto L(x_{1}, \ldots, x_{n}, \mu_{1}, \ldots, \mu_{p}) [/mm] = [mm] f(x_{1}, \ldots, x_{n}) [/mm] + [mm] (\mu_{1}, \ldots \mu_{p}) \cdot\left(\begin{array}{c}g_{1} (x_{1}, \ldots, x_{n})\\ \vdots \\ g_{p} (x_{1}, \ldots, x_{n})\end{array}\right)$
[/mm]
positiv definit auf dem Kern von $g'$ ist.
________________________________________________________________________________________________________________________________________________________
> Natürlich gibt es eine Ableitung der ersten Komponente.
> Definiere für ein festes [mm]\mu[/mm] einfach [mm]h_\mu(x) := L(x,\mu)[/mm],
> dann ist h: [mm]\IR^n \to \IR[/mm] und ich kann doch die Ableitung
> von [mm]h[/mm] bilden, was dann mit [mm]Dh(x)[/mm] bezeichnet wird und
> einfach die Jacobi-Matrix darstellt.
>
> Die zweite Ableitung von h wäre dann [mm]D^2h(x)[/mm] aka die
> Hesse-Matrix.
Wenn ich das bei dir richtig verstanden habe, meint man mit Komponenten die Vektoren $x$ und [mm] $\mu$. [/mm] Und wenn man nach der ersten Komponente ableitet, dann behandelt man die Variablen [mm] $\mu_{1}, \ldots, \mu_{p}$ [/mm] wie zahlen und man betrachtet nur noch die Funktion, die von den Veränderlichen [mm] $x_{1}, \ldots, x_{n}$ [/mm] abhängt.
Aber von dieser Funktion kann man doch nicht die Jacobi - Matrix bilden, sondern den Gradienten. Oder sagt man dafür auch Jacobi - Matrix, weil der Gradient ist ein Spezialfall der Jacobi - Matrix ist?
> Das ist einfach das Newton-Verfahren um obiges Problem (1)
> zu lösen.
> Dass das aber so ist, sollst du in a) zeigen.
>
> Also gehe nun wie folgt vor:
>
> 1.) In (1) geht es ja darum die Nullstelle einer bestimmten
> Funktion bestimmen (welcher?).
> Die kannst du bekanntlich mit dem Newton-Verfahren machen.
> Wie sieht das Newton-Verfahren in diesem Fall erst mal
> aus?
Verzeihe mir, wenn ich Quatsch erzähle.
Beim Newton - Verfahren im [mm] $\mathbb{R}^{1}$ [/mm] geht es darum, die Nullstellen einer Funktion [mm] $f:\mathbb{R} \rightarrow \mathbb{R}, [/mm] x [mm] \mapsto [/mm] f(x)$ approximativ zu bestimmen.
Die Iteration ist gegeben durch [mm] $x_{t + 1} [/mm] = [mm] x_{t} [/mm] - [mm] \frac{f(x_{t})}{f'(x_{t})}$.
[/mm]
Und beim Newton - Verfahren im [mm] $\mathbb{R}^{n}$ [/mm] geht es darum, die Nullstellen einer Funktion [mm] $f:\mathbb{R}^{n} \rightarrow \mathbb{R}, [/mm] x [mm] \mapsto [/mm] f(x)$ approximativ zu bestimmen.
Die Iteration ist gegeben durch [mm] $x^{t + 1} [/mm] = [mm] x^{t} [/mm] - [mm] f(x^{t}) \cdot Jac_{f}(x^{t})^{- 1}$.
[/mm]
Ich frage mich nur, was diese Iteration mit den Bedingungen
[mm] $\nabla_{x} L(x^{*}, \mu^{*}) [/mm] = 0$
[mm] $g(x^{*}) [/mm] = 0$
zu tun hat.
> 2.) Zeige durch Umformen, dass das in 1.) aufgestellte
> Verfahren der Gleichung in a) genügt.
Heißt das, dass ich die Iteration [mm] $x^{t + 1} [/mm] = [mm] x^{t} [/mm] - [mm] f(x^{t}) \cdot Jac_{f}(x^{t})^{- 1}$ [/mm] für die Umformung benötige ?
Viele Grüße,
Nathan
|
|
|
| |
|
Hiho,
> Dabei sind die Komponenten [mm]g_{i}(x_{1}, \ldots, x_{n})\quad (i = 1, \ldots, p)[/mm]
> die Nebenbedingungen (die schon nach 0 umgestellt sind ? )
Ja.
> Wenn ich das bei dir richtig verstanden habe, meint man mit
> Komponenten die Vektoren [mm]x[/mm] und [mm]\mu[/mm].
Offensichtlich, wenn die Funktion [mm] $L(x,\mu)$ [/mm] lautet.
> Und wenn man nach der
> ersten Komponente ableitet, dann behandelt man die
> Variablen [mm]\mu_{1}, \ldots, \mu_{p}[/mm] wie zahlen und man
> betrachtet nur noch die Funktion, die von den
> Veränderlichen [mm]x_{1}, \ldots, x_{n}[/mm] abhängt.
Korrekt.
> Aber von dieser Funktion kann man doch nicht die Jacobi -
> Matrix bilden, sondern den Gradienten. Oder sagt man dafür
> auch Jacobi - Matrix, weil der Gradient ist ein Spezialfall
> der Jacobi - Matrix ist?
Also ja, du kannst den Gradienten bilden und es wäre wohl besser gewesen hier vom Gradienten zu sprechen.
Der entspricht für den Fall einer reellwertigen Funktion aber gerade der (transponierten) Jakobi-Matrix.
> Beim Newton - Verfahren im [mm]\mathbb{R}^{1}[/mm] geht es darum,
> die Nullstellen einer Funktion [mm]f:\mathbb{R} \rightarrow \mathbb{R}, x \mapsto f(x)[/mm] approximativ zu bestimmen.
Korrekt.
>
>
> Die Iteration ist gegeben durch [mm]x_{t + 1} = x_{t} - \frac{f(x_{t})}{f'(x_{t})}[/mm].
Korrekt.
> Und beim Newton - Verfahren im [mm]\mathbb{R}^{n}[/mm] geht es
> darum, die Nullstellen einer Funktion [mm]f:\mathbb{R}^{n} \rightarrow \mathbb{R}, x \mapsto f(x)[/mm] approximativ zu bestimmen.
Ich denke ihr habt eher nur das Newton-Verfahren für [mm]f:\mathbb{R}^{n} \rightarrow \mathbb{R}^n[/mm] definiert.
Denn nur dann ist die Jakobi-Matrix quadratisch und der Ausdruck [mm] $Jac_f^{-1}$ [/mm] macht überhaupt Sinn!
Und um eine Verwechslung mit obigem $f$ zu vermeiden, nenne ich die Funktion mal $N: [mm] \IR^n \to \IR^n$.
[/mm]
> Die Iteration ist gegeben durch [mm]x^{t + 1} = x^{t} - f(x^{t}) \cdot Jac_{f}(x^{t})^{- 1}[/mm].
Hier schreibst du die Indizes plötzlich oben, davor unten?
Um eine Verwechslung mit den Komponenten von $x$ zu vermeiden? (Wäre verständlich)
Wir sollten uns nur auf eins einigen 
Und das Produkt $f [mm] \cdot Jac_f^{-1}$ [/mm] sollte wohl eher [mm] $Jac_f^{-1} \cdot [/mm] f$ lauten.
Dann lautet die Iterationsvorschrift also nach obigem (mit N statt f um Verwechslungen zu vermeiden und Schritt-Indizes oben):
[mm] $x^{t+1} [/mm] = [mm] x^t [/mm] - [mm] Jac_N^{-1} (x^t) \cdot N(x^t)$
[/mm]
> Ich frage mich nur, was diese Iteration mit den Bedingungen
> [mm]\nabla_{x} L(x^{*}, \mu^{*}) = 0[/mm]
>
> [mm]g(x^{*}) = 0[/mm]
> zu tun hat.
Na nun definiere doch mal: [mm] $N(x,\mu) [/mm] = [mm] (\nabla_{x} [/mm] L(x, [mm] \mu), [/mm] g(x))$
Dann ist [mm] $N:\IR^{n+p} \to \IR^{n+p}$ [/mm] und es gilt eine Nullstelle von $N$ zu finden… dafür kennst du nun ein Verfahren…
> > 2.) Zeige durch Umformen, dass das in 1.) aufgestellte
> > Verfahren der Gleichung in a) genügt.
>
>
> Heißt das, dass ich die Iteration [mm]x^{t + 1} = x^{t} - f(x^{t}) \cdot Jac_{f}(x^{t})^{- 1}[/mm] für die Umformung benötige ?
Das Verfahren benötigst du, ja… stelle doch jetzt mal die Iteration für das Newton-Verfahren für $N$ auf (sofern du verstanden hast, wieso eine Nullstelle von N das Problem löst)
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:50 So 12.01.2020 | | Autor: | NathanR |
Hallo, danke für den Tipp. Ich bearbeite jetzt mal die Aufgabe noch einmal und hoffentlich kommt was dabei heraus
Eine Frage nur: Was meinst du genau mit $N(x, [mm] \mu) [/mm] = [mm] (\nabla_{x} [/mm] L(x, [mm] \mu), [/mm] g(x))$ ?
Die Schreibweise mit den Klammern erinnert mich an das Skalarprodukt. Aber wenn das so wäre, dann würde $N$ nicht von [mm] $\mathbb{R}^{n + p}$ [/mm] nach [mm] $\mathbb{R}^{n + p}$ [/mm] abbilden.
lg, Nathan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:30 So 12.01.2020 | | Autor: | Gonozal_IX |
Hiho,
> Eine Frage nur: Was meinst du genau mit [mm]N(x, \mu) = (\nabla_{x} L(x, \mu), g(x))[/mm]
ich habe das ^T vergessen…
Also korrekt wäre: $N(x, [mm] \mu) [/mm] = [mm] \vektor{\nabla_{x} L(x, \mu) \\ g(x)}$
[/mm]
Es ist [mm] $\nabla_{x} [/mm] L(x, [mm] \mu) \in \IR^n, [/mm] g(x) [mm] \in \IR^p$, [/mm] damit ist $L [mm] \in \IR^{n+p}$
[/mm]
Gruß
Gono
|
|
|
|
