2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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.) $\endgroup$
    – Drew Brady
    Commented Nov 10, 2023 at 0:41
  • $\begingroup$ did you try the KKT-conditions and duality? Duality at least gives an upper bound. $\endgroup$ Commented Nov 10, 2023 at 0:50
  • $\begingroup$ 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/…). $\endgroup$ Commented Nov 10, 2023 at 1:00
  • $\begingroup$ This doesn't really seem to help too much. The dual problem is somewhat challenging to handle as well. $\endgroup$
    – Drew Brady
    Commented Nov 10, 2023 at 1:03
  • $\begingroup$ 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}$. $\endgroup$ Commented Nov 10, 2023 at 3:06

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.