Vektorauswahl Problem

23.09.2011, 09:38

OhNo

Vektorauswahl Problem

Hallo,

ich bin auf ein Problem gestoßen und komme bsiher zu keiner brauchbaren Lösung. Vielleicht hat einer von euch eine passende Idee oder hat schon ein ähnliches Problem gehabt:

Gegeben ist eine endliche Menge von $n$ verschiedenen Einheitvektoren aus dem R³.
Zu jedem Vektor $v$ nimmt man den negativen Vektor $-v$ hinzu.

Ziel: Aus jedem Paar $v,-v$ soll nun ein Vektor ausgewählt werden, so dass
die hierdurch insgesamt erhaltene Menge von Vektoren eine möglichst große Vektorsumme ergibt

Grüße OhNo

23.09.2011, 10:10

René Gruber

Auf diesen Beitrag antworten »

"Möglichst groß" ist dann wohl im Sinne des Betrages zu verstehen? Interessantes Problem.

23.09.2011, 10:21

OhNo

Auf diesen Beitrag antworten »

Ja der Betrag des resultierenden Vektors sollte möglichst groß sein. Das gleiche Kriterium müsste dann auch die Spannweite erfüllen. Das würde bedeuten: Ist die Spannweite klein ist der Betrag möglichst groß.

23.09.2011, 15:04

gonnabphd

Auf diesen Beitrag antworten »

Hi,

Könntest du noch erzählen, woher das Problem stammt? Und wie gross ist n typischerweise (bzw. ist das ein Problem für eine Anwendung oder aus einem Kurs über Algorithmen oder sowas)?

Grüsse Wink

23.09.2011, 15:23

OhNo

Auf diesen Beitrag antworten »

Hi,

das problem hat sich im Laufe meiner Bachelorarbeit ergeben. Es rührt daher, dass eine Spannung in der Machanik auf einer Schnittfläche wirkt. Theoretisch also in beide Richtungen der Normalen dieser Fläche. Ich möchte nun zu einer Belastung durch n Lastfälle die resultierende Belastung errechenen oder die mittlere Hauptlastrichtung. Die Anzahl der Lastfälle kann theoretisch beliebig groß sein. Im aktuellen Rahmen <5. Die Lösung des Problems möchte ich im Anschluss in Matlab implementiert werden.

Ich hoffe ich konnte euch das einigermaßen verständlich erklären. Vielen Dank dassi hr euch Gedanken macht.

24.09.2011, 03:43

gonnabphd

Auf diesen Beitrag antworten »

Etwas effizientes fällt mir zwar nicht ein, aber für kleine n kann man ja einfach alle Möglichkeiten durchprobieren lassen. Um das ein bisschen geordnet zu gestalten, könnte man die gegebenen Vektoren $\begin{eqnarray*} v_1, \dots, v_n \end{eqnarray*}$ in eine Matrix $\begin{eqnarray*} \begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} \end{eqnarray*}$ schreiben und diese auf Vektoren mit Einträgen aus $\begin{eqnarray*} \{-1,1\} \end{eqnarray*}$ anwenden. Wenn man alle Vektoren in $\begin{eqnarray*} \{-1,1\}^n \end{eqnarray*}$ durchgeht, kommt man genau auf alle möglichen Summen, welche du betrachten willst.

Dabei muss man sich dann einfach denjenigen Vektor merken, dessen Bild die maximale Norm hat und löst so das Problem.

Allerdings kenne ich mich mit Algorithmen nicht so wirklich aus und es ist gut möglich, dass es einen halbwegs anständigen gibt (der nicht $\begin{eqnarray*} \mathcal O(2^n) \end{eqnarray*}$ ist).

So viel zu meinen Ideen.

24.09.2011, 10:11

OhNo

Auf diesen Beitrag antworten »

