Forum:  Numerik & Optimierung
Thema: Minimierung Normalenkegel
Themen-Übersicht
favoritemathhoe
Aktiv
Dabei seit: 09.11.2015
Mitteilungen: 87
Aus:
Themenstart: 2019-11-26 18:59

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 :)


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2671
Aus: der Nähe von Schwerin
Beitrag No.1, eingetragen 2019-11-27 11:26

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 :)


favoritemathhoe
Aktiv
Dabei seit: 09.11.2015
Mitteilungen: 87
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2019-11-27 13:04

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?


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2671
Aus: der Nähe von Schwerin
Beitrag No.3, eingetragen 2019-11-27 13:16

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*}.
\]


favoritemathhoe
Aktiv
Dabei seit: 09.11.2015
Mitteilungen: 87
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2019-11-27 16:51




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


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2671
Aus: der Nähe von Schwerin
Beitrag No.5, eingetragen 2019-11-27 17:59

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.


favoritemathhoe
Aktiv
Dabei seit: 09.11.2015
Mitteilungen: 87
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2019-11-27 18:49

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?


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2671
Aus: der Nähe von Schwerin
Beitrag No.7, eingetragen 2019-11-27 19:47


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?


favoritemathhoe
Aktiv
Dabei seit: 09.11.2015
Mitteilungen: 87
Aus:
Beitrag No.8, vom Themenstarter, eingetragen 2019-11-27 20:35

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)


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2671
Aus: der Nähe von Schwerin
Beitrag No.9, eingetragen 2019-11-27 20:57

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


favoritemathhoe
Aktiv
Dabei seit: 09.11.2015
Mitteilungen: 87
Aus:
Beitrag No.10, vom Themenstarter, eingetragen 2019-11-27 21:06

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}


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2671
Aus: der Nähe von Schwerin
Beitrag No.11, eingetragen 2019-11-27 21:23

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.


favoritemathhoe
Aktiv
Dabei seit: 09.11.2015
Mitteilungen: 87
Aus:
Beitrag No.12, vom Themenstarter, eingetragen 2019-11-27 21:59

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?


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2671
Aus: der Nähe von Schwerin
Beitrag No.13, eingetragen 2019-11-27 22:25

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.


favoritemathhoe
Aktiv
Dabei seit: 09.11.2015
Mitteilungen: 87
Aus:
Beitrag No.14, vom Themenstarter, eingetragen 2019-11-27 22:49



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.


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2671
Aus: der Nähe von Schwerin
Beitrag No.15, eingetragen 2019-11-28 13:43

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?




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=244583=110
Druckdatum: 2020-02-23 14:30