Optimierungsproblem spitze Winkel

29.01.2008, 13:47

koffer

Optimierungsproblem spitze Winkel

Hallo zusammen,

ich habe folgendes Optimierungproblem:

Gegeben sind eine Anzahl Vektoren $\begin{eqnarray*} \vec{v_1} \ldots \vec{v_n} \end{eqnarray*}$ . Gesucht ist nun ein Vektor $\begin{eqnarray*} \vec{w} \end{eqnarray*}$ , der zu möglichst vielen der gegebenen Vektoren einen spitzen Winkel bildet, also dessen Skalarprodukt $\begin{eqnarray*} \vec{w}^T \cdot \vec{v_i} \end{eqnarray*}$ für möglichst viele Vektoren $\begin{eqnarray*} \vec{v_i} \end{eqnarray*}$ größer 0 ist.

Die Länge des Vektors $\begin{eqnarray*} \vec{w} \end{eqnarray*}$ ist dabei egal, gerne kann sie als 1 angenommen werden.

Wie kann ich das rauskriegen?

Viele Grüße,
K.

29.01.2008, 20:57

Tomtomtomtom

Auf diesen Beitrag antworten »

Intuitiv würde ich als ersten Versuch folgendes machen: Alle v_i's auf Länge 1 normieren, und deren Summe bilden. Über die mathematische Begründung habe ich mir erstmal noch keine Gedanken gemacht, ist nur eine Idee.

Edit: Die Idee war wohl falsch, zumindest fällt mir gerade ein Gegenbeispiel ein.

30.01.2008, 16:04

koffer

Auf diesen Beitrag antworten »

Hmm. Hat sonst jemand eine Idee?

21.02.2008, 18:00

koffer

Auf diesen Beitrag antworten »

Ich bin nach wie vor an einer Antwort interessiert!

Ist die Frage zu speziell? Oder zu schwierig? Oder unklar gestellt?

Ratlose Grüße
k.

21.02.2008, 18:59

Auf diesen Beitrag antworten »

Hast du einen speziellem Vektorraum im Sinn?

Die Frage kann man zwar in beliebigen Vektorräumen mit Skalarprodukt stellen, aber z.B. für $\begin{eqnarray*} \mathbb{R}^2 \end{eqnarray*}$ fällt eine Lösung (mir zumindest) leichter als in einem beliebigen VR. Augenzwinkern

21.02.2008, 20:03

Tomtomtomtom

Auf diesen Beitrag antworten »

Es ist halt einfach schwer. Die Zielfunktion die du im Sinn hast, nimmt nur diskrete Werte an, ist unstetig, und der Raum wird in (ziemlich große) Teilmengen zerlegt, auf denen die Zielfunktion denselben Wert hat.

Damit kannst du schonmal alle Verfahren die irgendwie mit Ableitungen arbeiten vergessen, und man braucht ne richtig gute Idee.

26.02.2008, 17:36

koffer

Auf diesen Beitrag antworten »

@ Arthur: Nein, einen speziellen Vektorraum habe ich nicht im Sinn. Gerne kannst Du den $\begin{eqnarray*} \mathbb{R}^2 \end{eqnarray*}$ annehmen, das ganze lässt sich dann sicher für höherdimensionale Raume erweitern.

@Tom: Auf eine ähnliche Lösung wie Du bin ich auch gekommen? Wie sah denn Dein Gegenbeispiel aus? Mir fällt nur ein, dass man Probleme bekommt, wenn die Summe aller Vektoren der Nullvektor ist. Aber sonst müsste das doch funktionieren, oder?

26.02.2008, 19:07

Tomtomtomtom

Auf diesen Beitrag antworten »

Ich hab mir das ungefähr so überlegt. Ich hoffe die Paint-Skizze bringts einigermaßen rüber, mir fällt grad nix anderes ein, mit dem ich das zeichnen kann.

Der blaue und die grünen Vektoren sind gegeben. Das Ergebnis ist (natürlich nur ungefähr) der rote Vektor, oder jedenfalls irgendein Vektor der nach oben zeigt, und damit ausschließlich mit dem blauen Vektor einen spitzen Winkel bildet. Besser ist natürlich jeder nach unten zeigende Vektor, denn ein solcher produziert zwei spitze Winkel zu den grünen Vektoren.

Noch krasser wird das ganze, wenn du noch mehr vom Typ her den grünen ähnlichen hinzunimmst, und diese weit genug von unten an die x-Achse schiebst (ohne zu dieser parallel zu sein). Das Ergebnis bleibt wieder, daß du mit diesem Verfahren einen Vektor erhältst, der nach oben zeigt, und der damit nur zu einem einzigen der n gegebenen Vektoren einen spitzen Winkel bildet, und zu n-1 nicht, obwohl man sofort einen Vektor sieht, der zu n-1 Vektoren einen spitzen Winkel bilden könnte (nämlich wieder jeder der senkrecht nach unten zeigt).

Das einzige was ich dir mathematisch sicher sagen kann ist: Es macht erstmal Sinn, alle gegebenen Vektoren auf 1 zu normieren, denn das ändert nichts an der Aufteilung des Raumes in Gebiete, in denen ein Vektor spitzwinklig auf einer Teilmenge der gegebenen Menge von Vektoren steht. Bei allem anderen kann ich nur vermuten, daß du allenfalls Heuristiken erwarten kannst, die dir eine annähernd gute Lösung liefern. Eine exakte Lösung sehe ich nicht.

27.02.2008, 12:09

koffer

Auf diesen Beitrag antworten »

Ja, das Beispiel leuchtet mir ein.

