KKT-Punkt lokales Minimum?

28.03.2009, 00:44

guest1402

Auf diesen Beitrag antworten »

KKT-Punkt lokales Minimum?

Servus! Mit folgender Aufgabenstellung hab ich smomentan zu tun:

Gegeben sei das Optimierungsproblem:
$\begin{eqnarray*} min 2x_{1}^2 + 2x_{1}x_{2} +x_{2}^2 -10x_{1}-10x_{2} \end{eqnarray*}$
unter den Restriktionen:
$\begin{eqnarray*} x_{1}^2+x_{2}^2\le 5 \end{eqnarray*}$
$\begin{eqnarray*} 3x_{1}+x_{2}\le 6 \end{eqnarray*}$
$\begin{eqnarray*} x_{1},x_{2}\ge 0 \end{eqnarray*}$

Stellen Sie die KKT(Karush Kuhn Tucker)-Bedingungen auf und bestimmen Sie alle Punkte, die diese Bedingungen erfüllen. Befinden sich unter diesen Punkten lokale Optima?

Den ersten Teil hab ich gelöst und bin auf den KKT-Punkt $\begin{eqnarray*} (1,2) \end{eqnarray*}$ gekommen. Wie allerdings kann ich überprüfen, ob dies ein lokales Minimum ist in der zuläßigen Menge ist? $\begin{eqnarray*} (1,2) \end{eqnarray*}$ liegt ja am Rand des Kreises gegeben durch die erste Restriktion. Maple sagt mir, dass der Punkt ein lokales Minimum über die zuläßige Menge ist (allgemein aber keines ist). Allerdings fehlt mir absolut ein Ansatz das auch formal zu zeigen bzw. zumindest das intuitiv begründen zu können.

Danke im voraus!

lG

31.03.2009, 20:51

Abakus

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Du könntest die interessierende (Relativ-)Umgebung von (1, 2) untersuchen. Wenn dort alle Funktionswerte größer sind, hast du es gezeigt.

Grüße Abakus smile

smile

01.04.2009, 13:49

n!

Auf diesen Beitrag antworten »

mikey1
allerdings frage ich mich folgendes: Wenn (1,2) lokales Minimum ist, dann müssen doch die KKT conditions gelten. In diesem Fall muss doch gelten:

$\begin{eqnarray*} \nabla f((1,2))+\lambda \nabla g((1,2))=0 \end{eqnarray*}$

Wobei $\begin{eqnarray*} g(x_1,x_2)=x^2+y^2 \end{eqnarray*}$ . Allerdings gibt es kein nichtnegatives $\begin{eqnarray*} \lambda \end{eqnarray*}$ , dass diese Gleichung erfüllt???

02.04.2009, 20:59

Abakus

Auf diesen Beitrag antworten »

RE: mikey1
Also ich habe nicht nachgerechnet. Da hier aber Zweifel angemeldet werden, kannst du, guest 1402, ja vielleicht mal deinen Rechengang aufzeigen.

Grüße Abakus smile

smile

03.04.2009, 10:19

n!

Auf diesen Beitrag antworten »

Gerne. Also hier mal meine Überlegungen. Hier liegt ja ein konvexes Optimierungsproblem vor.

Die Zielfunktion ist konvex (man rechnet leicht nach, dass die Hesse Matrix positiv definit ist).

Die Nebenbedingungen seien
$\begin{eqnarray*} x_1^2+x_2^2-5\leq 0 \end{eqnarray*}$
$\begin{eqnarray*} 3x_1+x_2-6\leq 0 \end{eqnarray*}$
$\begin{eqnarray*} -x_1\leq 0 \end{eqnarray*}$
$\begin{eqnarray*} -x_2\leq 0 \end{eqnarray*}$

Bezeichnet man der Reihe nach die Nebenbedingungsfunktionen als g1,...,g4.

