restringierte Optimierung / KKT-Bedingungen

Neue Frage »

rolf M. Auf diesen Beitrag antworten »
restringierte Optimierung / KKT-Bedingungen
Hallo,

in meinem Optimierungsskript sind fast alle sätze von der Form:

"Ist x* eine Lösung, dann ist x* ein KKT-Punkt"

Ich finde das irgentwie unsinnig, weil man doch gerade die optimale lösung durch die KKT-Punkte charakterisiert.

Oder ist das so zu verstehen, dass x* dann sozusagen zulässig ist, und erst optimal wird wenn die KKT-Bedinugen erfüllt sind?

es wäre doch viel sinnvoller sätze zu haben wie: "sind die KKT-bedingungen erfüllt, dann ist x* die optimale lösung"

Verstehe ich das ganze falsch oder sind diese Sätze praktisch nutzlos?

gruß

Rolf
tigerbine Auf diesen Beitrag antworten »
RE: restringierte Optimierung / KKT-Bedingungen
Zitat:

es wäre doch viel sinnvoller sätze zu haben wie: "sind die KKT-bedingungen erfüllt, dann ist x* die optimale lösung"


Schön wäre es, allgemein solche Sätze zu haben. Dem ist aber nicht so. Man ist schon froh, wenn man für restringierte Aufgaben notwendige Bedingungen formulieren kann. Die Sätze lauten dann so

x* ist Optimum + x* genügt einer Regularitätsbedingung => x* ist ein KKT-Punkt

Daher macht es Sinn, KKT-Punkte zu suchen. Motivation ist im Grunde die Verallgemeinerung der unrestringierten notwendigen Bedingung: Gradient =0.

Ein Nachteil an hinreichenden Bedingungen ist auch, dass sie i.A. keine Aussage darüber treffen, was ist, wenn sie nicht erfüllt sind. Typisches Beispiel (jetz halt unrestringiert):

Rolf M. Auf diesen Beitrag antworten »

Hallo tigerbine,

das ägert mich irgentwie, aber ich denke mathematik ist kein wunschkonzert : ) .

Also wenn ich das richtig verstehe, laufen die Algorithmen dafür dann im Prinzip so:

1. ist x* ein KKT-Punkt? ja -> prüfe ob hinreichend

nein -> 2. rechne was
3.rechne was.
...
...


also es muss noch extra geprüft werden, ob der vorliegende Punkt ein KKT-Punkt ist.
Rolf M. Auf diesen Beitrag antworten »

ach noch etwas, wenn ich ein konvexes Optimierungsproblem habe, gilt ja auch die umkehrung. also da würde dann die Prüfung entfallen.


gruß

Rolf
tigerbine Auf diesen Beitrag antworten »

Konvexe Probleme sind "einfach", aber in der Regel ist ein Optimierungsproblem doch nicht konvex.

Zum Thema "Wunschkonzert". Ich kann deinen "Frust" nachempfinden, ging mir mal ähnlich. Wie müssen das anders betrachten. Die Dinge, die wir in der Schule gelernt haben sind ja schon seeeeeeeeeehr alt. Damit fester Bestandteil des "Wissens" und wir erwarten, dass eine Aufgabe, die wir bekommen "lösbar" ist. [um 570 v. Chr. Pythagoras]. Der Simplex-Algorithmus für lineare Programme ist von 1947.

Man versucht ja die Resultate auch so zu formulieren, dass sie auf möglichst viele Situationen passen. Bei einer 1D Kurvendiskussion (unrestringiert) meckern wir ja auch nicht, dass wir erst mal die erste Ableitung 0 setzen. Das sind auch nur Kandidaten. Das will man nun möglichst gut übertragen.

Man ist also erst mal bemüht, notwendige Kriterien zu formulieren. Z.B. KKT. GGf. bekommt man aber so gar nur was schwächeres.

Bedenke auch, dass selbst wenn wir in dem Punkt noch eine hinreichende Bedingung erfüllt haben, so ist die durch "einen" Algorithmus erzielte Lösung nur ein lokales Minimum. I.A. also kein globales Minimum.

Es gibt also noch viel zu forschen. Augenzwinkern

Zitat:
Also wenn ich das richtig verstehe, laufen die Algorithmen dafür dann im Prinzip so:


Das kann ich nicht allgemein beantworten.
Rolf M. Auf diesen Beitrag antworten »

Mir war der Zusammenhang zwischen dem herkömlichen (1-D) Fall bekannt. Ich hatte mich nur einwenig geärgert wie es da keinen Satz gibt ala kkt => lok. Lösung. Aber vielen dank bis dahin! smile .

ich möchte sozusagen schon erahnen was später auf mich wartet (ich meine die algorithmen zu den restringierten problemen). Die kenne ich nähmlich noch nicht. ich könnte mir gut vorstellen,

dass da einige dabei sind die am anfang dann die folgende abfrage nutzen (als abbruchkriterium):

solange "nicht KKT-Punkte => "nicht lösung" (ist ja logisch das selbe wie "lok lösung" => "KKT-Punkt")


aber nochmals vielen dank! An dieser Stelle möchte ich nochmal sagen, dass ich großen Respekt vor allen Wissenschaftlern / innen habe, die diese Sachen weiterentwickeln!

gruß

Rolf
 
 
tigerbine Auf diesen Beitrag antworten »

1D war nur als Analogie gedacht. Augenzwinkern

Man wird i.A. nicht so vorgehen. Man stellt z.B. die KKT-Bedingungen auf [Gleichunggsystem] und versucht dieses zu lösen. Es gibt auch gute Software für so was. Die kann man auch "blind" mal nutzen. Wer einen zulässigen Punkt mit "kleinstem" Funktionswert findet, hat die "aktuell" beste Lösung. Big Laugh

Generell ist eine Konvergenztheorie dort schon was anspruchsvoler. Soll auch heißen, nicht alles was praktisch klappt, läßt sich schön zu Papier bringen.
Rolf M. Auf diesen Beitrag antworten »

ich denke der Sachverhalt ist ein bisschen klarer geworden! Vielen Dank für deine Hilfe Wink
Neue Frage »
Antworten »



Verwandte Themen

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