Find the minimum $s > 0$ such that this linear function is non-negative

20 Views Asked by At

Let $x \in [0, 1]^N$, and $y \in [0, 1]$. Consider also $a >0$ and $b > 0$.

Define the following linear function:

$$f_s(x,y) = \sum_{i=1}^N[(a-b)x_i-a] - s[(a-b)y - a],$$

for $s>0$.

What is the minimum $s$ such that $f_s(x,y)$ is non-negative for all $x \in [0, 1]^N$ and for all $y \in [0,1]$?

My attempt

It is easy to show that:

$$\min\{-a, -b\} \leq (a-b)x_i-a \leq \max\{-a, -b\},$$

or equivalently

$$-\max\{a, b\} \leq (a-b)x_i-a \leq -\min\{a, b\}.$$

Of course, the same holds replacing $x_i$ with $y$.

Then:

$$\begin{align}f_s(x,y) & \geq \sum_{i=1}^N(-\max\{a, b\}) - s(-\min\{a, b\}) = \\ & = -N\max\{a, b\} + s \min\{a, b\}. \end{align} $$

In order to guarantee that $f_s(x,y) \geq 0$, then, I conclude that $$s \geq N\frac{\max\{a, b\}}{\min\{a, b\}}.$$

This bound works. Anyway, from numerical simulation I observed that there can be a better lower bound (I tried generating random numbers for $10^6$ times).

Is there another way to find the minimum $s$ possible?

Remark

The bound I found is the best when $a=b$.