Gleichungssystem mit Nebenbedingung

12.04.2008, 12:49	Mazze	Auf diesen Beitrag antworten »
Gleichungssystem mit Nebenbedingung Huhu alle miteinander, vorne weg erstmal was wir haben $\begin{eqnarray} B \in \mathbb{R}^{n \times m}, x \in \mathbb{R}^{m}, y \in \mathbb{R}^n, \sum_{j = 1}^{m}B_{ij} = 1 \forall i \in \{1,...,n\},B_{ij} > 0 \end{eqnarray}$ Ich würde gerne das LGS $\begin{eqnarray} -Bx = y \end{eqnarray}$ unter der Bedingung $\begin{eqnarray} x_i < 0, \forall i \in \{1,...,m\} \text{ und } \|\|x\|\| \text{ groß } \end{eqnarray}$ lösen. Die Frage ist natürlich ob eine solche Lösung überhaupt existiert. Für kleine Beispiele macht man sich das schon klar aber meine B's sind im Bereich $\begin{eqnarray} a \times 195 \end{eqnarray}$ wobei a von 1 - 120 Läuft. Wenn ich zum Beispiel die Pseudoinverse (in matlab) bilde, dann bekomme ich meistens auch positive Einträge in x. Meine Idee war folgendes zu versuchen. Der Kern der pseudoinversen von B ist nicht leer, also habe ich mir gedacht die Funktion $\begin{eqnarray} f(x) \text{ der Art zu betrachten das } -Bf(x) = y \end{eqnarray}$ , man kann dann für f(x) zum Beispiel setzen $\begin{eqnarray} f(x) = - B^{\dagger}(y + x) \end{eqnarray}$ wobei x aus dem Kern von $\begin{eqnarray} B^\dagger \end{eqnarray}$ Wir wollen jetzt den Betrag von f(x) maximieren unter der Nebenbedingung das $\begin{eqnarray} f(x)_i < 0 \end{eqnarray}$ , also schreiben wir $\begin{eqnarray} \tilde{f}(x) = \\|f(x)\\|^2 \end{eqnarray}$ und haben dann das Optimierungsproblem $\begin{eqnarray} \max_{x \in \text{Kern}(B^\dagger} \tilde{f}(x) + \sum_{i=1}^{m}\lambda_i(-f(x)_i) \end{eqnarray}$ unter den Nebenbedingungen : $\begin{eqnarray} -f(x)_i \geq 0 \end{eqnarray}$ $\begin{eqnarray} \lambda_i \geq 0 \end{eqnarray}$ $\begin{eqnarray} -f(x_i) \lambda_i = 0 \end{eqnarray*}$ Aber ob das überhaupt was ergibt weiss ich nicht, weshalb ich erstmal Fragen wollte, ob vielleicht jemand einen Methode kennt das ursprüngliche Problem gut zu lösen (maschinell) oder ob man eventuel zeigen kann das es so eine Lösung garnicht zu geben braucht (beides würde helfen).
13.04.2008, 22:09	Mazze	Auf diesen Beitrag antworten »
Ich habe mich jetzt das Wochende damit beschäftigt und habe einige Ergebnisse und Veränderungen. Vielleicht hilft dieses ja um jemandem durchblick zu verschaffen. Folgendes ist immer noch das Problem $\begin{eqnarray} -Bx = y \end{eqnarray}$ lösen, allerdings ist die Bedingung nun etwas schärfer. Ich brauche $\begin{eqnarray} \sum_{i=1}^{m}\exp(x_i) < 1 \end{eqnarray}$ B ist immernoch eine n x m Matrix mit n < m und den Zeilensummen = 1. Ich hatte übers Wochende den Optimierungsansatz weiter verfolgt aber es ist nicht wirklich etwas dabei rumgekommen. Zum Verständnis : Das gesammte LGS heisst $\begin{eqnarray} q\bold{1} - Bx_0 = y \end{eqnarray}$ dabei muss q > 0 sein. Nun, der Vektor x beschreibt Logarithmen von Wahrscheinlichkeiten. Es muss insgesammt gelten : $\begin{eqnarray} \sum_{i}(x_0)_i= 1 \end{eqnarray}$ Ist $\begin{eqnarray} \tilde{x} \end{eqnarray}$ eine Lösung von $\begin{eqnarray} -Bx = y \end{eqnarray}$ bekommt man $\begin{eqnarray} x_0 = \tilde{x} + q\bold{1} \end{eqnarray}$ da $\begin{eqnarray} B\bold{1} = \bold{1} \end{eqnarray}$ . Daraus kann man, wegen der Normalisierungseigenschaft q bestimmen. $\begin{eqnarray} \sum_{i}\exp\left(\tilde{x}_i + q\right) = 1 \Rightarrow q = -\log\left(\sum_{i}\exp(\tilde{x}_i)\right) \end{eqnarray}$ Und da q > 0 sein muss für mein Problem, muss $\begin{eqnarray} \sum_{i}\exp(\tilde{x}_i) < 1 \end{eqnarray}$ sein. Vielleicht hat ja jemand eine Idee. WIe auch immer , ich glaube fast das Problem ist in der Stochastic besser aufgehoben. Es geht zwar um die Lösbarkeit eines GLS unter Nebenbedinungen, aber das Problem selbst Stammt eher nicht aus der Algebra. edit : Wenn ich $\begin{eqnarray} B\bold{1} \end{eqnarray}$ schreibe heisst das in diesem Fall das B mit einem entsprechend dimensionierten 1 Vektor multipliziert wird.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »