Nichtlineare Optimierung

Neue Frage »

toasten Auf diesen Beitrag antworten »
Nichtlineare Optimierung
Hi,

wir haben gerade das Thema "Nichtlineare Optimierung" angefangen. Leider sehe ich noch nicht so ganz durch :-(

Folgend meine Aufgabe:


wobei

Ich soll (ohne Beweis) eine Optimallösung angeben.
Zudem soll ich noch den Tangentialkegel und den linearisierten Kegel bestimmen, wobei die zulässige Menge des Problems ist.


habe ich probiert graphisch zu ermitteln. Für haben die Graphen der Nebenbedingungen ihren Schnittpunkt bei (1, -1).
Würde die Aufgabe also heißen, wäre .
Da in dem Problem allerdings ein Minus steht, schlussfolgere ich .
Kann ich das so machen?

Leider habe ich auch keine Idee, wie ich die beiden Kegel beschreiben kann. :-(

Vielen Dank für eure Hilfe.

Grüße
toasten
tigerbine Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Die Zielfunktion sagt: mache x1 so groß wie möglich. Wie groß ist ist? Ist gamma fest? 0 oder 1?







Die Lösung ist also für gamma gleich 1, x*=1, mit f(x*)=-1.

Der Linearisierte Kegel ist einfacher zu bestimmen.Wie lautet die Definition? Da kommen Gradienten drin vor.



Leider kann ich Flächen hier nicht ausmalen. Vielleicht kommst du auch so drauf, wie hier der linearisierte Kegel aussieht. Der sollte einen dann auch für den Tangentialkegel inspirieren. Die Defintion ist was unhandlich, aber zeichnerisch lässt der sich hier gut bestimmen.

Für gamma gleich 0 besteht die zulässige Menge nur aus einem Punkt, hier (0,0). Da sind die beiden Kegel sehr einfach anzugeben.
toasten Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Hallo tigerbine,

vielen Dank für deine Antwort

Zitat:
Original von tigerbine
Die Zielfunktion sagt: mache x1 so groß wie möglich.

Stimmt, da stand ich gestern etwas aufn Schlauch.

Zitat:
Wie groß ist ist? Ist gamma fest? 0 oder 1?

Ich nehme an, man soll es für gamma = 0 und gamma = 1 prüfen.

Zitat:






Die Lösung ist also für gamma gleich 1, x*=1, mit f(x*)=-1.

Ja, solch ein Bild habe ich auch schon gezeichnet. Der Schnittpunkt liegt ja bei (1 , -1).

Zitat:

Der Linearisierte Kegel ist einfacher zu bestimmen.Wie lautet die Definition? Da kommen Gradienten drin vor.


Wir haben den linearisierten Kegel wie folgt definiert:

mit der linearisierten zulässigen Menge


Zitat:



Leider kann ich Flächen hier nicht ausmalen. Vielleicht kommst du auch so drauf, wie hier der linearisierte Kegel aussieht. Der sollte einen dann auch für den Tangentialkegel inspirieren. Die Defintion ist was unhandlich, aber zeichnerisch lässt der sich hier gut bestimmen.

Ok, ich verstehe, was du hier gemacht hast und kann es nachkonstruieren. Von der Zeichung her, würde ich jetzt sagen, dass das linke obere von blau und grün aufgespannte Dreieck der linearisierte Kegel ist.

Aber wie kann ich das rechnerisch bzw. in Worten angeben? Etwa so:

Ich habe ich jetzt als Nebenbedingungen "blau" und "grün" ("rot" ist ja überflüssig) und mit x_1 <= 1 gewährleistet, dass nicht das rechte Dreieck mitgenommen wird.

Wenn das jetzt so richtig ist, muss ich jedoch zugeben, wäre ich ohne Zeichnung nicht so darauf gekommen... :-( vor allem nach unser Definition

Zumal unser Tangentialkegel noch kryptischer aussieht:


Könntest du mir heir netterweise noch einen Tipp geben?

Zitat:

Für gamma gleich 0 besteht die zulässige Menge nur aus einem Punkt, hier (0,0). Da sind die beiden Kegel sehr einfach anzugeben.

Wie du sicherlich an meinen Fragen bemerkt hast, bin ich noch nicht so ganz sicher mit diesen Kegeln. Ich würde daher sagen: aus

Vielen Dank für deine Hilfe,
toasten
tigerbine Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Zu deinem linearisierten Kegel. Klar, kann man die Menge so angeben. Ob das schön ist, ist doch nicht die Frage. Auch algebraisch kannst du eine Bedingung weglassen. Big Laugh

Mit der Skizze bedenke, dass die Kegel in den Urpsrung verschoben werden müssen. Kein Buch macht das. Man zeichnet die immer an die zulässige Menge dran. Sollte halt wissen, dass man x*+Kegel hin malt.

Ich kenne die Kegel Definitionen "anders". Kannst du bei googlebooks und ff. mal nachlesen. Das tippe ich nicht ab. Big Laugh

Der Tangentialkegel braucht:

- Eine Folge innerhalb der zulässigen Menge, die gegen x* läuft

- Eine positive Nullfolge

und dann liegen die Folgenden d im Tangentialkegel



Anschaulich 2D sind das alle Richtungen, zwischen den Tangenten an die zulässige Menge. Daher dort einfach, i.A. sehr kompliziert.

Wenn die zulässige Menge nur aus einem Punkt besteht, wie sieht dann die zulässige Folge aus? Der TK besteht also aus nur welcher Richtung?

Den linearisierten Kegel kannst du ja auf jeden Fall mit den Bedingungen eh wieder hinschreiben.
toasten Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Hi,

also ich habe jetzt den Tangentialkegel auf zwei Wege bestimmt:

1.: Aus der Zeichnung abgelesen:

... in x-Richtung muss d nach links zeigen (also negativ) und in y-Richtung muss d zum einen nach oben (positiv) zeigen, darf aber eine Steigung von 1:2 (einen nach links, zwei nach oben) nicht überschreiten.

2.: Mittels der Definition:

Es ist

Nun setze ich

und
.

Man sieht


Daraus folgt

und somit


Obwohl ich die Nebenbedingungen für beta jetzt nur anhand meiner Zeichnung gesehen habe und sie leider nicht herleiten kann :-(

Hast du eine Idee?

Danke
tigerbine Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Für diese Fälle haben wir immer nur die äußeren Tangenten bestimmt. Man "sieht", dass man Folgen dazwischen konstruieren kann. Wurde nie gemacht. Da kann ich dir leider nicht mehr anbieten.
 
 
toasten Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Naja, letztendlich habe ich ja nur eine Folge {x_k} konstruiert, die gegen x^* konvergiert. Und dann mittels der Def der Tangentialrichtung
einfach die Tangentialrichtung(en) ausgerechnet.
Also so wie in deiner Beschreibung eines Tangentialkegels.
Die Einschränkungen für beta werden sich schon irgendwie beim Aufstellen meiner Gleichungen ergeben - wahrscheinlich ist es jetzt aber schon zu spät um mit offenen Augen zu gucken.

Kennst du die Regularitätsbedingung von Robinson?
Ich denke, die wird mit deiner Aussage des verschobenen Kegels zusammenhängen...

Viele Grüße
Torsten
tigerbine Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Ich kenne einige, aber Robinson ist mir neu. Was sagt die?

edit:
Inet sagt, dass die äquivalent zur MFCQ (Mangasarian Fromowitz) ist. Die kenne ich.


Meine Aussage hat damit aber nichts zu tun. Die Kegel leigen eigentlich im Ursprung. Man zeichnet sie nur anders.
toasten Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Ja genau,
MFCG ist auch ein Name dafür.

Wie kann man denn zeigen, dass das Problem die MFCG-Regularitätsbedingung erfüllt?
toasten Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Hi,

ich bin mit dieser Regularität jetzt auf zwei Probleme gestoßen.

1:
Im Netz habe ich folgende Definition für die MFCG gefunden (seite 21):
http://www.isa.uni-stuttgart.de/AbOpt/Ka...optIIfolien.pdf

dabei sind meine ja alle gleichzusetzen mit einem .
D.h., a) " linear unabhängig" brauche ich nicht zu betrachten.
Bei b) muss ich nur "" betrachten. Nun ist aber , da ich ja nur echte Ungleichungen habe, oder?

Somit kann ich gar keine der Bedingungen a) und b) prüfen...

