Linearizing a program with multinomial logit in the objective

Question

I have a nonlinear problem as follows: \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}

Essentially, there are $K$ buckets with a desired value of $y_k$ for each. There are $N$ agents, each of which makes a choice based on a multinomial logit function.

I think I can get rid of the absolute value using the common trick: \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} but I don't know how to proceed from here. I have 2 questions.

1. Is it possible to linearize the fractional exp and reduce the problem to a linear program?
2. If not, how should I try to solve this problem? Is there a class of models that encompass this?

Answer 1

This is going to be a bit involved, so you might want to load up on caffeine now. The first step is a change of variables. Let $$z_{k}^{i}=\frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K}e^{x_{j}^{i}}}\ge0.$$The objective function reduces to $$\min \sum_{k=1}^{K}|y_{k}-\sum_{i=1}^{N}z_{k}^{i}|$$(which you can linearize) subject to the constraint $$\sum_{k=1}^{K}z_{k}^{i}=1\quad\forall i=1,\dots,N$$plus nonnegativity of the $z$ variables. This should be easy to solve for $z$.

Before attempting to recover $x$, we need to note a bit of invariance that works in our favor. Let $\lambda_i, i=1,\dots,N$ be arbitrary constants. Suppose that $x$ is a particular solution, and define $$\hat{x}_{k}^{i}=x_{k}^{i}+\lambda^{i}\quad\forall i,k.$$ Then $$\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.$$

Now let $z$ be an optimal solution to the transformed problem. For fixed $i$, $$\frac{z_{k}^{i}}{z_{j}^{i}}=\frac{e^{x_{k}^{i}}}{e^{x_{j}^{i}}}=e^{x_{k}^{i}-x_{j}^{i}}$$and so $$\log\left(\frac{z_{k}^{i}}{z_{j}^{i}}\right)=x_{k}^{i}-x_{j}^{i}.$$This will let us recover appropriate $x$ values. For each $i$, let $j_0=\textrm{argmin}_j \lbrace z^i_j \rbrace$. Arbitrarily set $x^i_{j_0}=0$, resulting in $$x^i_k=\log\left(\frac{z_{k}^{i}}{z_{j_0}^{i}}\right)\ge 0\quad \forall k\neq j_0.$$

Update: There is one serious flaw in this solution. If we constrain $z$ to be nonnegative, the LP solution may set $z^i_k=0$ for some index combinations, in which case the $x$ values cannot be recovered. (My recovery method would lead to division by 0, and if we go back to the definition of $z^i_k$ in terms of $x$, we see that no $z^i_k$ can actually be 0 (other than approximately, if some $x$ values are very large). So we need to set a nonzero lower bound for $z$.