Konvexe Funktion, lokale Minima

Neue Frage »

AlSvartr Auf diesen Beitrag antworten »
Konvexe Funktion, lokale Minima
Servus zusammen...

...ich hab da mal ne kleine Frage bezüglich konvexer Funktionen und Optimierungsproblemen. Es wird verlangt, eine Instanz (wobei Teilmenge von und konvex ist) eines Optimierungsproblems als Beispiel anzugeben, bei der lokale Minima existieren, die aber nicht global sind. Die Voraussetzung ist aber wie gesagt, dass konvex ist. Jetzt frage ich mich: Wie soll das gehen? Per Definition gilt für konvexe Funktionen . Damit würde aber die Existenz eines lokalen Minimums, das nicht global ist, bei einer Konvexkombination zwischen zwei lokalen Minima die Konvexitätsbedingung verletzen. Damit - würde ich sagen - ist der Fall erledigt und für konvexe kann ein solches lokales Minimum, das nicht global ist, nicht existieren.

Irre ich mich? Und wenn ja: Warum? geschockt
Abakus Auf diesen Beitrag antworten »
RE: Konvexe Funktion, lokale Minima
Muss das lokale Minimum streng sein oder kann da zB eine ganze Strecke mit solchen Minima vorhanden sein ?

Grüße Abakus smile
AlSvartr Auf diesen Beitrag antworten »

Diesbezüglich ist keine explizite Anforderung gestellt, aber was würdest du dir denn als Antwort vorstellen, wenn es das nicht sein muss?
Abakus Auf diesen Beitrag antworten »

Meine erste Idee war sowas: (die zB oberhalb dieser 3 Geraden liegende Menge; wäre zu testen, ob sich das so beschreiben lässt)



Die Frage ist auch, von was für Minima hier die Rede ist.

Grüße Abakus smile

EDIT: die Funktion c wird dann durch die Begrenzung der Menge gebildet
AlSvartr Auf diesen Beitrag antworten »

Aber dann sind doch alle lokalen Optima (bzw. Minima) auch wieder global. Interessanterweise las ich gerade im Skript eigentlich genau das, was ich schon als Antwort in meiner Lösung geschrieben hatte: Eine konvexe Funktion kann viele lokale Optima haben, aber alle müssen auch global sein (weil die Funktion sonst nicht konvex wäre). Scheint also irgendwie ne Fangfrage zu sein, die Aufgabe verwirrt
Abakus Auf diesen Beitrag antworten »

Was soll denn diese Instanz und die Menge F genau sein ? Kannst du die Begriffe mal definieren ? (ich sehe da noch nicht völlig klar)

So wie du es hingeschrieben hast, müsste die Menge F ja auch konvex sein, damit c auf der Verbindungsstrecke von x nach y in der Bedingung definiert ist. Ist das der Fall ?

Grüße Abakus smile
 
 
AD Auf diesen Beitrag antworten »

Ich knüpfe mal an Abakus' letzte Aussage an:

Da steht bislang nichts davon, dass auch konvex sein soll (es sei denn, dieser Begriff "Instanz" beinhaltet das). Demnach könnte man z.B. als endliche Menge wählen, dann ist jedes isoliert und somit automatisch lokale Minimumstelle. Augenzwinkern
AlSvartr Auf diesen Beitrag antworten »

Es gibt wohl tatsächlich nicht die Anforderung, dass konvex sein soll, aber nach einigem Kopfzerbrechen vermuten wir nun, dass die Aufgabe eigentlich auf etwas anderes hinauslaufen soll. Wie gesagt, nur eine Vermutung! Und zwar folgende: Es ist nach lokalen Minima gefragt, die nicht optimal sind - wir haben in die Vorlesung auch -Nachbarschaften (meines Wissens auch bekannt unter dem Namen ) betrachtet. Wir gehen nun davon aus, dass wir eigentlich nur eine Instanz eines Problems zeigen sollen, welche für eine solche Nachbarschaft lokale Minima liefert, die nicht global sind. Wenn ich wüsste, ob das auch richtig vermutet ist, wär ich glücklicher Augenzwinkern

Jedenfalls hab ich mir dazu dann ein grenzbanales Beispiel ausgedacht, was ich dann vermutlich auch noch falsch aufgeschrieben habe Augenzwinkern ... zu sehen ist das dann hier: http://home.inf.fh-brs.de/~troth22s/ko_u02_loesung.pdf (Aufgabe 4)

@Abakus:
Bei einer Instanz (F,c) eines Optimierungsproblems ist F der Lösungsraum und die Kostenfunktion.
Neue Frage »
Antworten »



Verwandte Themen

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