Linearizzare un programma con logit multinomiale nell'obiettivo

Question

Ho un problema non lineare come segue: \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}

In sostanza, ci sono $K$ secchi con un valore desiderato di $y_k$per ciascuno. Ci sono$N$ agenti, ciascuno dei quali effettua una scelta basata su una funzione logit multinomiale.

Penso di poter sbarazzarmi del valore assoluto usando il trucco comune: \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}ma non so come procedere da qui. Ho 2 domande.

1. È possibile linearizzare l'esperimento frazionario e ridurre il problema a un programma lineare?
2. In caso contrario, come dovrei provare a risolvere questo problema? Esiste una classe di modelli che lo racchiuda?

Answer 1

Questo sarà un po 'complicato, quindi potresti voler caricare la caffeina ora. Il primo passo è un cambio di variabili. Permettere$$z_{k}^{i}=\frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K}e^{x_{j}^{i}}}\ge0.$$La funzione obiettivo si riduce a $$\min \sum_{k=1}^{K}|y_{k}-\sum_{i=1}^{N}z_{k}^{i}|$$(che puoi linearizzare) soggetto al vincolo $$\sum_{k=1}^{K}z_{k}^{i}=1\quad\forall i=1,\dots,N$$più la non negatività di $z$variabili. Questo dovrebbe essere facile da risolvere$z$.

Prima di tentare il recupero $x$, dobbiamo notare un po 'di invarianza che funziona a nostro favore. Permettere$\lambda_i, i=1,\dots,N$essere costanti arbitrarie. Supporre che$x$ è una soluzione particolare e definisci $$\hat{x}_{k}^{i}=x_{k}^{i}+\lambda^{i}\quad\forall i,k.$$ Poi $$\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.$$

Adesso molla $z$essere una soluzione ottimale al problema trasformato. Per fisso$i$, $$\frac{z_{k}^{i}}{z_{j}^{i}}=\frac{e^{x_{k}^{i}}}{e^{x_{j}^{i}}}=e^{x_{k}^{i}-x_{j}^{i}}$$e così $$\log\left(\frac{z_{k}^{i}}{z_{j}^{i}}\right)=x_{k}^{i}-x_{j}^{i}.$$Questo ci permetterà di recuperare in modo appropriato $x$valori. Per ciascuno$i$, permettere $j_0=\textrm{argmin}_j \lbrace z^i_j \rbrace$. Impostato arbitrariamente$x^i_{j_0}=0$, con il risultato di $$x^i_k=\log\left(\frac{z_{k}^{i}}{z_{j_0}^{i}}\right)\ge 0\quad \forall k\neq j_0.$$

Aggiornamento : c'è un grave difetto in questa soluzione. Se vincoliamo$z$ per essere non negativo, la soluzione LP può essere impostata $z^i_k=0$ per alcune combinazioni di indici, nel qual caso il $x$i valori non possono essere recuperati. (Il mio metodo di recupero porterebbe alla divisione per 0 e se torniamo alla definizione di$z^i_k$ in termini di $x$, vediamo che no $z^i_k$ può effettivamente essere 0 (diverso da approssimativamente, se alcuni $x$i valori sono molto grandi). Quindi dobbiamo impostare un limite inferiore diverso da zero per$z$.