Timeline for Hardness of concave minimization problem
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2020 at 6:14 | comment | added | gerw | If the feasible region is bounded, my conclusion fails. The main argument was that we can look at rays starting in $0$. | |
| Apr 7, 2020 at 22:44 | comment | added | Francis | What if the feasible region of $x$ is bounded? Specifically, $x \in X \subseteq \mathbb{R}^d$ and $\|X\|_2 \leq \gamma$, does your conclusion still hold? As far as I can understand, the contradiction doesn't exist because 1 is only the minimizer of $\phi$ within the bounded region $X$, but it's not the minimizer for the whole infty range. | |
| Apr 7, 2020 at 17:40 | comment | added | gerw | Your example does not have a minimizer. If the problem has a minimizer, then $0$ is a minimizer. Otherwise, the infimal value is $-\infty$. | |
| Apr 7, 2020 at 16:30 | comment | added | Francis | The proof makes sense, but the conclusion seems kind of strange to me. Does this mean $\underset{x}{\min} c(x) - k\cdot x$ = 0? However, consider a simple example when $c(x) = \sqrt{x}$ and $k = 1$. Apparently, $\underset{x}{\min} \sqrt{x} - x = - \infty$ instead of 0? So where goes wrong in this problem. | |
| Apr 1, 2020 at 4:34 | history | answered | gerw | CC BY-SA 4.0 |