Linearisieren eines Programms mit multinomialem Logit im Ziel

Question

Ich habe ein nichtlineares Problem wie folgt: \begin{align}\min&\quad\sum_{k=1}^{K}\left|y_k - \sum_{i=1}^{N} \frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K} e^{x^{i}_{j}}}\right|\\\text{s.t.}&\quad x^i_{j} \ge 0\end{align}

Im Wesentlichen gibt es $K$ Eimer mit einem gewünschten Wert von $y_k$für jede. Es gibt$N$ Agenten, von denen jeder eine Auswahl basierend auf einer multinomialen Protokollierungsfunktion trifft.

Ich denke, ich kann den absoluten Wert mit dem üblichen Trick loswerden: \begin{align}\min&\quad \sum_{k=1}^{K}t_k\\\text{s.t.}&\quad t_k \ge y_k - \sum_{i=1}^{N} \frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K} e^{x^{i}_{j}}}\\&\quad t_k\ge-\left(y_k - \sum_{i=1}^{N} \frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K} e^{x^{i}_{j}}}\right)\end{align}aber ich weiß nicht, wie ich von hier aus vorgehen soll. Ich habe 2 Fragen.

1. Ist es möglich, die gebrochene exp zu linearisieren und das Problem auf ein lineares Programm zu reduzieren?
2. Wenn nicht, wie soll ich versuchen, dieses Problem zu lösen? Gibt es eine Klasse von Modellen, die dies umfassen?

Answer 1

Dies wird ein bisschen kompliziert sein, also möchten Sie vielleicht jetzt Koffein aufladen. Der erste Schritt ist eine Änderung der Variablen. Lassen$$z_{k}^{i}=\frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K}e^{x_{j}^{i}}}\ge0.$$Die Zielfunktion reduziert sich auf $$\min \sum_{k=1}^{K}|y_{k}-\sum_{i=1}^{N}z_{k}^{i}|$$(die Sie linearisieren können) vorbehaltlich der Einschränkung $$\sum_{k=1}^{K}z_{k}^{i}=1\quad\forall i=1,\dots,N$$plus Nichtnegativität der $z$Variablen. Dies sollte leicht zu lösen sein$z$.

Vor dem Versuch, sich zu erholen $x$müssen wir ein bisschen Invarianz beachten, die zu unseren Gunsten wirkt. Lassen$\lambda_i, i=1,\dots,N$beliebige Konstanten sein. Nehme an, dass$x$ ist eine bestimmte Lösung und definieren $$\hat{x}_{k}^{i}=x_{k}^{i}+\lambda^{i}\quad\forall i,k.$$ Dann $$\hat{z}_{k}^{i}=\frac{e^{\lambda^{i}}e^{x_{k}^{i}}}{\sum_{j=1}^{K}e^{\lambda^{i}}e^{x_{j}^{i}}}=z_{k}^{i}\quad\forall i,k.$$

Nun lass $z$eine optimale Lösung für das transformierte Problem sein. Für fest$i$, $$\frac{z_{k}^{i}}{z_{j}^{i}}=\frac{e^{x_{k}^{i}}}{e^{x_{j}^{i}}}=e^{x_{k}^{i}-x_{j}^{i}}$$und so $$\log\left(\frac{z_{k}^{i}}{z_{j}^{i}}\right)=x_{k}^{i}-x_{j}^{i}.$$Dadurch können wir uns angemessen erholen $x$Werte. Für jede$i$, Lassen $j_0=\textrm{argmin}_j \lbrace z^i_j \rbrace$. Beliebig eingestellt$x^i_{j_0}=0$, ergebend $$x^i_k=\log\left(\frac{z_{k}^{i}}{z_{j_0}^{i}}\right)\ge 0\quad \forall k\neq j_0.$$

Update : Diese Lösung weist einen schwerwiegenden Fehler auf. Wenn wir uns einschränken$z$ Um nicht negativ zu sein, kann die LP-Lösung eingestellt werden $z^i_k=0$ für einige Indexkombinationen, in welchem ​​Fall die $x$Werte können nicht wiederhergestellt werden. (Meine Wiederherstellungsmethode würde zu einer Division durch 0 führen, und wenn wir zur Definition von zurückkehren$z^i_k$ bezüglich $x$wir sehen das nein $z^i_k$ kann tatsächlich 0 sein (außer ungefähr, wenn einige $x$Werte sind sehr groß). Wir müssen also eine Untergrenze ungleich Null für festlegen$z$.