konvexes Optimierungsproblem < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:35 Mo 04.05.2009 | | Autor: | ella87 |
| Aufgabe | Sein [mm]\alpha>0 [/mm] gegeben. Die Entropie von [mm](x_{1},...,x_{n})[/mm] mit [mm]x_{i}>0[/mm] [mm]1 \le i \le n[/mm] ist definiert als
[mm] H(x_{1},...,x_{n}) = \summe_{i=1}^{n} x_{i}log \bruch{1}{ x_{i}}[/mm]
Betrachten Sie folgendes Probem:
Man bestimme eine (möglichst gute) obere Schranke für die Entropie unter der Annahme, dass die Summe der [mm]x_{i}[/mm] den Wert [mm]\alpha[/mm] nicht überschreitet.
(a) Formulieren Sie dieses Problem als konvexes Optimierungsproblem mit linearen Nebenbedingungen.
(b) Stellen Sie die zugehörigen KKT-Bedingungen auf.
(c) Finden Sie mit Hilfe der KKT-Bedingungen aus (b) eine Optimallösung. |
Hallo!
Ansatz hab ich leider noch keinen. Konvexe Optimierung heißt, ich muss eine konvexe Funktion [mm] f: F \to \IR[/mm] aufstellen und dann für [mm] \Omega \subseteq F [/mm] konvex [mm]\min_{w \in \Omega}f(w)[/mm]. Wobei doch f meine Schranke sein müsste. Nebenbedingung wäre doch [mm]\summe_{i=1}^{n} x_{i} \le \alpha[/mm].
Ich hab das leider noch nicht ganz verstanden mit den Optimierungen und würde gerne die Vorgehensweise bei einem solchen Problem verstehen.
Vielleicht kann mir erstmal jemand bei der Formulierung den Problems helfen (b) und (c) sind mir erstmal nebensächlich.
Vielen lieben Dank Ella
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:18 Mo 04.05.2009 | | Autor: | Blech |
> Ansatz hab ich leider noch keinen. Konvexe Optimierung
> heißt, ich muss eine konvexe Funktion [mm]f: F \to \IR[/mm]
> aufstellen und dann für [mm]\Omega \subseteq F[/mm] konvex [mm]\min_{w \in \Omega}f(w)[/mm].
> Wobei doch f meine Schranke sein müsste. Nebenbedingung
> wäre doch [mm]\summe_{i=1}^{n} x_{i} \le \alpha[/mm].
und [mm] $x_i>0$ $\forall [/mm] i$.
>
> Ich hab das leider noch nicht ganz verstanden mit den
> Optimierungen und würde gerne die Vorgehensweise bei einem
> solchen Problem verstehen.
>
Deine urspr. Zielfunktion ist doch [mm] $\summe_{i=1}^{n} x_{i}\log \bruch{1}{ x_{i}}=-\summe_{i=1}^{n} x_{i}\log x_{i}$. [/mm] Die ist ja schon gegeben.
Sie ist außerdem konkav, weil [mm] $-x\log [/mm] x$ konkav ist, und Du willst maximieren.
Wie kriegt man aus einer konkaven jetzt eine konvexe Funktion, die wir minimieren können?
ciao
Stefan
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 18:35 Mi 06.05.2009 | | Autor: | ella87 |
> Sie ist außerdem konkav, weil [mm]-x\log x[/mm] konkav ist, und Du
> willst maximieren.
> Wie kriegt man aus einer konkaven jetzt eine konvexe
> Funktion, die wir minimieren können?
Gute Frage  Ist sie nicht konkav, weil [mm]-x\log x[/mm] konvex?
Ich tippe auf die Umkehrfunktion???
Hab recht lange an der getüftelt, aber keine Lösung....
Ist die Idee denn richtig? Wir haben zu konkaven Funktionen in der VL garnichts gemacht...
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 22:31 Do 07.05.2009 | | Autor: | Fusel |
Hey, da man immer Minimierungsprobleme betrachtet, musst du hier (-H) minimieren und da H konkav ist, ist (-H) auch konvex und man hat den 1. Teil des konvexen Optimierungsproblems :)
Nur hab ich eine Frage zu den Nebenbedingungen:
Wir hatten bei linearen Nebenbedingungen immer die Form Ax [mm] \le [/mm] b
Nur sind hier ja u.a. die Bedingung [mm] x_i [/mm] < 0 gegeben. Wie kann ich das denn in die Form Ax [mm] \le [/mm] b bringen?
Ich habe es einmal in der Form:
[mm] (1...1)*\pmat{ x_1 \\ ...\\ x_n} \le \alpha [/mm] gemacht und dazu geschrieben, dass [mm] x_i \le [/mm] 0 ist (bzw evtl kann man das einfach unter das "min" schreiben, nur weiß ich nicht, ob dann allgemein die KTT-Bedingungen so "gelten"??)
Und einmal in der Form
[mm] \pmat{ 1 & 1 &...&1 \\ -1 & 0...&0 \\ ...\\ 0 & 0 & ...& -1 } *\pmat{ x_1 \\ ...\\ x_n} \le *\pmat{ \alpha \\0 \\ ...\\ 0}
[/mm]
und dazu geschrieben das [mm] x_i \not= [/mm] 0
Es kommt am Ende auch dasselbe Ergebnis raus, aber wie macht man das denn formal? Kann mir da jemand helfen?
Danke schön :)
Fusel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 So 10.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Fr 08.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