2:
Ich habe gerade nochmal nach der Regularitätsbedingung von Robinson in unser Bib gesucht.

Im Jarre/Stoer: Optimierung auf Seite 249 (Definition 9.1.13) ist sie so zu finden, wie bei uns in de VL (leider ist genau diese Seite bei google books nicht verfügbar):
(P) heißt regulär in, wenn 0 ein innerer Punkt der Menge


wobei kappa laut unserer Vorlesung der Kegel


Dieser Kegel hat uns alles schon in der VL Probleme bereitet.

Ich komme auf folgendes

und jetzt komme ich nicht weiter... :-(

____________________
edit:
bei amazon kann man die Seite sich angucken, wenn man eingeloggt ist:
http://www.amazon.de/reader/3540435751?_...ader_3540435751
tigerbine Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Erfüllt das Problem denn die MFCQ?

Für gamma =1 haben wir 3 aktive Ungleichheitsrestriktionen. Denn (1,-1) liegt auf allen drei Kurven.




Gibt es nun ein d mit

?

Oder welchen Punkt wolltest du testen?
toasten Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Ja, solch einen Vektor gibt es: z.B. d=(-2,1)^T.

Aber da habe ich die Menge I(x^*) wohl falsch verstanden...

Du hast jetzt das d geprüft für alle Gradienten, die

erfüllen und nicht


...oder habe ich da jetzt irgendwo einen Denkfehler...?
tigerbine Auf diesen Beitrag antworten »
RE: Nichtlineare Optimierung
Das I(x*) ist die Menge der aktiven Ungleichheitsrestriktionen im zul. Punkt x*. Ein blick in undere Skizze zeigt, dass alle 3 Ungleichungen dort aktiv gehen. Die Ränder gehen ja alle durch x*=(1,-1).

Also habe ich mir von allen g Funtkionen die Gradienten in x* aufgeschrieben und dann die Forderung, wie sieht in der MFCQ steht. Ich ergänze





Wenn es so einen Vektor d gibt (angeben), dann ist die MFCQ erfüllt. Fertig. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »