Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Minimierung Normalenkegel
Druckversion
Druckversion
Autor
Universität/Hochschule J Minimierung Normalenkegel
favoritemathhoe
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.11.2015
Mitteilungen: 87
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-11-26


Guten Abend,

ich komme bei der folgenden Aufgabe leider nicht weiter und vielleicht kann mir ja hier jemand helfen :)

Minimieren Sie die quadratische Funktion q(x)=xQx mit x aus R^2 und Q =
 \[
  \left( {\begin{array}{cc}
   2 & 1 \\
   1 & 2 \\
  \end{array} } \right)
\]  über verschiedene Bereiche beschrieben durch X = \(\{x \in \mathbb{R}^2 : Ax\leq b\} \). Dabei ist A =
 \[
  \left( {\begin{array}{cc}
   1 & 0 \\
   0 & 1 \\
-1 & -1 \\
  \end{array} } \right)
\]. Die verschiedenen bereiche sind gegeben durch b1= (-1,-1,3)^T, b2=(-1,1,3)^T und b3=(1,1,3)^T.
Argumentieren Sie mit dem Normelnkegel im jeweiligen Optimalpunkt. Warum ist dieser Punkt eindeutig?


Ich habe dann alles nochmals anders hingeschrieben, also z.B. für b1:
Minimiere 2x^2+2xy+2y^2 unter den Bed
x<=-1, y<=-1, -x-y<=3.

Jetzt weiß ich allerdings nicht weiter, wie soll ich mit dem Normalenkegel argumentieren?


Schon mal vielen Dank für alle Antworten :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2863
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-11-27


Hallo,

ich glaube, dein $Q$ ist symmetrisch, also \[Q=\begin{pmatrix}2&1\\1&2\end{pmatrix}.\] Kannst du deine Bereiche $X$ mal zeichnen. Es wird sich wahrscheinlich um Dreiecke handeln :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
favoritemathhoe
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.11.2015
Mitteilungen: 87
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-11-27


Vielen Dank für die Antwort :)
Jja, Q ist symmetrisch, das war ein Tippfehler..
Und ja, es handelt sich um ein Dreieck. Damit kann ich dann ja auch das Minimum bestimmen (einer der Eckpunkte oder?)
Aber was hat das dann mit dem Normalenkegel zu tun?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2863
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-11-27


Das klären wir gleich. Kannst du trotzdem bitte deinen ersten Beitrag ändern und die Dreiecke zeichnen?

Vielleicht ist es sinnvoll andere Koordianten einzuführen. Setze beispielsweise
\[
\begin{align*}
y_1 &:=\sqrt 2\cdot x_1 + \frac 12\sqrt 2\cdot x_2\\
y_2 &:= \frac 12\sqrt 6\cdot x_2\\
\end{align*}.
\]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
favoritemathhoe
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.11.2015
Mitteilungen: 87
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-11-27





Hier ist es gezeichnet. Im Fall von b1 wäre z.B. das Minimum bei (-1,-1).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2863
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-11-27


Es scheint etwas nicht zu stimmen :/

Die  Normalenvektoren der Facetten aud der Aufgabe sind jeweils $(1,0)$, $(-1,1)$ und $(-1,-1)$. Die im Bild sind aber $(1,0)$, $(0,1)$ und $(-1,-1)$. Magst du entweder das Bild noch einmal ändern oder die Aufgabenstellung korrigieren?

Wie gesagt, glaube ich auch, dass eine Koordiantentransformation hilfreich ist.

So ist
\[2x_1^2+2x_1x_2+2x_2^2=2\left(x_1+\frac 12 x_2\right)^2 + \frac 32 x_2^2.\]
An den Normalenkegeln kannst du sehen, in welche Richtungen du nicht mehr gehen kannst.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
favoritemathhoe
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.11.2015
Mitteilungen: 87
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-11-27


Es tut mir leid, in der Aufgabenstellung war noch ein Fehler (jetzt behoben). Das Bild passte so.
Die Minima liegen bei 6 (P(-1,-1)), 3/2 (P(-1,1/2)) und 0 (P(0,0)).

Was soll mir die Koordinatentransformation an dieser Stelle bringen? Könnte ich nicht jetzt mit den gegebenen Punkten argumentieren?
Wie würde der Normalenkegel ausgehend vom Punkt P(-1,-1) aussehen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2863
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-11-27



Was soll mir die Koordinatentransformation an dieser Stelle bringen?
Mach es doch erstmal und dann schauen wir weiter, ob es etwas gebracht hat.


 Könnte ich nicht jetzt mit den gegebenen Punkten argumentieren?
Wie würde der Normalenkegel ausgehend vom Punkt P(-1,-1) aussehen?
Ja, das geht auch. Wie habt ihr denn Normalenkegel definiert?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
favoritemathhoe
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.11.2015
Mitteilungen: 87
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-11-27


Der Normalenkegel ist bei uns definiert als der polare Kegel des Radialkegels.

Also im Fall b3 ist es {0},
im Fall b2 eine Grade und
im Fall b1 geht der Normalenkegel von P(-1,-1) wie die Lösungsmenge gespiegelt auf der anderen Seite weg.. (ich weiß, fürchterlich ausgedrückt)..

Für b1 heißt das also, dass es keine bessere Lösung geben kann, für b2 und b3, dass eine bessere Lösung nicht mehr im Lösungsbereich läge (also auch nicht existent)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2863
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-11-27


Kannst du dann auch nochmal die Definition des Radialkegels und des polaren Kegels beschreiben? Irgendetwas scheint wieder nicht ganz zu stimmen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
favoritemathhoe
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.11.2015
Mitteilungen: 87
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-11-27


Normalenkegel von X in x: N_x(X) = K_x(X)°
Radialkegel: K_x(X) = cone(X-{x})
Polarer Kegel: K°={y aus R^n : <y,x> <= 0 für alle x aus K}



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2863
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-11-27


Das sieht gut aus :) Was sind also die Radialkegel der Ecken der Dreiecke und was sind die Normalenkegel? Versuche es mal in Gleichungen hinzuschreiben.

Und eigentlich fände ich es doch cooler, wenn du die Koordinaten transformierst. Dann siehst du mehr.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
favoritemathhoe
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.11.2015
Mitteilungen: 87
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2019-11-27


Der Radialkegel der drei Punkte ist jeweils der Kegel der ausgehend von dem Punkt in Richtungen der zulässigen Lösungen ausdehnt, also
in b1 genau entlang der zwei Grenzen des zulässigen Bereichs
in b2 wird er durch die Grade x<=-1 begrenzt
in b3 liegt er komplett um den Punkt drumherum, weswegen hier der Normalenkegel auch {0} ist

Der Normalenkegel zeigt von diesen Punkten aus weg von der zulässigen Menge. Also für b1 ist es der Radialkegel gespiegelt an P(-1,-1) und für b2 eine gerade ausgehend von P(1,1/2) parallel zur x-Achse..

Ich frage mich wie ich im Fall b1 und b2 mit diesen Infos jetzt begründen soll, dass der Punkt eindeutig ist... weil er der einzige Berührungspunkt der möglichen Lösungen an der Grenze der nicht mehr möglichen Lösungen ist?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2863
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-11-27


Das stimmt so nicht. Das, was du beschreibst, sind zum Teil nicht mal Kegel. Kannst du die Normalenkegel bitte zeichnen? Oder mit Gleichungen beschreiben?

Bei deiner Begründung, warum die minimierenden Punkte die minimierenden Punkte sind, musst du auch irgendwie auf das quadratische Zielfunktional eingehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
favoritemathhoe
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.11.2015
Mitteilungen: 87
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2019-11-27




So würde ich die Normalenkegel im Fall b1 (blau) und b2 grün zeichnen.. wenns das nicht ist hab ich absolut keinen Plan mehr.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2863
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2019-11-28


Die Normalenkegel (ebenso wie die Radialkegel) haben ihre Spitze immer in der Null, ansonsten wären sie auch gar keine Kegel.

Wie hast du deine Optima berechnet?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
favoritemathhoe hat die Antworten auf ihre/seine Frage gesehen.
favoritemathhoe 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]