# Maximizing sum of homogeneous functions of order one over a polytope

Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a homogeneous function of order one for $i=1,\dots,n$. Further suppose that for any $y\in \mathbb{R}^n$ where the first entry is zero (i.e., $y(1)=0$), $f_i(y)=0$ for all $i$.

Consider the following optimization problem: \begin{aligned} \max_{\{x_i\in \mathbb{R}^n\}} \quad & \sum_i f_i(x_i) \\ s.t. \quad & \sum_i x_i =b \\ & x_i \geq 0 \end{aligned}

Is it the case that at the optimal solution we generically have $x_i=0$ for all but one $i$? Observe that this trivially holds if $f_i$ are linear.

• $x_i$ are vectors, see the domain of $f_i$. By increasing, I mean increasing in each coordinate. Question updated to clarify these points.
– Ozzy
Commented Sep 26, 2017 at 16:23
• Correct -- question updated accordingly.
– Ozzy
Commented Sep 26, 2017 at 16:41
• What about the case $f_i(z)= z^i$ (the $i$-th coordinate of $z$) for all $i$. Then the optimal solution is $(b^1e_1,\ldots,b^ne_n)$ where $b^i$ are the coordinates of $b$ and $e_1,\ldots,e_n$ the canonical basis.
– Surb
Commented Sep 26, 2017 at 16:55
• in the linear case, it is true there may exist a solution where all $x_i$ are positive. But this is not true generically. Your second point is correct. Which made me realize that some of the additional structure I have in the problem is necessary for the question to be interesting. I'm updating the question accordingly.
– Ozzy
Commented Sep 26, 2017 at 17:05
• I'm not sure what you exactly mean by generically. Regarding the additional assumption, it seems still possible to build linear cases where for every $i$, $f_i(y)$ does not depend on $y(1)$.
– Surb
Commented Sep 26, 2017 at 17:53