Linealizar un programa con logit multinomial en el objetivo

Question

Tengo un problema no lineal de la siguiente manera: \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}

Esencialmente, hay $K$ cubos con un valor deseado de $y_k$para cada. Existen$N$ agentes, cada uno de los cuales hace una elección basada en una función logit multinomial.

Creo que puedo deshacerme del valor absoluto usando el truco común: \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}pero no sé cómo proceder desde aquí. Tengo 2 preguntas.

1. ¿Es posible linealizar la exp fraccional y reducir el problema a un programa lineal?
2. Si no es así, ¿cómo debería intentar solucionar este problema? ¿Existe una clase de modelos que abarquen esto?

Answer 1

Esto va a ser un poco complicado, por lo que es posible que desee cargarse de cafeína ahora. El primer paso es un cambio de variables. Dejar$$z_{k}^{i}=\frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K}e^{x_{j}^{i}}}\ge0.$$La función objetivo se reduce a $$\min \sum_{k=1}^{K}|y_{k}-\sum_{i=1}^{N}z_{k}^{i}|$$(que puede linealizar) sujeto a la restricción $$\sum_{k=1}^{K}z_{k}^{i}=1\quad\forall i=1,\dots,N$$más la no negatividad del $z$variables. Esto debería ser fácil de resolver$z$.

Antes de intentar recuperarse $x$, debemos notar un poco de invariancia que funciona a nuestro favor. Dejar$\lambda_i, i=1,\dots,N$ser constantes arbitrarias. Suponer que$x$ es una solución particular y definir $$\hat{x}_{k}^{i}=x_{k}^{i}+\lambda^{i}\quad\forall i,k.$$ Luego $$\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.$$

Ahora deja $z$ser una solución óptima al problema transformado. Para fijo$i$, $$\frac{z_{k}^{i}}{z_{j}^{i}}=\frac{e^{x_{k}^{i}}}{e^{x_{j}^{i}}}=e^{x_{k}^{i}-x_{j}^{i}}$$y entonces $$\log\left(\frac{z_{k}^{i}}{z_{j}^{i}}\right)=x_{k}^{i}-x_{j}^{i}.$$Esto nos permitirá recuperarnos adecuadamente. $x$valores. Para cada$i$, dejar $j_0=\textrm{argmin}_j \lbrace z^i_j \rbrace$. Establecido arbitrariamente$x^i_{j_0}=0$, Resultando en $$x^i_k=\log\left(\frac{z_{k}^{i}}{z_{j_0}^{i}}\right)\ge 0\quad \forall k\neq j_0.$$

Actualización : hay un defecto grave en esta solución. Si restringimos$z$ para no ser negativo, la solución LP puede $z^i_k=0$ para algunas combinaciones de índices, en cuyo caso el $x$los valores no se pueden recuperar. (Mi método de recuperación conduciría a la división por 0, y si volvemos a la definición de$z^i_k$ en términos de $x$, vemos que no $z^i_k$ puede ser 0 (excepto aproximadamente, si algunos $x$los valores son muy grandes). Así que necesitamos establecer un límite inferior distinto de cero para$z$.