Die Mathe-Redaktion - 24.06.2018 22:39 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt6 im Schwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 406 Gäste und 22 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » 2ⁿ Zahlen durch Summen von n Zahlen annähern
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich 2ⁿ Zahlen durch Summen von n Zahlen annähern
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2346
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-12-12

\(\begingroup\)
Hallo,

ein Kollege hat (etwas abstrahiert) folgendes Problem:



Gegeben ist eine Menge $Y\subset\mathbb{R}$ mit $2^n$ Elementen.
Gesucht sind $x_1,\ldots,x_n\in\mathbb{R}$ und eine Bijektion $S:Y\rightarrow\mathcal{P}(\{1,\ldots,n\})$ so, dass für $y\in Y$ die Summe $\sum_{k\in S(y)}x_k$ möglichst nahe an $y$ liegt, also z.B. so, dass $\sum_{y\in Y}\left|y-\sum_{k\in S(y)}x_k\right|^2$ möglichst klein ist.



Für gegebenes $S$ ist das Finden der $x_1,\ldots,x_n$ ein überbestimmtes lineares Gleichungssystem, für das man die beste Näherungslösung mit numerischen Methoden berechnen kann. Die Zahlen sind aber zu groß, um alle Möglichkeiten für $S$ durchzuprobieren.

Kommt dieses Problem jemandem bekannt vor und er kann mich auf Literatur verweisen? Hat jemand ein Gefühl dafür, wie kompliziert diese Fragestellung ist?

Viele Grüße
Stefan
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1175
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-12-15


2017-12-12 17:19 - darkhelmet im Themenstart schreibt:
Die Zahlen sind aber zu groß, um alle Möglichkeiten für <math>S</math> durchzuprobieren.

Für <math>Y=\{1,2,3,4\}</math>  komme ich auf <math>X=\{5/3,~ 8/3\}</math>  mit

<math>\displaystyle
f_2(Y)=(1-0)^2 + (2-\textstyle\frac{5}{3})^2 + (3-\textstyle\frac{8}{3})^2 + (4-\textstyle\frac{13}{3})^2
= \textstyle{4/3}
</math>

und besser geht es wohl nicht. Für ein vorgegebenes <math>Y\subset\mathbb{R}_\oplus</math> und eine Versuchsmenge <math>X</math> lassen sich deren <math>2^{|X|}</math> mögliche Summen <math>\sum_{x\in T\subseteq X}\,x</math> der Größe nach ordnen und den ebenfalls geordneten Zahlen von <math>Y</math> zuweisen, um <math>f_X(Y)</math> zu berechnen. Das scheint in diesem Fall eine optimale Bijektion <math>S</math> zu definieren, aber einen Beweis dafür habe ich nicht.


Für allgemeines  <math>Y=\{a,b,c,d\},~~ 0\le a<b<c<d</math>  gilt

<math>\displaystyle
X = \Bigl\{\,\frac{d+2b-c}{3},~ \frac{d-b+2c}{3}\,\Bigr\},\qquad
{\rm mit} ~ f_2(Y) = a^2 + \frac{(b+c-d)^2}{3}
</math>



  Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1175
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2017-12-16


2017-12-12 17:19 - darkhelmet im Themenstart schreibt:
Hat jemand ein Gefühl dafür, wie kompliziert diese Fragestellung ist?

Ich kenne diese Aufgabenstellung nicht und habe keine Ahnung, ob und wo sie sich anwenden lässt. Aber sie scheint mir interessant zu sein und ich hätte mögliche Anwendungen gerne kennengelernt. Da nach Gefühlen gefragt wird (die in meinem Fall nicht viel wert sind), würde ich darauf tippen, dass die Aufgabe vermutlich polynomialbeschränkt in <math>|Y|=2^n</math> ist.


Wie wäre es mit folgendem Algorithmus für <math>Y\subset\mathcal{R}_\oplus^{(2^n)}</math> :

[1] Wähle ein beliebiges <math>\bar X\subset\mathcal{R}_\oplus^n</math>
[2] while True:
[3]     Für <math>\bar X</math> bestimme ein <math>S</math>,
        indem du die <math>2^n</math> Summen <math>\sum_{x\in T\subseteq\bar X}x</math> der Größe nach ordnest.
        (Zeit <math>O(\,n|Y|+|Y|\log(|Y|)\,)=O(2^n\,n)</math>)
