Is minimizing number of $\{{i : x_i \ne 0}\}$ subject to $Ax=b$ a convex problem? Why is it computationally hard?
What is polar cone of $\{x \in \mathbb{R}^2:0\le x_1 \le x_2\}$?
Are $min\{0,x-1,x^3\}$ and $min\{||x-y||:y_1\le...\le y_n\}$ concave or convex sets?
My guess is that 1 is a convex problem. Seems like 2 dual cone is $0\ge x_1 \ge x_2$. For 3, the first is concave because $g$ is a piecewise function of three concave functions (on appropriate domain) but is that enough of a justification? Thanks in advance. Any help please?
(1) : This problem isn't convex because the function you're minimizing is discontinuous.
As for its hardness, you can reduce any number of graph problems to (1) -- I would bet that you could encode an instance of Vertex Cover or some other NP-hard problem as (1), which would make (1) NP-hard.
(2) : The region described is bounded by two lines ($x_1 \geq 0$ and $x_2\geq x_1$). There's a diagram here that should help you figure out the rest.
(3) : You're close on the first. You need to explain why $x^3$ is concave for this set. As for the second, the region described by the $y$'s is convex (why?). Distance is also convex. You should be able to work from there.