I am tackling the following optimization problem where ideally I would like to minimizemaximize (analytically, over $\alpha$) these kindssorts of quantities, where $K$ is some 'large' constant (e.g. $K > 100$)$n \ll d$ and $d \in \mathbb{N}, \epsilon \in \mathbb{R}^{+*}$, and in practice a non trivial upper bound on the objective would be enough.
$$\sum_{i=1}^{d} \alpha_i e^{-K(\alpha_i - 1/d)}$$$$\Gamma(d, n, \alpha) = \sum_{i=1}^{d} \alpha_i^2 e^{- n \alpha_i}$$
Subject to the following constraints,
$$\alpha \in \Delta^{d-1}$$$$\alpha \in \Delta^{d-1} \text{ (simplex)}$$ $$||\alpha - (1/d)||_1 \geq \epsilon$$
What sortsI have a 'hunch' candidate minimizer, an alternating $\alpha_i = (1\pm \epsilon)/d$.
Here is an attempt, but there are a few issues, as I am not sure how to deal with the non-linear constraint, and I cannot rule out some of techniquesthe cases, where some of the $\alpha_i$ would be available to melarger than ?$2/n$ (I think I would alsoshould be fairly happy withable to do that as I am only interested in the limit case $n/d \rightarrow 0$).
Denote $f(\alpha_i)= \alpha_i^2 e^{-n \alpha_i}$. We start by developing a non-trivialconcave upper bound for $f(\alpha_i)$, defined by a second degree polynomial $Q(\alpha_i)$ on $[0, 2/n]$, and a constant piece on $[2/n, 1]$. We wish $Q$ to satisfy the minimumfollowing equalities,
\begin{equation} \begin{split} Q(0) &= 0 \\ Q(2/n) &= 4/n^2 \\ Q'(2/n) &= 0 \end{split} \end{equation}
Which yields the following $g$:
\begin{equation} \begin{split} g(\alpha_i) = \begin{cases} \alpha_i(4/n - \alpha_i) & \text{if } \alpha_i \in [0, 2/n] \\ 4/n^2 & \text{otherwise} \end{cases} \end{split} \end{equation}
It follows that
\begin{equation} \begin{split} \Gamma(d, n, \alpha) \leq \sum_{i=1}^{d} g(\alpha_i) \end{split} \end{equation}
Using Lagrange multipliers,
\begin{equation} \begin{split} \mathcal{L}(d, n, \alpha, \lambda, \mu) = \sum_{i=1}^{d} g(\alpha_i) - \lambda \left( \sum_{i=1}^{d} \alpha_i - 1 \right) - \mu \left( \sum_{i=1}^{d} |\alpha_i - 1/d| - \epsilon \right) \end{split} \end{equation}
$\forall k \in [d]$,
\begin{equation} \begin{split} \frac{\partial \mathcal{L}}{\partial \alpha_k} &= g'(\alpha_k) - \lambda = \begin{cases} (4/n - 2 \alpha_k) - \lambda - \mu sgn(\alpha_k - 1/d) & \text{if } \alpha_k \in [0, 2/n] \\ - \lambda - \mu sgn(\alpha_k - 1/d) & \text{otherwise} \end{cases} \\ \frac{\partial^2 \mathcal{L}}{\partial \alpha_k^2} &= g''(\alpha_k) = \begin{cases} -2 & \text{if } \alpha_k \in [0, 2/n] \\ 0 & \text{otherwise} \end{cases} \\ \\ \end{split} \end{equation}
We wish to solve $\forall k \in [d], \frac{\partial \mathcal{L}}{\partial \alpha_k} = 0$.
Take $\alpha_k < 1/d$, then since $d \gg n$, $\alpha_k < 1/n$, $sgn(\alpha_i - 1/d) = -1$, and
\begin{equation} \begin{split} \alpha_k = \frac{2}{n} - \frac{\lambda - \mu}{2} \end{split} \end{equation}
meaning that all $\alpha_k$ strictly smaller than $1/d$ are equal: $\exists \alpha^-, \forall k \in [d], \alpha_k < 1/d \Rightarrow \alpha_k = \alpha^-$.
Take now $\alpha_k > 1/d$, if $\lambda + \mu = 0$, then all $\alpha_k$ are large: $\alpha_k > 2/n$ (but not necessarily the same...). If $\lambda + \mu \neq 0$, then the solution to $\frac{\partial \mathcal{L}}{\partial \alpha_k} = 0$ must be for $\alpha_k \in [0, 2/n]$ on which $\frac{\partial \mathcal{L}}{\partial \alpha_k}$ is strictly decreasing. Hence $\alpha_k = \alpha^{+} < 2/n$.
I am not able to rule out the possibility that some of the $\alpha_i = 1/d$.
Suppose I managed to rule out unwanted cases and have a 'hunch' candidate minimizer, wouldtwo possible values for the problem of proving$\alpha_i$, then it becomes easy
Denote by $$I^+ = \{ k \in [d], \alpha_k > 1/d \}, I^- = \{ k \in [d], \alpha_k < 1/d \}$$ $$d^+ = |I^+|, d^- = |I^-|$$
It immediately follows that \begin{equation} \label{eq:sum} \begin{split} d &= d^+ + d^- \end{split} \end{equation}
\begin{equation} \label{eq:simplex} \begin{split} d^-\alpha^- + d^+\alpha^+ = 1 \end{split} \end{equation}
Setting $||\alpha - (1/d)||_1 = \epsilon$, also
\begin{equation} \label{eq:precision} \begin{split} d^+\alpha^+ - d^-\alpha^- + \frac{1}{d}(d^- - d^+) = \epsilon \end{split} \end{equation}
and from the above, it is indeed a minimizerfollows that
\begin{equation} \begin{split} \label{eq:weights} \alpha^+ &= \frac{1}{d} + \frac{\epsilon}{2d^+} \\ \alpha^- &= \frac{1}{d} - \frac{\epsilon}{2d^-} \end{split} \end{equation}
The objective function can then be any simplerrewritten as a function of ? Are there some techniques at my disposal for doing so$d^+/d$ whose optimal value ? My guess is$1/2$ can be found, and an alternating $\alpha_i = (1\pm \epsilon)/d$upper bound can then be obtained by plugging in.