Hi gonnabphd danke für deinen nächtlichen Einsatz. An eine Permutationsvariante habe ich auch schon gedacht und es als zu aufwendig verworfen. Aber diese Matrix formulierung könnte es interessant machen, da ich das ganze ja in Matlab umsetzten will. Allerdings habe ich noch nicht ganz erstanden wie deine idee exakt funktioniert.

Zitat:

Original von gonnabphd
$\begin{eqnarray*} \begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} \end{eqnarray*}$ diese auf Vektoren mit Einträgen aus $\begin{eqnarray*} \{-1,1\} \end{eqnarray*}$ anwenden.

meinst du damit $\begin{eqnarray*} \begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} \cdot \begin{bmatrix} -v_1 & \cdots & -v_n \end{bmatrix} \end{eqnarray*}$ ?

Ich steh gerade ein bischen auf dem Schlauch sorry.

24.09.2011, 15:47

gonnabphd

Auf diesen Beitrag antworten »

$\begin{eqnarray*} A = \begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} \end{eqnarray*}$ ist eine 3 x n Matrix.

Mal ein Beispiel wie ich mir das gedacht hatte mit n = 4:

$\begin{eqnarray*} v_1 = (1,4,2)^t, \; v_2 = (5,3,2)^t, \; v_3 = (5,3,1)^t, \; v_4 = (7,3,6)^t \end{eqnarray*}$

Dann wäre

$\begin{eqnarray*} A = \begin{pmatrix} 1 & 5 & 5 & 7\\ 4 & 3 & 3 & 3 \\ 2 & 2 & 1 & 6 \end{pmatrix} \end{eqnarray*}$

Nun beginnt man z.B. erst mit dem Vektor $\begin{eqnarray*} w_1 = (1,1,1,1)^t \end{eqnarray*}$ :

$\begin{eqnarray*} A\cdot w_1 = v_1 + v_2 + v_3 + v_4 \end{eqnarray*}$

und berechnet die Norm von $\begin{eqnarray*} A\cdot w_1 \end{eqnarray*}$ .

dann weiter mit $\begin{eqnarray*} w_2 = (-1,1,1,1)^t \end{eqnarray*}$

$\begin{eqnarray*} A\cdot w_1 = -v_1 + v_2 + v_3 + v_4 \end{eqnarray*}$

etc. etc.

Man müsste also einen Weg finden, alle $\begin{eqnarray*} 2^n \end{eqnarray*}$ Vektoren $\begin{eqnarray*} w_i \end{eqnarray*}$ in $\begin{eqnarray*} \underbrace{\{-1,1\} \times \{-1,1\} \times \dots \times \{-1,1\}}_{\text{n mal}} \end{eqnarray*}$ nacheinander zu generieren.

Übrigens: Wenn du blosse eine Abschätzung für die maximale Grösse des Vektors $\begin{eqnarray*} (-1)^{\epsilon_1} v_1 + \dots + (-1)^{\epsilon_n} v_n \end{eqnarray*}$ haben willst, dann könntest du bspw. einfach die Matrix $\begin{eqnarray*} A \end{eqnarray*}$ zu einer n x n Matrix mit Nullen ergänzen, also

$\begin{eqnarray*} \tilde A = \begin{pmatrix} A \\ 0\end{pmatrix} \end{eqnarray*}$

bilden, und dann die 2-Norm von $\begin{eqnarray*} \tilde A \end{eqnarray*}$ berechnen. Damit bekommst du für alle Vektoren $\begin{eqnarray*} w \end{eqnarray*}$ aus $\begin{eqnarray*} \{-1,1\}^n \end{eqnarray*}$ :

$\begin{eqnarray*} \| A\cdot w \|_2 = \| \tilde A \cdot w \|_2 \le \|\tilde A \|_2 \|w\|_2 = \sqrt{n} \|\tilde A\|_2 \end{eqnarray*}$

Also eine obere Schranke für die Länge des längsten Vektors. Interessant wäre es vielleicht auch, zu untersuchen wie nahe diese obere Schranke an das Optimum herankommt.

