Explicit upper and lower bounds for a certain support function

Question

Let $a_1 \geq a_2 \geq \cdots \geq a_n \geq 0$ be a sequence of nonincreasing nonnegative real numbers. Define the set, for $t > 1$, $$ B_t = \Big\{b \in \mathbb{R}^n : b_i \geq 0, \sum_i b_i^2 \leq 1, \sum_i \sqrt{b_i} \leq t\Big\}. $$ I am interested in upper and lower bounds that differ only in constants (independent of $t, a$) for the following $$ f_t(a) = \max_{b \in B_t} \sum_{j=1}^n a_j b_j. $$ It can be seen as at the support function of the convex hull of $B_t$ for such nonincreasing nonnegative $a$.

Answer 1

Let $$g_t(a) = \max_{1\le k\le n}\ \min\left(\sqrt{\sum_{i=1}^k a_i^2},\ t^2\frac{\sum_{i=1}^k a_i^2}{\left(\sum_{i=1}^k\sqrt{a_i}\right)^2}\right).$$ Then $g_t(a) \le f_t(a) \le 3g_t(a)$. The proof follows.

Consider some maximizer $b$. It has a prefix of $k \ge 1$ positive elements, potentially followed by some zeros. This is true because otherwise another permutation of $b$ achieves larger objective value. Hence, only the first $k$ elements of $a$ and $b$ matter.

The KKT conditions for $b$ being a maximizer say there exist some $\lambda,\mu \ge 0$ such that for $1 \le i \le k$ we have $$a_i - 2\lambda b_i - \frac{\mu}{2\sqrt{b_i}} = 0.$$

Note that we don't need Lagrange multipliers for the positivity constraints since we assume $b_i \ne 0$. Now, since $\mu \ge 0$ and $b_i > 0$, the KKT condition above implies $a_i \ge 2\lambda b_i$.

Next, consider the second order optimality conditions (differentiate twice to check that the solution is concave around the maximizer $b$) $$-2\lambda + \frac{\mu}{4b_i^{3/2}} \le 0.$$ This can be rewritten as $\frac{\mu}{2\sqrt{b_i}} \le 4\lambda b_i$. Inserting it into the KKT conditions yields $a_i \le 6\lambda b_i$. Hence $\lambda$ must be positive and we have established $\frac{a_i}{6\lambda} \le b_i \le \frac{a_i}{2\lambda}$.

By inserting $\frac{a_i}{6\lambda} \le b_i$ into the bounds $\sum_{i=1}^k b_i^2 \le 1$ and $\sum_{i=1}^k \sqrt{b_i} \le t$, we get the bound $$\lambda \ge \frac{1}{6}\max\left(\sqrt{\sum_{i=1}^k a_i^2},\ \frac{1}{t^2}\left(\sum_{i=1}^k\sqrt{a_i}\right)^2\right).$$ Now combining this with $b_i \le \frac{a_i}{2\lambda}$ gives $$\sum_{i=1}^k a_i b_i \le 3\min\left(\sqrt{\sum_{i=1}^k a_i^2},\ t^2\frac{\sum_{i=1}^k a_i^2}{\left(\sum_{i=1}^k\sqrt{a_i}\right)^2}\right).$$

By taking the maximum over $1 \le k \le n$, we establish the upper bound.

The lower bound is achieved by selecting $\lambda$ and $b_i$ as their lower bounds as derived above. Specifically, the lower bound is achieved for some $1 \le k \le n$ by selecting $b_i = \nu a_i$ for $1 \le i \le k$ and $b_i = 0$ for $i > k$, where $$\nu = \min\left(\left(\sum_{i=1}^k a_i^2\right)^{-1/2},\ \frac{t^2}{\left(\sum_{i=1}^k\sqrt{a_i}\right)^2}\right).$$