Sei $\begin{eqnarray*} I \end{eqnarray*}$ die Menge der aktiven Ungleichungen, also die, die mit Gleichheit im Punkt $\begin{eqnarray*} (1,2) \end{eqnarray*}$ erfüllt sind. Nach Karush-Kuhn-Tucker gilt ja für ein lokales Minimum stets, dass nichtnegative Skalare $\begin{eqnarray*} \lambda \end{eqnarray*}$ exisiteren mit:

$\begin{eqnarray*} \nabla f(x)+\sum_{i\in I}^{}~\lambda_ig_i(x)=0 \end{eqnarray*}$

Für den Punkt (1,2) reduziert sich das auf die Gleichung in meinem vorherigen Beitrag (einzig aktive Ungleichung ist g1). Eingesetzt:

$\begin{eqnarray*} \begin{pmatrix} -2 \\ 0 \\\end{pmatrix}+\lambda \begin{pmatrix} 2 \\ 4 \\\end{pmatrix}=0 \end{eqnarray*}$

Und man sieht, dass man kein $\begin{eqnarray*} \lambda \end{eqnarray*}$ existiert??? verwirrt

verwirrt

04.04.2009, 19:59

Abakus

Auf diesen Beitrag antworten »

Ich komme auf:

$\begin{eqnarray*} \nabla f(\chi) = (4x +2y - 10, 2x + 2y -10) \end{eqnarray*}$

und

$\begin{eqnarray*} \nabla f(1,2) = (-2, -4) \end{eqnarray*}$

Dafür findet sich ein Lambda; ansonsten richtig gesehen: ein solches Lambda muss bei "aktiver" Ungleichung existieren.

Grüße Abakus smile

smile

Anzeige

06.04.2009, 10:29

n!

Auf diesen Beitrag antworten »

Gradientenberechnung muss gekonnt sein Hammer

Hammer

Allerdings ist doch der Beweis, dass hier tatsächlich ein lokales Minimum vorliegt sehr einfach. Es ist doch eine der sogenannten contraint qualifications erfüllt, nämlich die, dass der Gradient in der aktiven Ungleichung an diesem Punkt linear unabhängig ist (klar, es gibt ja nur einen). Damit sind die KKT Bedingungen hier sogar hinreichend!

06.04.2009, 17:50

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von n!
Allerdings ist doch der Beweis, dass hier tatsächlich ein lokales Minimum vorliegt sehr einfach. Es ist doch eine der sogenannten contraint qualifications erfüllt, nämlich die, dass der Gradient in der aktiven Ungleichung an diesem Punkt linear unabhängig ist (klar, es gibt ja nur einen). Damit sind die KKT Bedingungen hier sogar hinreichend!

Wenn man diesen oder ähnliche Sätze zur Verfügung hat (und alle Bedingungen gecheckt hat), ja. Wir haben allerdings noch nichtmal nachgerechnet, dass (1, 2) überhaupt ein kritischer Punkt der Lagrange-Funktion ist bzw. genau geschaut, welche Bedingungen eigentlich gelten, was guest1402 mal machen müsste.

Grüße Abakus smile

smile

14.10.2009, 21:22

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Hallöchen,

da ich gerade versuche mir dieses Thema drauf zuschaffen, möchte ich diesen Thread gerne weiterführen. Augenzwinkern

Augenzwinkern

Bei einem solchen restringierten Optimierungsproblem hat man (in der Normalform) eine zu minimierende Funktion f. Die zulässige Menge drückt man in der Nebenbedingung durch Ungleichheitsrestriktionen (g) und Gleichheitsrestriktion (h) aus. Würde das hier dann so aussehen?

$\begin{eqnarray*} f(x)=2x_{1}^2 + 2x_{1}x_{2} +x_{2}^2 -10x_{1}-10x_{2} \end{eqnarray*}$

$\begin{eqnarray*} g_1(x)=x_1^2+x_2^2-5 \leq 0 \end{eqnarray*}$

$\begin{eqnarray*} g_2(x)=3x_1+x_2-6 \leq 0 \end{eqnarray*}$

$\begin{eqnarray*} g_3(x)=-x_1 \leq 0 \end{eqnarray*}$

