7
$\begingroup$

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?
$\endgroup$

1 Answer 1

7
$\begingroup$

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$.

$\endgroup$
8
  • $\begingroup$ There's a bug in my solution, noted above in the update. We need to set an arbitrary but strictly positive lower bound on $z$. $\endgroup$
    – prubin
    Oct 16, 2020 at 3:21
  • $\begingroup$ Thank you for your detailed solution and the follow up discussion! So, it just suffices to set $z_i >0 $? $\endgroup$
    – Alex
    Oct 16, 2020 at 19:40
  • 1
    $\begingroup$ Your solver will not let you use a weak inequality as a bound, so rather than $z \gt 0$ you will need $z \ge \epsilon$ for some strictly positive $\epsilon$. $\endgroup$
    – prubin
    Oct 16, 2020 at 20:23
  • 1
    $\begingroup$ I just did a rather interesting numerical experiment (with fabricated data, $N=10$, $K=100$, $y_k$ between 0 and 1), using the transformed LP described above and a genetic algorithm. The GA was able to match the LP solution, which is not terribly surprising. What caught my eye was that the LP solution was much sparser than the GA solution. The LP solution had 34 nonzero $x$ values (out of 1,000) while the GA had all 1,000 $x$ values nonzero (ranging from around 1.2 to around 99). So whether the LP is a good choice for you may depend on how you feel about a sparse solution. $\endgroup$
    – prubin
    Oct 16, 2020 at 20:32
  • $\begingroup$ I'm new to the optimization world, so I really appreciate all these insights. May I ask, why you considered GA? in my problem N=100 and K=5000, so motivation for LP was to make it run faster. My understanding is that GA is quite slow $\endgroup$
    – Alex
    Oct 16, 2020 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.