1

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.

Television
  • 560
  • Any specific requirements? Throwing a standard nonlinear solver at it works well. A conjecture (completely unsubstantiated) is that the solution is symmetric, and then all you have to do is to solve the scalar function $x_i^2e^{-x_i)=C/n$ (which has up to two solutions, but I guess only one is interesting) – Johan Löfberg May 24 '18 at 10:21
  • 1
    On closer inspection, a local nonlinear solver easily picks the wrong solution (fooled by the multi-modality of $x^2exp(-x)$), leading to a very sub-optimal solution. – Johan Löfberg May 24 '18 at 10:34
  • 1
    Something to exploit is perhaps the fact that the equation $x_i^2e^{-x_i}=C/n$ when assuming symmetry, is the Lambert W function in disguise (take square-root of both sides and then define new variable $y_i = -x_i/2$.) – Johan Löfberg May 24 '18 at 10:59
  • @JohanLöfberg That is an interesting observation. But I am not quite sure what to make of it. Any thoughts on how this could be useful? Thanks! – Television May 24 '18 at 14:21

1 Answers1

2

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$

madnessweasley
  • 1,723
  • 1
    So can I broadly generalize what you have said here: For problems with symmetric constraints and a symmetric objective, an optimal (both minimization and maximization) solution must be at $(x^,\dots,x^,0,\dots,0)$ and the question would then be to show which of these takes the optimal value? – Television May 25 '18 at 07:02
  • 1
    @NivedRajaraman I don't know. I will have to think about it. Suppose you have a symmetric objective function ($f$), symmetric equality constraints ($h_k$), and nonnegativity constraints $x \geq 0$ (the only inequality constraints in the formulation). Assume that the problem is feasible. Then we can certainly say that all candidates for optimal solutions (min. and max.) are points such that $(\nabla f(x^))_i + \sum_k \lambda_k (\nabla h_k(x^))_i = 0$,$x^_i \geq 0$, $i \in \mathcal{I}$, and $x^_j = 0$,$j \in {1,\cdots,n}\backslash \mathcal{I}$ for different choices of $\mathcal{I}$. – madnessweasley May 25 '18 at 15:12