$\begin{eqnarray*} g_4(x)=-x_2 \leq 0 \end{eqnarray*}$

Damit ich die KKT-Bedingungen aufstellen kann, muss ich erstmal die Lagrange-Funktion des restringierten Optimierungsproblems aufstellen. Da keine Gleichheitsrestriktionen auftreten ergibt sich:

$\begin{eqnarray*} L(x,\lambda,\mu) = f(x) + \sum_{i=1}^4 \lambda_ig_i(x) \end{eqnarray*}$

Für die KKT-Bedingungen braucht man nun schon mal den Gradienten

$\begin{eqnarray*} \nabla_x L(x,\lambda):=\nabla f(x) + \sum_{i=1}^m \lambda_i \nabla g_i(x) \end{eqnarray*}$

Das ist doch aber was anderes als

$\begin{eqnarray*} \nabla L(x,\lambda) \end{eqnarray*}$ (*)

denn dort hätte man ja auch partiell nach $\begin{eqnarray*} \lambda \end{eqnarray*}$ abgeleitet? Vergleiche das pdf.

Richtig verstanden oder Fehler drin. Danke Wink

Wink

14.10.2009, 23:50

Abakus

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Was passiert, wenn du es konkret durchrechnest? Aus meiner (im Moment ggf. oberflächlichen) Sicht musst du auch nach den Lambdas ableiten (weil du ja auch den Rand betrachten musst).

Grüße Abakus smile

smile

14.10.2009, 23:53

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Bin gerade dabei. In meiner Lektüre steht das bei den KKT nur nach x abgeleitet wird.

Vielleicht wirfst du mal einen Blick rein? Ich versuche die Aufgabe derweil zu rechnen. Danke Wink

Wink

15.10.2009, 00:01

Abakus

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Bei deiner Lektüre stoße ich auf eine Anzeigebeschränkung (muss ich da was Besonderes machen?)

Ansonsten: wenn du nach den Lambdas ableitest, bekommst du die normalen Nebenbedingungen, die du natürlich auch vorher hattest. Möglich, das die einfach so ohne Ableiten hergenommen werden und die jeweiligen Ableitungen dann weggelassen werden (?).

Grüße Abakus smile

smile

15.10.2009, 00:03

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Beschränkung bei der ersten Seite? Ist zu google books, du hast in dem Buch doch noch nicht geblättert, oder?

Vielleicht kommst du selber über die Büchersuche besser hin?

Kanzow, Theorie und Numerik restringierter Optimierungsaufgaben , Seite 46, Definition 2.35

15.10.2009, 00:16

Abakus

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?

Zitat:

Original von tigerbine
Beschränkung bei der ersten Seite? Ist zu google books, du hast in dem Buch doch noch nicht geblättert, oder?

Vielleicht kommst du selber über die Büchersuche besser hin?

Kanzow, Theorie und Numerik restringierter Optimierungsaufgaben , Seite 46, Definition 2.35

Ich sehe nur das Inhaltsverzeichnis unglücklich

unglücklich

; möglich, es ändert sich, wenn ich mich da bei Gelegenheit anmelde.

Grüße Abakus smile

smile

15.10.2009, 00:26

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Ich bin da nicht angemeldet. Ich gebe über die Suche das Buch ein (oben) und links suche ich nach den Details. Ich werde die Seite nun mal einscannen. Sorry für die Quali, das Buch ist was dick...

15.10.2009, 01:06

tigerbine

Auf diesen Beitrag antworten »

Rechnung
Was mir noch nicht klar ist, wir der Threadsteller auf den Punkt p=(1,2) gekommen ist. verwirrt

verwirrt

$\begin{eqnarray*} \nabla_x L(x,\lambda)=\begin{pmatrix} 4x_1+2x_2-10 \\ 2x_1 + 2x_2 -10 \end{pmatrix} + \lambda_1 \begin{pmatrix} 2x_1 \\ 2x_2\end{pmatrix}+ \lambda_2 \begin{pmatrix} 3\\1 \end{pmatrix} + \lambda_3 \begin{pmatrix} -1\\0 \end{pmatrix} + \lambda_4 \begin{pmatrix} 0 \\-1 \end{pmatrix} \stackrel{!} = \begin{pmatrix} 0\\ 0 \end{pmatrix} \end{eqnarray*}$

