Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Optimierungsproblem
Druckversion
Druckversion
Autor
Universität/Hochschule J Optimierungsproblem
hanuta2000
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.05.2020
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-06-03


Hi, ich hab folgende Aufgabe und komme nicht ganz weiter:
Gegeben ist eine diffbare, nichtlineare (nicht notwendig konvexe) Zielfunktion mit einem LGS als Nebenfunktion:
\(min f(x), x \in \mathbb{R}^n \)
\(s.t. Ax=b \)
Dabei ist \(A \in \mathbb{R}^{m x n} , b \in \mathbb{R}^m , n \geq m \)
ZZ: Ist \(x^*\) ein Minimierer, dann existiert ein \(\lambda \) mit
\(\nabla f(x^*) + A^T \lambda = 0 \)
Hinweis: Nutze Variationsungleichung, also \(\nabla f(x^*)(x-x^*) \geq 0
 \forall x \in \mathbb{R}^n\) und die Beziehung \( orth(kernA)=Bild A^T \)
orth ist das orthogonale Komplement (wie drehe ich das T?)
Ich bin dankbar für jeden Hinweis



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.12.2009
Mitteilungen: 650
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-06-03


Hallo hanuta2000,

die Variationsungleichung ist so nicht richtig. Sie gilt nur für alle zulässigen Richtungen:

Bezeichne <math>C := \{x: \; Ax=b\}</math>, so gilt die Variationsungleichung
<math>\nabla f(x^\ast)h \geq 0</math> für alle <math>h \in T_C(x^\ast)</math> wobei <math>T_C(x^\ast)</math> den Tangentialkegel bezeichnet.

Einfacher dürfte es aber gehen, wenn man hier den Normalenkegel verwendet, was einfach nur der polare Kegel zum Tangentialkegel ist. Hier gilt nun <math>-\nabla f(x^\ast) \in N_C(x^\ast)</math>


Stelle einfach mal diese beiden Kegel auf und betrachte sie weiter.



Tipp: Deine zu zeigende Gleichung lässt sich umstellen zu <math>-\nabla f(x^\ast) = A^T \lambda</math> oder <math>-\nabla f(x^\ast) \in Bild(A^T)</math>.



P.S. Das orthogonale Komplement kannst du mit \perp verwenden: <math>kern(A)^\perp</math>


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hanuta2000
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.05.2020
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-06-03


Danke schonmal!
Also in der Aufgabe wird auf diese Ungleichung verwiesen, die genauso im Skript steht. Das mit den Kegeln hatten wir so nie, würde deshalb ungerne so argumentieren. Aber dass \( - \nabla f(x^*) \in Bild A^T \) ist, ist schon Mal eine Erkenntnis. Ich probiere mich morgen weiter daran und melde mich dann sicher noch Mal.

Danke dir



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hanuta2000
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.05.2020
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-06-04


Hallo nochmal:
also was ich ja eigentlich tun muss ist zu zeigen, dass
\( - \nabla f(x^*) \in Bild A^T = kern A^\perp \). Dh ich muss zeigen dass \( \forall u \in kernA: \langle- \nabla f(x^*),u\rangle = 0 \)
Da muss ich ja jetzt scheinbar die Variationsungleichung nutzen. Ich weiß allerdings nicht wie mir die dabei hilft und außerdem sagtest du ja, dass die so wie ich sie geschrieben habe falsch ist (wieso? im Skript steht sie so).

LG



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.12.2009
Mitteilungen: 650
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-06-04


Hallo,

nur ganz kurz: Wenn du die Variationsungleichung so verwendest wie du sie hast, ignorierst du die Nebenbedingung <math>Ax=b</math>.
Diese verwurstelt man in den sog. zulässigen Richtungen.

Betrachte z.b. das einfache eindimensionale Problem <math>min \; x</math> unter der Nebenbedingung <math>x \geq 0</math>. Dies ist ein Spezialfall von deinem Problem.

Das Minimum ist offenbar <math>x^\ast=0</math>, aber deine Variationsungleichung
<math>\nabla f(x^\ast)(x-x^\ast) = 1 \cdot (x - 0) = x \geq 0  \; \; \forall x \in  \IR</math>

gilt offenbar nicht. Dies liegt daran, da z.B. die "Richtung" <math>x = -1</math> "aus der zulässigen Menge an der Stelle <math>x^\ast=0</math> herauszeigt". Konkret wird dies eben durch den sog. Tangentialkegel realisiert.


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2159
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-06-04


Hallo,

wenn man den Hinweis einfach ignoriert, folgt die Aussage aus der Multiplikatorregel von Lagrange (lernt man meistens in Analysis 2).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hanuta2000
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.05.2020
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-06-04


Dann weiß ich leider nicht wieso gesagt wird dass ich diese Variationsgleichung nutzen soll..

Hab mir gerade die Multiplikatorregel angeschaut: Es gilt also
\( \nabla f(x^*)=\lambda \nabla(Ax^*-b) \) aber diese Regeln gilt doch nur wenn der Gradient rechts für \( x^* \neq 0\) ist, so wie ich das gelesen habe, aber \(Ax^* \) ist ja eben =b, also ist der Gradient 0
Oder hab ich gerade einen Denkfehler?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2159
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-06-04

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
2020-06-04 14:00 - hanuta2000 in Beitrag No. 6 schreibt:
Hab mir gerade die Multiplikatorregel angeschaut: Es gilt also
\( \nabla f(x^*)=\lambda \nabla(Ax^*-b) \) aber diese Regeln gilt doch nur wenn der Gradient rechts für \( x^* \neq 0\) ist, so wie ich das gelesen habe, aber \(Ax^* \) ist ja eben =b, also ist der Gradient 0
Oder hab ich gerade einen Denkfehler?
Erst Ableiten, dann einsetzen. Außerdem hast du die Gleichung sowieso falsch übernommen (der Ausdruck $\nabla(Ax^*-b)$ ergibt keinen Sinn, da das Bild der Abbildung $x\mapsto Ax-b$ nicht in $\IR$ liegt).

