Let $\epsilon \in [0, 1]$, $b \in \mathbb R^k$, and $\Delta_k := \{x \in \mathbb R^k | x \ge 0,\; 1^Tx = 1\}$ be the unit $(k-1)$-dimensional simplex with $k\ge 2$.
Question
Find a closed-form solution to the problem $\underset{x \in \Delta_k | x_1 \ge \epsilon}{\text{argmax}}\;x^Tb$.
Solution to special cases
- $\epsilon = 0$: $x^*=\delta_{j^*}$ where $j \in \text{argmax}_{j=1}^k b_j$.
- $\epsilon=1$: $x^*=\delta_1$.
So here's an answer.
Consider the invertible change of variable $x = h(\bar{x}):=\epsilon\delta_1 + (1-\epsilon)\bar{x}$ which maps the simplex $\Delta_k$ unto itself, with inverse $\bar{x} = h^{-1}(x)=(1-\epsilon)^{-1}(x-\epsilon\delta_1)$.
It follows, that $$ \min_{x \in \Delta_k | x_1 \ge \epsilon}x^Tb=\min_{x \in \Delta_k | x-\alpha\delta_1 \ge 0}x^Tb=\min_{(1-\epsilon)^{-1}(x-\epsilon\delta_1)}x^Tb=\min_{\bar{x} \in \Delta_k}(\epsilon\delta_1+(1-\epsilon)\bar{x})^Tb, $$ which is attained by $\bar{x}^* \in \text{argmin}_{\bar{x} \in \Delta_k}\bar{x}^Tb=\text{ConvHull}(\text{argmin}_{j=1}^k b_j)$, yielding $ x^*=\epsilon\delta_1 + (1-\epsilon)\bar{x}^*$.