Es ist zumindest dann wenn man den Punkt hat:

$\begin{eqnarray*} \nabla_x L(p,\lambda)=\begin{pmatrix} -2 \\ -4 \end{pmatrix} + \lambda_1 \begin{pmatrix} 2 \\ 4 \end{pmatrix}+ \lambda_2 \begin{pmatrix} 3\\1 \end{pmatrix} + \lambda_3 \begin{pmatrix} -1\\0 \end{pmatrix} + \lambda_4 \begin{pmatrix} 0 \\-1 \end{pmatrix} \stackrel{!} = \begin{pmatrix} 0\\ 0 \end{pmatrix} \end{eqnarray*}$

Mit der Bedingung $\begin{eqnarray*} \lambda^Tg(x)=0 \end{eqnarray*}$ folgt dann:

$\begin{eqnarray*} g_1(p)=0 \end{eqnarray*}$

$\begin{eqnarray*} g_2(p)=-1 \Rightarrow \lambda_2=0 \end{eqnarray*}$

$\begin{eqnarray*} g_3(p)=-1 \Rightarrow \lambda_3 = 0 \end{eqnarray*}$

$\begin{eqnarray*} g_4(p)=-2 \Rightarrow \lambda_4 =0 \end{eqnarray*}$

Damit ergibt sich

$\begin{eqnarray*} \nabla_x L(p,\lambda)=\begin{pmatrix} -2 \\ -4 \end{pmatrix} + \lambda_1 \begin{pmatrix} 2 \\ 4 \end{pmatrix}\stackrel{!} = \begin{pmatrix} 0\\ 0 \end{pmatrix} \Rightarrow \lambda_1=1 \end{eqnarray*}$

Damit ist $\begin{eqnarray*} (p,\lambda_p) \end{eqnarray*}$ ein KKT-Punkt.

Bleiben die Fragen:

Wie kommt man auf den Punkt?
Gibt es noch weitere KKT Punkte?
Wie stehen die stationären Punkte von f unter NB und die KKT Punkte in Bezug?

15.10.2009, 01:15

Abakus

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Erstmal danke für die Buchseite Augenzwinkern

Augenzwinkern

.

Ich denke, es gibt 2 verschiedene Möglichkeiten, die Nebenbedingungen aufzustellen: einige Ökonomen leiten halt gerne nach den Lambdas ab; andere halten das für problematisch, sobald Ungleichungen als Nebenbedingung da sind (wenn es nur Gleichungen sind, ist es ja augenscheinlich dasselbe die Nebenbedingungen so aufzunehmen oder diese erst durch Differentiation zu erhalten).

In jedem Fall steht die "komplementäre Schlaffheitsbedingung" $\begin{eqnarray*} \lambda \ge 0 (=0 ~ \text{ falls }~ g(\chi) < 0) \end{eqnarray*}$ immer dabei.

Zitat:

Was mir noch nicht klar ist, wir der Threadsteller auf den Punkt p=(1,2) gekommen ist. verwirrt

verwirrt

Ja, das hat er bisher nicht verraten.

Grüße Abakus smile

smile

15.10.2009, 01:22

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Sacannen gern geschehen.

Ich denke den KKT kommt noch größere Bedeutung zu und "äquivalente" Formulierungen in den nächsten Kapiteln. Der Autor hat bestimmt keine Angst vorm Ableiten. Augenzwinkern

Augenzwinkern

Nur bin ich eben im Buch noch nicht so weit. Nur allein schon bei dieses sicherlich konstruierten Aufgabe mit (mind) einer ganzzahligen Lösung finde ich es schon schwierig, auf einen Punkt zu kommen.

Aber zumindest habe ich die Bedingungen nun ja schon einmal aufgestellt. Big Laugh

