Optimal value of this non-convex optimization problem

Question

Are there any optimization techniques for problems such as: \begin{alignat*}{2} &\text{Find: } &&\min \sum_i^n x_i e^{-x_i} \\ &\text{Subject to: } &&\sum_i^n x_i^2 e^{-x_i} = C\\ & &&x_i \ge 0,\ \forall i \end{alignat*} Would appreciate any helpful pointers. A tight lower bound would also be of interest.

Answer 1

First, let us exclude the cases when the problem is infeasible (i.e., $C < 0$ or $C > 4n\exp(-2)$), or trivial (i.e., $C = 0$ or $C = 4n\exp(-2)$). We are left with the cases where $0 < C < 4n\exp(-2)$.

If $x_i > 0$ at the optimal solution for each $i$, then the Lagrange Multiplier Theorem guarantees that all of the $x_i$ will be equal at the solution (which is obtained by solving $x^2_i \exp(-x_i) = \frac{C}{n}$).

Now suppose exactly $m$ of the $x_i$ are (strictly) positive at the solution $(\bar{x}_1,\cdots,\bar{x}_n)$ for some $1 \leq m < n$. Without loss of generality, let the nonzero components be $\bar{x}_1,\cdots,\bar{x}_m$ (i.e., $\bar{x}_{m+1} = \cdots = \bar{x}_{n} = 0$). Once again, by the Lagrange Multiplier Theorem, we will have $\bar{x}_1 = \cdots = \bar{x}_m$ with $\bar{x}_1$ corresponding to the largest solution of the equation $\bar{x}^2 \exp(-\bar{x}) = \frac{C}{m}$. Let $(x^*_1,\cdots,x^*_n)$ denote the solution where all of the $x_i$ are positive and equal, i.e. $x^*_i$ corresponds to the largest solution of the equation $\left(x^*\right)^2 \exp(-x^*) = \frac{C}{n}$.

The objective value for $(\bar{x}_1,\cdots,\bar{x}_n)$ is given by $m\bar{x}_1\exp(-\bar{x}_1) = \frac{C}{\bar{x}_1}$. The objective value for $(x^*_1,\cdots,x^*_n)$ is given by $nx^*_1\exp(-x^*_1) = \frac{C}{x^*_1}$. Since the largest admissible solution of the equation $\left(x^*\right)^2 \exp(-x^*) = \frac{C}{n}$ is greater than or equal to the largest admissible solution to the equation $\bar{x}^2 \exp(-\bar{x}) = \frac{C}{m}$, we have that the objective value of $(x^*_1,\cdots,x^*_n)$ is at least as good as that of $(\bar{x}_1,\cdots,\bar{x}_n)$.

Therefore, $(x^*_1,\cdots,x^*_n)$ is the optimal solution. $\square$