Maximierung einer Funktion über Paare aus 2 Mengen

Neue Frage »

21.02.2010, 09:11	Strider	Auf diesen Beitrag antworten »
Maximierung einer Funktion über Paare aus 2 Mengen Hallo, ich hoffe ich bin mit der Frage hier am richtigen Platz gelandet, aber da ich sie nicht genau einzuordnen weiß, bin ich bisher auch mit recherche zum Thema gescheitert. 2 gleichgroße Mengen A,B mit Zahlen Element [0,1] Ich suche das maximum der Funktion: Summe ( Wurzel ( alpha * a + (1-alpha) b) Wobei a, b aus den entsprechenden Mengen stammen. Es wird aber nicht jedes a mit jedem b kombiniert sondern jedes nur in einem paar verwendet. Alpha aus [0,1] Beispiel: A{0,0,1} B{0,1,1} alpha=0,5 Dann kann ich z.b. die Paare (1,0) (0,1) (0,1) bilden oder die Paare (0,0)(0,1)(1,1) u.s.w. Ersteres ergibt etwa 2,12 zweites 1,7 -Wie drücke ich das Problem mathematisch richtig aus? -Wie zeige ich das maximum (Recht offensichtlich ist, dass es dann erreicht wird wenn alle alpha a + (1-alpha) *b möglichst gleich groß sind) -Ist das ein bekanntes Problem? Unter welchem Stcihwort finde ich Literatur dazu?
21.02.2010, 09:19	wisili	Auf diesen Beitrag antworten »
RE: Maximierung einer Funktion über Paare aus 2 Mengen So kann man nicht helfen: Die Klammern stimmen nicht, man weiss nicht, worüber summiert wird.
21.02.2010, 09:29	Strider	Auf diesen Beitrag antworten »
RE: Maximierung einer Funktion über Paare aus 2 Mengen Da hast du recht also nochmal hübscher: 2 Mengen A,B mit Zahlen Element [0,1] der Kardinalität i Ich suche das Maximum der Funktion: $\begin{eqnarray} <br /> \sum\limits_{i} \sqrt{\alpha \cdot a + (1-\alpha )b}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \alpha \in [0,1]<br /> \end{eqnarray}$ Wobei a, b aus den entsprechenden Mengen stammen. Es wird aber nicht jedes a mit jedem b kombiniert sondern jedes nur in einem Paar verwendet. Alpha ist gegeben, es soll über die optimale Paarbildung maximiert werden. Weiß leider nicht wie ich das in der Formel korrekt ausdrücke Beispiel: A{0,0,1} B{0,1,1} alpha=0,5 Dann kann ich z.b. die Paare (1,0) (0,1) (0,1) bilden oder die Paare (0,0)(0,1)(1,1) u.s.w. Ersteres ergibt etwa 2,12 zweites 1,7 -Wie drücke ich das Problem mathematisch richtig aus? -Wie zeige ich das maximum (Recht offensichtlich ist, dass es dann erreicht wird wenn alle $\begin{eqnarray} <br /> \alpha \cdot a + (1-\alpha )b<br /> \end{eqnarray}$ möglichst gleich groß sind) -Ist das ein bekanntes Problem? Unter welchem Stcihwort finde ich Literatur dazu?
21.02.2010, 10:35	wisili	Auf diesen Beitrag antworten »
RE: Maximierung einer Funktion über Paare aus 2 Mengen A und B (im Beispiel) haben wiederholte «Elemente», A und B sind also keine Mengen, sondern endliche Folgen? Maximiert wird über alle Permutationen von A (oder natürlich B)? Ist alpha fest gewählt, oder variiert es? (Gemäss Beispiel scheint es fest.) Wieso nennst du den Summenterm «Funktion»: Welches sind die Argumente dieser Funktion? Kommen nur 0 und 1 als Elemente von A und B in Frage? ([0, 1] liest man als reelles Intervall und ist für alpha auch genau so gemeint.)
21.02.2010, 10:55	wisili	Auf diesen Beitrag antworten »
RE: Maximierung einer Funktion über Paare aus 2 Mengen $\begin{eqnarray} P_{A} \end{eqnarray}$ sei die Menge der Permutationen von A. Zu bestimmen wäre $\begin{eqnarray} \max\limits_{p\in P_{A}}\sum\limits_{i=1}^n \sqrt{\alpha \cdot a_{p(i)} + (1-\alpha )\cdot b_{i} } \end{eqnarray}$ Trifft das zu?
21.02.2010, 13:16	Strider	Auf diesen Beitrag antworten »
RE: Maximierung einer Funktion über Paare aus 2 Mengen Hallo 1000 dank für die Unterstützung. Sorry wegen der Ungenauigkeiten, ist ne Weile her, dass ich das letzte Mal mit mit Mathe beschäftigt habe In der Tat sind das also 2 Folgen und die Elemente sind aus dem Intervall [0,1]. Das mit der Permutation ist denke ich aber nicht so wie ich das gemeint habe. Ich brauche ja keine Permutation von A sondern immer Tupel aus A und B. Nochmal ein eindeutigeres Beispiel: n=2 A = (a1,a2) B = (b1,b2) Daraus lassen sich 2 Kombinationen bilden: (a1,b1) (a2,b2) oder (a1,b2) (a2,b1) Die Frage ist für welche dieser Kombinationen der Term dann der größere ist. Also: $\begin{eqnarray} <br /> \sqrt{\alpha a1 + (1-\alpha)b1} +\sqrt{\alpha a2 + (1-\alpha)b2} >< \sqrt{\alpha a1 + (1-\alpha)b2} +\sqrt{\alpha a2 + (1-\alpha)b1}<br /> \end{eqnarray}$ alpha ist fest und aus dem Intervall [0,1] Ich denke, es sollte sich eine Allgemeine Aussage darüber machen lassen, wie das Maximum zu erreichen ist, z.B wenn die Varianz var( $\begin{eqnarray} <br /> \alpha \cdot a + (1-\alpha )b<br /> \end{eqnarray*}$ ) möglichst klein ist. Wenn ich das Zeigen könnte wäre ich glücklich
Anzeige

21.02.2010, 14:16	wisili	Auf diesen Beitrag antworten »
RE: Maximierung einer Funktion über Paare aus 2 Mengen Damit kein Missverständnis aufkommt: Ich habe auch noch keine Antwort parat. Eine klare Fragestellung ist aber sicher ein erster Meilenstein. Statt zu sagen, A sei eine endliche Folge mit (z.B.) 6 Gliedern, kann man auch sagen, A sei ein 6-tupel: A = (a1, a2, a3, a4, a5, a6), B = (b1, b2, b3, b4, b5, b6) Die 6 senkrechten Kolonnen sind jetzt 6 Paare für die 6-gliedrige Summe. Permutiert man die Komponenten des Tupels A, so erhält man senkrecht 6 neue Paare, etc. A'= (a6, a2, a4, a1, a5, a3), B = (b1, b2, b3, b4, b5, b6) Das gäbe insgesamt 6! = 720 verschiedene Summen, worunter das Maximum (oder mehrere Maxima) zu finden sind. Ohne Beweis habe ich (vielleicht wie du?) die Vermutung, dass man für das Maximum die Tupel A und B aufsteigend ordnen muss, um dann die Paare «der Reihe nach» zu bilden (d.h. grosse Komponenten mit grossen zu paaren, kleine mit kleinen). Dass die Lösung noch von alpha abhängt, würde ich (bis jetzt) nicht vermuten, kann es aber auch (noch) nicht ausschliessen. Nachtrag: Bei der Varianz der n Summenglieder hätte ich eher ein Maximum erwartet. Aber ich kann mich täuschen. Meine vorerst nur intuitiven Urteile können nämlich die Wirkung der Wurzel noch nicht einbeziehen ...
21.02.2010, 16:11	Strider	Auf diesen Beitrag antworten »
Jetzt habe ich das mit der Permutation kapiert. Clever! Ich vermute genau das Gegenteil. Man muss wegen der Wurzel große mit kleinen paaren. Nach was für einem Stichwort müsste ich für dieses oder ähnliche Problem in der Literatur schauen?
21.02.2010, 17:10	wisili	Auf diesen Beitrag antworten »
Da muss ich passen; vielleicht weiss jemand anderer Rat. (Uebrigens: Bei deinem Beispiel A{0,0,1}, B{0,1,1}, alpha=0,5 vermute ich tatsächlich falsch!)
03.03.2010, 09:56	Strider	Auf diesen Beitrag antworten »
Falls hier nochmal jemand nachschaut: Fündig wird man beim Thema "Assortative matching" Beweisskizze: Ableitung der Wurzel nach a und b < 0 => kleine a "profitieren" stärker von großen b als große a => Lösung ist ein Negative Assortative Matching", sprich größte a mit kleinsten b etc.

Neue Frage »

Antworten »

Maximierung einer Funktion über Paare aus 2 Mengen

Verwandte Themen