24.09.2011, 17:03

OhNo

Auf diesen Beitrag antworten »

Zitat:

Original von gonnabphd
Übrigens: Wenn du blosse eine Abschätzung für die maximale Grösse des Vektors

eigentlich ist mir die Größe nicht wichtig. wichtig ist nur die Richtung.

Wenn ich bei deinem Beispiel bleibe wäre es dann richtig

$\begin{eqnarray*} w \cdot A = \begin{pmatrix}1 & 1 & 1 & 1\\ -1 & 1 & 1 & 1\\ -1 & - 1 & 1 & 1\\ -1 & -1 & -1 & 1\\ -1 & -1 & -1 & -1\\ -1 & 1 & 1 & -1\\ \vdots & \vdots & \vdots & \vdots\end{pmatrix} \cdot \begin{pmatrix} 1 & 5 & 5 & 7\\ 4 & 3 & 3 & 3 \\ 2 & 2 & 1 & 6 \end{pmatrix} \end{eqnarray*}$

und davon dann die Summe zuberechenen?

Zitat:

Original von gonnabphd
Man müsste also einen Weg finden, alle $\begin{eqnarray*} 2^n \end{eqnarray*}$ Vektoren $\begin{eqnarray*} w_i \end{eqnarray*}$ in $\begin{eqnarray*} \underbrace{\{-1,1\} \times \{-1,1\} \times \dots \times \{-1,1\}}_{\text{n mal}} \end{eqnarray*}$ nacheinander zu generieren.

Dafür könnte ich diese Funktion nutzen
http://www.mathworks.de/help/toolbox/stats/combnk.html

24.09.2011, 17:48

gonnabphd

Auf diesen Beitrag antworten »

Zitat:

Original von OhNo
Wenn ich bei deinem Beispiel bleibe wäre es dann richtig

$\begin{eqnarray*} w \cdot A = \begin{pmatrix}1 & 1 & 1 & 1\\ -1 & 1 & 1 & 1\\ -1 & - 1 & 1 & 1\\ -1 & -1 & -1 & 1\\ -1 & -1 & -1 & -1\\ -1 & 1 & 1 & -1\\ \vdots & \vdots & \vdots & \vdots\end{pmatrix} \cdot \begin{pmatrix} 1 & 5 & 5 & 7\\ 4 & 3 & 3 & 3 \\ 2 & 2 & 1 & 6 \end{pmatrix} \end{eqnarray*}$

und davon dann die Summe zuberechenen?

Nein. Dieses Matrixprodukt ist doch noch nicht einmal definiert. Allerdings gibt dir (mit deiner Schreibweise)

$\begin{eqnarray*} A\cdot w^t \end{eqnarray*}$

eine Matrix in der alle möglichen Summen $\begin{eqnarray*} (-1)^{\epsilon_1} v_1 + \dots + (-1)^{\epsilon_n} v_n \end{eqnarray*}$ in den Spalten spalten stehen.

Mir ist noch nicht so ganz klar, was diese Vektorsummen dann physikalisch darstellen sollen. Also man hat eine Fläche und auf diese Fläche wirken Kräfte. Und du willst nun die Gesamtkraft ausrechnen? Falls ja: Wieso kennt man denn die Kräfte bis auf das Vorzeichen?
Ich kann mir im Moment gerade keine physikalische Situation vorstellen, bei der das der Fall ist - aber vielleicht verstehe ich dich auch ganz falsch.

24.09.2011, 18:20

OhNo

Auf diesen Beitrag antworten »

Zitat:

Original von gonnabphd
Nein. Dieses Matrixprodukt ist doch noch nicht einmal definiert. Allerdings gibt dir (mit deiner Schreibweise)

$\begin{eqnarray*} A\cdot w^t \end{eqnarray*}$