Big Laugh

Zitat:

Ich denke, es gibt 2 verschiedene Möglichkeiten, die Nebenbedingungen aufzustellen: einige Ökonomen leiten halt gerne nach den Lambdas ab.

Kommt man damit denn besser an den Punkt (1,2)? Der Threadsteller (März) wird es wohl nicht mehr verraten.

15.10.2009, 18:26

Abakus

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?

Zitat:

Original von tigerbine
Kommt man damit denn besser an den Punkt (1,2)? Der Threadsteller (März) wird es wohl nicht mehr verraten.

Genauso gut, denke ich mal. Eine aufwändige Fallunterscheidung (ob der kritische Punkt jetzt im Inneren oder auf dem Rand des zulässigen Bereichs liegt) wird einem hier kaum erspart bleiben, denke ich.

Grüße Abakus smile

smile

15.10.2009, 18:32

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Verstehe ich es richtig: KKT ist notwendig für ein Minimum. Je nach Problem kann es auch hinreichend sein. Für die Verfahren, die man entwickelt zeigt man dann, dass ihre Lösung äquivalent zu einem KKT Punkt ist. Also dass man diese Eigenschaften eher im Beweis eines Verfahrens benutzt als in der Ausrechnung von Hand?

Im unrestringierten Fall reduziert sich die KKT Bedingung auf das verschwinden des Gradienten?

15.10.2009, 21:50

Abakus

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?

Zitat:

Original von tigerbine
Verstehe ich es richtig: KKT ist notwendig für ein Minimum. Je nach Problem kann es auch hinreichend sein.

Ja, genau.

Zitat:

Für die Verfahren, die man entwickelt zeigt man dann, dass ihre Lösung äquivalent zu einem KKT Punkt ist. Also dass man diese Eigenschaften eher im Beweis eines Verfahrens benutzt als in der Ausrechnung von Hand?

Da bin ich überfragt, denke jedoch, dass die rechnerische Anwendung im Vordergrund steht. Das Verfahren lässt sich sicher gut programmieren, so dass man es nicht per Hand rechnen muss.

Zitat:

Im unrestringierten Fall reduziert sich die KKT Bedingung auf das verschwinden des Gradienten?

Dann hätte man ja keine Nebenbedingungen und es wäre ein "normales" Minimax-Problem.

Grüße Abakus smile

smile

15.10.2009, 22:09

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Ok. Der restringierte Fall wird also was komplizierter. Kein Wunder, dass das Kapitel "Optimalitätsbedingungen" dort viel länger ist. Augenzwinkern

Augenzwinkern

Frage, kennst du dich mit Dingen wie "Tangentialkegel" und den KKT unter verschiedenen Regularitätsbedingungen aus?

Wink

Wink

15.10.2009, 22:14

Abakus

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?

Zitat:

Original von tigerbine
Frage, kennst du dich mit Dingen wie "Tangentialkegel" und den KKT unter verschiedenen Regularitätsbedingungen aus?

Wink

Wink

Nein, nicht wirklich. Ich würde einfach die ermittelten kritischen Punkte untersuchen.

Grüße Abakus smile

smile

15.10.2009, 22:16

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Das ist bei einem allgemein Problem eher schwierig. Ich muss die Theorie der Optimalitästbedingungen lernen. Beispiele sollten mir nur beim Verständnis helfen. Dennoch danke für deine Bemühungen. Wink

Wink

16.10.2009, 01:08

tigerbine

Auf diesen Beitrag antworten »

RE: KKT-Punkt lokales Minimum?
Eine Frage ist mir bei der weiteren Lektüre noch gekommen. In einem Minimum eines restringierten Optimierungsproblems muss der Gradient aber nicht verschwinden, so wie das beim unrestringierten der Fall war? Oder verstehe ich das folgende Lemma falsch (Anhang)? Denn es gilt dort für alle Vektoren aus dem Tangentialkegel von x*

$\begin{eqnarray*} \nabla f(x^*)^Td \geq 0 \end{eqnarray*}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »