Let $f(x)$ be a concave function in $\mathcal{C}^2$.
Consider a vector ${\bf y} = [y_1, \ldots, y_N]^\top \in Y = [0, a]^N$, where $a>0$ is a real number.
Finally, for a given $1 \leq k \leq N$, consider the following problem:
$$\left\{y_{k}^*,y_{k+1}^*, \ldots, y_N^*\right\} = \arg \min_{y_{k},y_{k+1}, \ldots, y_N} f\left(\sum_{i=1}^Ny_i\right)\\
\text{s.t.} \\y_i \in [0, a] ~~\forall 1 \leq i\leq N.
$$
In other words, I should find the values $\left\{y_{k}^*,y_{k+1}^*, \ldots, y_N^*\right\}$ such that:
$$f\left(\sum_{i=1}^{k-1} y_i + \sum_{i=k}^N y_i^*\right) \leq f\left(\sum_{i=1}^{k-1} y_i + \sum_{i=k}^N y_i\right)$$
for any vector ${\bf y}.$
I'm having difficulties since:
- We are minimizing a concave function (usually, it is easier to maximize them).
- The minimization is performed with respect to some independent variables.
My intuition suggests me that the minimum is attained when $$y_k^* = y_{k+1}^* = \ldots = y_N^* = 0.$$
Any suggestion about how to solve this kind of problem?
Best Answer
First of all, note that the actual values of the first $k$ and the last $N-k$ variables do not matter. What matters is their sum. So, the problem is equivalent to minimizing $f(x + y)$, subject to $x \in [0, ka]$, and $y \in [0, (N-k) a]$ over $y$.
We can make the change of variables $z = x + y$, or equivalently $y = z - x$, meaning that we need to solve $$ \min_{x \leq z \leq x + (N-k) a)} f(z). $$ The minimum of a concave function over a convex set is always attained at the extreme points (corners) of the set. The extreme points of the interval $[x, x+(N-k) a]$ are its endpoints, so the minimum is $\min\{ f(x), f(x+(N-k) a \}$.
Overall, $$ g(y_1, \dots, y_k) = \min_{y_{k+1}, \dots, y_N} f(\sum_{i=1}^k y_i + \sum_{i=k+1}^N y_i) = \min\left\{ f\left(\sum_{i=1}^k y_i\right), f\left(\sum_{i=1}^k y_i + (N-k) a\right) \right\} $$
Depending on which endpoint turns out to have smaller value, you have either $y_{k+1}^* = \dots = y_N^* = 0$ or any values which sum up to $(N-k) a$, such as $y_{k+1}^* = \dots = y_N^* = a$.