Die Gleichung $Ax=b$ ist äquivalent zu $m$ Nebenbedingungen:
Wenn $A_1,\ldots, A_m$ die Zeilen der Matrix $A$ sind, dann muss $A_ix=b_i$ für $i=1,\ldots, m$ gelten.
Die Lagrange-Funktion ist also $\Lambda(x,\lambda) = f(x) + \sum_{i=1}^m\lambda_i (A_ix-b_i) = f(x) + \lambda^T (Ax-b)$.
Wenn du $\Lambda$ nach $x$ ableitest, dann ergibt sich aus $\frac \partial {\partial x}\Lambda(x^*,\lambda) = 0$ die Behauptung.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hanuta2000
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.05.2020
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-06-04


Vielen Dank!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.12.2009
Mitteilungen: 650
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-06-04


Okay, ich habe noch mal über meinen Tangentialkegel nachgedacht und man muss hier nicht so starke Geschütze auffahren.

Man beachte, dass die Menge <math>C:=\{x: Ax=b\}</math> abgeschlossen und konvex ist. Dann kann man einen Satz aus deiner Vorlesung verwenden und erhält für das Optimierungproblem

<math>min \; f(x)</math> s.t. <math>x\in C</math>

die Variationsungleichung

<math>\nabla f(x^\ast) (x - x^\ast) \geq 0</math> für alle <math>x \in C</math>

(Wenn deine VI mit <math>\forall x \in \IR^n</math> im Skript steht, ist sie in diesem Kontext falsch)


Jetzt nutzen wir aus, das <math>C</math> ein affiner Unterraum ist und schreiben

<math>C := \{x_0 + v: \; Av = 0\}</math> für ein <math>x_0 \in C</math>.

Das setzen wir in die VI ein und erhalten mit <math>x_0 = x^\ast</math>

<math>\nabla f(x^\ast) v \geq 0</math> für alle <math>v \in kern(A)</math>

Weiter ist <math>kern(A)</math> ein Unterraum, d.h. das wiederrum ist äquivalent zu

<math>\nabla f(x^\ast) v = 0</math> für alle <math>v \in kern(A)</math>

Von hier aus kommst du denke ich selber weiter.

Viele Grüße





Edit: Für alle Interessierten: Man kann das natürlich auch mit der allgemeinen Theorie aus meinen ersten Post erschlagen.

Der Tangentialkegel ist gegeben als
<math>T_C(x) := \{ d: \; \exists \tau_i \to 0, \tau_i > 0, \{x_i\} \subset C, \; \tau^{-1}(x_i-x) \to d  \}</math>

Unsere Menge <math>C</math> ist wie oben <math>C:=\{x: \; Ax=b\}</math>. Im Allgemeinen ist der Tangentialkegel schwer bis gar nicht explizit zu berechnen - dafür gibt es dann Konstrukte wie den linearisierten Tangentialkegel. Hier aber ist es möglich und man erhält

<math>T_C(x^\ast) = kern(A)</math>

Nach der allgemeinen Theorie ist unsere VI ja gegeben durch

<math>\nabla f(x^\ast) h \geq 0 \; \forall h \in T_C(x^\ast)</math>

bzw

<math>\nabla f(x^\ast) h \geq 0 \; \forall h \in kern(A)</math>

was genau unser Ergebnis von oben ist.


Edit 2: Wer möchte kann ja mal den Normalenkegel bestimmen. Man erhält <math>N_C(x^\ast) = kern(A)^\perp</math> und damit direkt <math>-\nabla f(x^\ast) \in N_C(x^\ast) = Bild(A)</math> nach der allgemeinen Theorie.


Viele Grüße


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hanuta2000
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.05.2020
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2020-06-05


Dankeschön, tatsächlich bin ich gerade eben noch auf diese Lösung gekommen, allerdings war ich mir nicht ganz sicher, warum kernA als Unterraum dafür sorgt, dass dann Gleichheit folgt.
Wie kann ich mir das erklären?
LG



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.12.2009
Mitteilungen: 650
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-06-05


2020-06-05 10:44 - hanuta2000 in Beitrag No. 10 schreibt:
Dankeschön, tatsächlich bin ich gerade eben noch auf diese Lösung gekommen, allerdings war ich mir nicht ganz sicher, warum kernA als Unterraum dafür sorgt, dass dann Gleichheit folgt.
Wie kann ich mir das erklären?
LG

Hallo,

welche Eigenschaften hat denn ein Unterraum?


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hanuta2000
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.05.2020
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2020-06-05


Der Unterraum ist nicht leer, \( \forall u,v \in kernA\) ist \(u+v \in kernA\) und für \(\alpha \in \mathbb{R}: \alpha u \in kernA\)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2159
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-06-05

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Für die Gleichheit in der Ungleichung brauchst du, dass wenn $v$ im Kern liegt, dann auch $-v$.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hanuta2000
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.05.2020
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2020-06-05


Jo alles klar, habs verstanden. Danke dir für deine Hilfe!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hanuta2000 hat die Antworten auf ihre/seine Frage gesehen.
hanuta2000 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  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]