Also als mathematische Formulierung würde mir zumindest folgendes einfallen:
$\begin{eqnarray*} \vec{w} = \arg\max_{\vec{w}} \sum_{i=1}^n~sign(\vec{w}^T \cdot \vec{v}_i) \end{eqnarray*}$
Nur das ist vermutlich wegen der nichtlinearen Signum-Funktion nicht so ohne weiteres abzuleiten...
Oder gibt's da eine Regel?

27.02.2008, 14:05

Auf diesen Beitrag antworten »

Also im $\begin{eqnarray*} \mathbb{R}^2 \end{eqnarray*}$ hätte ich folgenden Lösungsvorschlag:

Man sortiert die Vektoren der Winkelreihenfolge nach auf. Jetzt zählt man ür jeden Vektor, wieviel Vektoren im nächsten Halbkreis (bei Vorgabge einer Drehrichtung) liegen. Bei dem Vektor, wo das Maximum dieser Anzahl ist, nimmt man den "mittleren" Winkel dieses Halbkreises als die Richtung deines $\begin{eqnarray*} \vec{w} \end{eqnarray*}$ .

Ziemlich mies vom Aufwand her, nämlich $\begin{eqnarray*} O(n^2) \end{eqnarray*}$ , etwas besser organisiert ist vielleicht $\begin{eqnarray*} O(n\log(n)) \end{eqnarray*}$ drin, hab ich jetzt nicht genauer drübe rnachgedacht. Jedenfalls ist die Einschätzung

Zitat:

Original von koffer
das ganze lässt sich dann sicher für höherdimensionale Raume erweitern.

auf diesen Lösungsweg bezogen vollkommen unzutreffend, weil es i.a. keine derart totale Ordnung der Vektorenrichtungen gibt.

27.02.2008, 14:46

Tomtomtomtom

Auf diesen Beitrag antworten »

Zitat:

Original von koffer
Ja, das Beispiel leuchtet mir ein.

Also als mathematische Formulierung würde mir zumindest folgendes einfallen:
$\begin{eqnarray*} \vec{w} = \arg\max_{\vec{w}} \sum_{i=1}^n~sign(\vec{w}^T \cdot \vec{v}_i) \end{eqnarray*}$
Nur das ist vermutlich wegen der nichtlinearen Signum-Funktion nicht so ohne weiteres abzuleiten...
Oder gibt's da eine Regel?

Wie ich schon erwähnte, werden bei dieser Problemformulierung höchstens ableitungsfreie Verfahren funktionieren, da die Zielfunktion fast überall konstant ist (und damit deren Ableitung fast überall 0 ist).

Und Arthur Dent's Methode läßt sich durchaus verallgemeinern, im IR^3 zum Beispiel so:

Jedes Paar von (linear unabhängigen) Vektoren spannt eine Ebene auf. Also ordnest du jedem Paar von Vektoren zwei Zahlen zu, nämlich die beiden Anzahlen von Vektoren, die in den beiden durch die Ebene voneinander abgetrennten Halbräumen liegen. Am Ende suchst du das Paar aus, bei dem auf einer Seite das Maximum liegt, und nimmst einen Normalenvektor der Ebene in diese Richtung. Ist von der Komplexität allerdings nochmal deutlich ungünstiger als im IR^2, ich denke da kommt O(n^3) raus.

Im IR^4 könnte das analog gehen, mir fehlt nur gerade die geometrische Vorstellung. Wenn ich mich richtig erinnere trennt ein dreidimensionaler Unterraum den IR^4 in zwei disjunkte Halbräume. Wenn ja, dann funktioniert das Verfahren und hat Komplexität O(n^4). Analog dann IR^n.

Ich finde die Methode gut, sie beruht im Prinzip aus dem aufstellen einer Menge von Kandidaten und dem anschließenden systematischen durchsuchen. Man muß sich nur noch überlegen, das es immer eine Lösung in der Kandidatenmenge gibt. Das müßte eventuell über einen Widerspruchsbeweis gehen.

Und ein bißchen muß man noch aufpassen, was man macht, wenn es im IR^n schon n linear abhängige Vektoren gibt.

Edit 18:10 Uhr: Einige begriffliche Fehler ersetzt.

27.02.2008, 17:37

Auf diesen Beitrag antworten »

@Tom^4

Interessant, soweit habe ich gar nicht gedacht, als ich die Erweiterungsmöglichkeiten leichtfertig abgetan habe... Augenzwinkern

Wenn man mal in Abwandlung der Problemstellung "spitz" durch "nichtstumpf" ersetzt, dann kann man nach deinen Betrachtungen schon mal soviel sagen:

Die maximale Anzahl Vektoren mit nichtstumpfem Winkel zu einem passenden Vektor $\begin{eqnarray*} \vec{w} \end{eqnarray*}$ in einem $\begin{eqnarray*} d \end{eqnarray*}$ -dimensionalen Vektorraum mit $\begin{eqnarray*} n\geq d-1 \end{eqnarray*}$ ist mindestens

$\begin{eqnarray*} d-1 + \left\lceil \frac{n-(d-1)}{2} \right\rceil = \left\lceil \frac{n+d-1}{2} \right\rceil \end{eqnarray*}$ .

Ersetzt man "nichtstumpf" wieder durch "spitz", gilt das leider nicht mehr, man denke nur an das Beispiel von n=2 genau entgegengesetzten Vektoren im $\begin{eqnarray*} \mathbb{R}^2 \end{eqnarray*}$ . Augenzwinkern

Neue Frage »

Antworten »

Optimierungsproblem spitze Winkel

Verwandte Themen