[4]     Für das gefundene <math>S</math> bestimme ein neues <math>X</math>,
        indem du die partiellen Ableitungen von <math>f_Y(X)</math> auf Null setzt.
        (Zeit <math>O(\,n|Y|+n^3)=O(2^n\,n)</math>)
[5]    Falls <math>X=\bar X</math> ist, breche ab;   ansonsten setze <math>X\rightarrow\bar X</math>

Offen bleibt die Frage, ob und wie schnell dieser Algorithmus endet.


Ich hätte gerne auch folgendes gewusst:
(1) Dürfen die Zahlen in <math>Y</math> verschiedene Vorzeichen haben oder nicht?
(2) Ist die Aufgabe auch für <math>|Y|\ne 2^n</math> definiert?
(3) Ist die Aufgabe auch für Multisets <math>(y_1,y_2,\ldots,y_{2^n})</math> definiert, wo sich die <math>y_k</math> unter Umständen wiederholen können?



  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2346
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2017-12-16

\(\begingroup\)
Hi Goswin,

schön, dass du dich für das Problem interessierst. Ich muss allerdings sagen, dass ich da schon mehr Zeit investiert habe, als ich eigentlich sollte. Nicht dass du dich in das Problem verbeißt und dich ärgerst, dass von mir nichts zurückkommt. Deshalb hatte ich auch eher nach einer bereits existierenden "Komplettlösung" gefragt.

2017-12-16 16:40 - Goswin in Beitrag No. 2 schreibt:
Aber sie scheint mir interessant zu sein und ich hätte mögliche Anwendungen gerne kennengelernt.

Grob gesagt will man eine elektrische Leitung bauen, deren Länge man dynamisch ändern können will mit Hilfe von $n$ Schaltern, die jeweils zwischen zwei verschieden langen Leitungsstücken umschalten können. Das ergibt $2^n$ mögliche Gesamtleitungslängen. Wenn man umgekehrt $2^n$ Gesamtleitungslängen hat, die realisierbar sein sollen, und sich fragt, wie man die Längen der Leitungsstücke wählen soll, kommt man auf etwas ähnliches wie dieses Problem. Mehr ins Detail will ich aber nicht gehen.

2017-12-16 16:40 - Goswin in Beitrag No. 2 schreibt:
(1) Dürfen die Zahlen in <math>Y</math> verschiedene Vorzeichen haben oder nicht?

Das ist egal. Wenn $x_1,\ldots,x_n$ eine Lösung für $Y$ ist, ist z.B. $x_1+\frac{C}{n},\ldots,x_n+\frac{C}{n}$ eine Lösung für $Y+C$ für alle $C\in\mathbb{R}$.

2017-12-16 16:40 - Goswin in Beitrag No. 2 schreibt:
(2) Ist die Aufgabe auch für <math>|Y|\ne 2^n</math> definiert?

Dann kann natürlich $S$ auch nicht bijektiv sein. Kann aber sein, dass diese Einschränkung mathematisch gar nichts bringt.

2017-12-16 16:40 - Goswin in Beitrag No. 2 schreibt:
(3) Ist die Aufgabe auch für Multisets <math>(y_1,y_2,\ldots,y_{2^n})</math> definiert, wo sich die <math>y_k</math> unter Umständen wiederholen können?

Das ist ja das gleiche wie zuzulassen, dass $Y$ weniger als $2^n$ Elemente hat. Also siehe (2).
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1175
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2017-12-17


2017-12-16 21:15 - darkhelmet in Beitrag No. 3 schreibt:
Nicht dass du dich in das Problem verbeißt und dich ärgerst, dass von mir nichts zurückkommt. Deshalb hatte ich auch eher nach einer bereits existierenden "Komplettlösung" gefragt.

Mach dir da mal keine Sorge. Aber ich dachte, mein Algorithmus in Beitrag_2 käme einer "Komplettlösung" verdächtig nahe, oder?



