1
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ $x_i$ are vectors, see the domain of $f_i$. By increasing, I mean increasing in each coordinate. Question updated to clarify these points. $\endgroup$
    – Ozzy
    Commented Sep 26, 2017 at 16:23
  • $\begingroup$ Correct -- question updated accordingly. $\endgroup$
    – Ozzy
    Commented Sep 26, 2017 at 16:41
  • $\begingroup$ 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. $\endgroup$
    – Surb
    Commented Sep 26, 2017 at 16:55
  • $\begingroup$ 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. $\endgroup$
    – Ozzy
    Commented Sep 26, 2017 at 17:05
  • $\begingroup$ 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)$. $\endgroup$
    – Surb
    Commented Sep 26, 2017 at 17:53

0

Reset to default

You must log in to answer this question.