eine Matrix in der alle möglichen Summen $\begin{eqnarray*} (-1)^{\epsilon_1} v_1 + \dots + (-1)^{\epsilon_n} v_n \end{eqnarray*}$ in den Spalten spalten stehen.

Die Reihe mit der größten Summe müsste doch dann die richtige Richtung sein. also nochmal das Problem:

Man hat ein Bauteil auf das Kräfte wirken. Im inneren ergeben sich Spannungen. Diese liegen in einer Fläche. Für meine Anwendung ist es egal ob diese Spannungen Zug- oder Druckspannungen sind.

Die Spannungen die ich betrachte treten nicht gleichzeitig auf. Überlagern sich also nicht. Während die Fläche die gleiche, bleibt ändern die Spannungen ihre Richtung. Nun möchte ich die mittlere Richtung der Spannungen ermitteln. Ein einfacher Mittelwert reicht hier nicht aus, da sich entgegengesetze Spannungen eliminieren. Da ich aber zwischen negativer und positver Spannung nicht unterschiede müssen diese sich addieren und diese Richtung "bestärken" anstatt sie zu "schwächen".

Frag gerne ochmal nach falls ich mich unverständlich ausgedrückt habe.

24.09.2011, 20:02

gonnabphd

Auf diesen Beitrag antworten »

Zitat:

Die Reihe mit der größten Summe müsste doch dann die richtige Richtung sein.

Ich würde sagen, die Spalte in $\begin{eqnarray*} A\cdot w^t \end{eqnarray*}$ mit dem grössten Betrag wäre die Richtung, die du suchst. (jedenfalls ist das dann die grösste Vektorsumme wie im Threadstart beschrieben.)
Denn jede Spalte ist ja eine Summe $\begin{eqnarray*} (-1)^{\epsilon_1} v_1 + \dots + (-1)^{\epsilon_n} v_n \end{eqnarray*}$ , die Reihen haben mMn keine Bedeutung.

25.09.2011, 10:54

OhNo

Auf diesen Beitrag antworten »

ja du hast natürlich Recht. Habs per Hand gerade nachgerechnet. Die Spalten sind die gesuchten Vektroren.

Grüße

28.09.2011, 02:04

gonnabphd

Auf diesen Beitrag antworten »

Mir ist gerade noch eine Idee gekommen, wie man vielleicht einen effizienten Algorithmus finden könnte:

Dein Problem kann ja zurückgeführt werden auf folgendes: Gegeben eine Matrix A in $\begin{eqnarray*} \mathbb R^{3\times n} \end{eqnarray*}$ , finde diejenige Ecke des Hyperquaders $\begin{eqnarray*} [-1,1]^n \end{eqnarray*}$ , für welche $\begin{eqnarray*} |Ax| \end{eqnarray*}$ maximal ist.

Ich vermute mal, dass es gute Algorithmen gibt, um folgendes Problem zu lösen:

Finde einen Punkt $\begin{eqnarray*} x_0\in [-1,1]^n \end{eqnarray*}$ welcher

$\begin{eqnarray*} [-1,1]^n \to \mathbb R, \; x \mapsto |Ax| \end{eqnarray*}$

maximiert. Ein solcher Punkt liegt natürlich auf einer Seitenfläche des Hyperquaders.
Ich würde nun mal vermuten, dass sich zeigen lässt, dass dein gesuchter Punkt dann eine der Ecken dieser Seite sein muss (weil die am nächsten liegen).

Ich kenne mich mit Optimierung überhaupt nicht aus, aber ich denke mal, dass man mit obigem eine polynomielle Laufzeit erreichen könnte (wenn denn alles tatsächlich so ist, wie ich vermute...).

Ich weiss nicht, ob's noch relevant ist, oder ob du dich weiter damit beschäftigen willst, aber ich dachte ich schreib den Gedanken einfach mal hier auf.

Neue Frage »

Antworten »

Vektorauswahl Problem

Verwandte Themen