2017-12-16 21:15 - darkhelmet in Beitrag No. 3 schreibt:
2017-12-16 16:40 - Goswin in Beitrag No. 2 schreibt: (3) Ist die Aufgabe auch für Multisets <math>(y_1,y_2,\ldots,y_{2^n})</math> definiert, wo sich die <math>y_k</math> unter Umständen wiederholen können?

Das ist ja das gleiche wie zuzulassen, dass <math>Y</math> weniger als <math>2^n</math> Elemente hat. Also siehe (2).

Das ist nicht das gleiche, da im Gegensatz zu (2) bei (3) angegeben wird, für welche Zahlen in <math>Y</math> es mehrere Summen geben muss und genau wie viele der Summen.



2017-12-16 21:15 - darkhelmet in Beitrag No. 3 schreibt:
Wenn <math>x_1,\ldots,x_n</math> eine Lösung für <math>Y</math> ist, ist z.B. <math>x_1+\frac{C}{n},\ldots,x_n+\frac{C}{n}</math> eine Lösung für <math>Y+C</math> für alle <math>C\in\mathbb{R}.</math>

Diese Behauptung ist einfach falsch, und Gegenbeispiele sind leicht zu finden.  Zum Beispiel, gibt es für <math>Y=\{0,1,2,3\}</math> die offenbare Optimallösung <math>X=\{1,\,2\}</math> mit <math>f_2(Y) = f_2(Y|X)=0</math>.  Für <math>\bar Y=\{1,2,3,4\}</math> dagegen müsste laut deiner Behauptung <math>\bar X=\{1.5,\,2.5\}</math> eine Lösung sein. Das ist sie aber nicht, da <math>f_2(\bar Y|{\bar X})=1.5</math> ist, während in Beitrag_1 bereits eine Lösung mit <math>f_2(\bar Y)=1.333</math> aufgezeigt wurde.



  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2346
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2017-12-18

\(\begingroup\)
2017-12-17 20:40 - Goswin in Beitrag No. 4 schreibt:
Aber ich dachte, mein Algorithmus in Beitrag_2 käme einer "Komplettlösung" verdächtig nahe, oder?

Kann ich nicht beurteilen.

Die Verallgemeinerung (3) interessiert mich dann nicht.

