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{equation} \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} \end{equation}

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.

  • 1
    $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 Sep 26 '17 at 16:23
  • Correct -- question updated accordingly. – Ozzy Sep 26 '17 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 Sep 26 '17 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 Sep 26 '17 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 Sep 26 '17 at 17:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.