Explicit upper and lower bounds for a certain support function

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$$.

• Comment: Of course for such upper and lower bounds, one can simply take $f_t$. I am hoping for something more explicit. (I realize this is loosely formulated, so I leave it open to interpretation and will accept anything that is more explicit than the current variational representation.) Commented Nov 10, 2023 at 0:41
• did you try the KKT-conditions and duality? Duality at least gives an upper bound. Commented Nov 10, 2023 at 0:50
• I would also try solving the penalized unconstrained version i.e. $$max \sum a_i b_i+c\min(0,1-\sum b_i^2)+c\min(0,t-\sum \sqrt{b_i})$$ and then taking $c\to +\infty$. (see penalized version with inequality constraints in warin.ca/ressources/books/…). Commented Nov 10, 2023 at 1:00
• This doesn't really seem to help too much. The dual problem is somewhat challenging to handle as well. Commented Nov 10, 2023 at 1:03
• Are you looking for any particular bounds for some problem? Lower bounds are much easier because you just have to make choices that satisfy the constraints eg. setting $b_{1}=1$ and the rest $b_{i}=0$ and to get a lower bound by $a_{1}$. Commented Nov 10, 2023 at 3:06

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).$$