Bei (1) hast du Recht, da habe ich was durcheinandergebracht. Wenn es hilft, kann man annehmen $Y\subset[0,\infty[$ und $0\in Y$.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1175
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2017-12-24


2017-12-18 16:00 - darkhelmet in Beitrag No. 5 schreibt:
2017-12-17 20:40 - Goswin in Beitrag No. 4 schreibt:
Aber ich dachte, mein Algorithmus in Beitrag_2 käme einer "Komplettlösung" verdächtig nahe, oder?
Kann ich nicht beurteilen.

Deine Skepsis besteht zu Recht.  Der Algorithmus ist in dieser Form unbrauchbar, weil er stagniert: er hält an, ohne ein Optimum zu erreichen. Ob er repariert werden kann, bleibt abzuwarten.


2017-12-18 16:00 - darkhelmet in Beitrag No. 5 schreibt:
Die Verallgemeinerung (3) interessiert mich nicht.
[...]
Wenn es hilft, kann man annehmen <math>Y\subset[0,\infty[</math> und <math>0\in Y</math>.

Auf den ersten Blick denke ich, dass das sehr wohl hilft: die praktische Anwendung hat offenbar nur positive Daten und die Aufgabestellung ist auch so schon komplex genug. Ab nun werde ich also voraussetzen, dass alle Datenwerte positiv und verschieden voneinander sind.

Der Fall mit weniger als <math>2^n-1</math> Daten scheint aber eine betrachtenswerte Erweiterung zu sein, da die Anpassung an eine vorgegebene Datenmenge mit größerem <math>n</math> immer besser (oder zumindest nicht schlechter) wird.

Wie viele Daten sollen in der praktischen Anwendung angepasst werden?



  Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1175
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2017-12-29


Hallo darkhelmet,

Für <math>n\le4</math> und der Bedingung, dass <math>S</math> bijektiv sein soll, ist dein Problem nun gelöst und die optimalen <math>X</math> in Sekundenbruchteilen berechenbar: man muss einfach nur 14 Anordnungen von Teilmengen durchprobieren. Für <math>n=5</math> sieht das ganze ebenfalls machbar aus, aber das überlassen wir am besten den direkt Betroffenen.

Freilich pickst du dir mit den Bedingungen <math>S~\mathrm{bijektiv}</math>, <math>|Y|=2^n</math> die Rosinen aus dem Kuchen. Warum sollte <math>S</math> eigentlich bijektiv sein, genügt nicht auch bei <math>|Y|=2^n</math> eine beliebige Zuweisung von Teilmengen an die Daten? Und Fälle wie <math>n=3,~ |Y|=4</math> oder <math>n=3,~ |Y|=12</math>, oder für allgemeines <math>|Y|>n</math>, kommen mir erheblich schwieriger vor als der von dir aufgestellte.

Bei der Anwendung die du erwähnt hast ist es schon seltsam, dass jemand ausgerechnet <math>2^n</math> Leitungslängen genau <math>1\leftrightarrow 1</math> anzupassen hat!




  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2346
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2017-12-29


Das sieht ja vielversprechend aus. Vielen Dank! Es wird aber wahrscheinlich ein paar Tage dauern, bis ich mir das genauer anschauen kann.



  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2346
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2018-01-11

\(\begingroup\)
Eins verstehe ich noch nicht: Ist es offensichtlich, dass für eine optimale Lösung die Funktion $y\mapsto\sum_{k\in S(y)}x_k$ streng monoton steigend ist?

Das ist ja die Grundlage für die Verbindung zur Fragestellung des anderen Threads. Klingt nicht unplausibel, aber ich habe im Moment keine Beweisidee.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1175
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-01-13

\(\begingroup\)
2018-01-11 14:28 - darkhelmet in Beitrag No. 9 schreibt:
Ist es offensichtlich, dass für eine optimale Lösung die Funktion <math>y\mapsto\sum_{k\in S(y)}x_k</math> streng monoton steigend ist?

Monoton steigend sicher; dass sie streng monoton ist, habe ich für den Themenstrang hier nicht vorausgesetzt. Das Gegenteil ist freilich falsch: es gibt viele Lösungen mit monoton steigender Funktion die nicht optimal sind.

Beweis der Monotonie:
Es sei <math>\chi(y)=\sum_{k\in S(y)}x_k</math> und <math>y\mapsto\chi(y)</math> eine nicht monoton steigende Funktion. Dann gibt es <math>y_r<y_s</math> mit <math>\chi(y_r)>\chi(y_s)</math>, und es gilt


<math>\displaystyle
\sum_{y\in Y}\bigl(y-\chi(y)\bigr)^2
~= \!\!\sum_{y\in Y\setminus\{y_r,y_s\}}
\!\!\!\!\!\bigl(y-\chi(y)\bigr)^2
~+~ \bigl(y_r-\chi(y_r)\bigr)^2 ~+~ \bigl(y_s-\chi(y_s)\bigr)^2 ~=~
\\[12pt]
~\qquad = \!\!\sum_{y\in Y\setminus\{y_r,y_s\}}\!\!\!\!\!
\bigl(y-\chi(y)\bigr)^2
~+~ \bigl(y_r-\chi(y_s)\bigr)^2 ~+~ \bigl(y_s-\chi(y_r)\bigr)^2 ~+~
\\[3pt]
~\qquad\qquad\qquad\qquad
~+~ 2\,\bigl(y_s-y_r\bigr)\,\bigl(\chi(y_r)-\chi(y_s)\bigr)
\\[15pt]
~\qquad > \!\!\sum_{y\in Y\setminus\{y_r,y_s\}}\!\!\!\!\!
\bigl(y-\chi(y)\bigr)^2
~+~ \bigl(y_r-\chi(y_s)\bigr)^2 ~+~ \bigl(y_s-\chi(y_r)\bigr)^2
</math>

Dann aber könnten wir den Zielwert <math>f(Y)</math> verkleinern indem wir <math>S(y_r),S(y_s)</math> mitqeinander austauschen, und <math>y\mapsto\chi(y)</math> ist somit nicht optimal.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]