Given that $x^*$ are optimal solutions to $$\min_{x \in \mathbb{R}^n} f(x) + \lambda\|x\|_0$$ for $\lambda > 0$ and that $$f^* = \min_{x \in \mathbb{R}^n} f$$ is finite and $\phi(\lambda) = min\{\|x^*\|_0 \ \text{ for an optimal solution } \|x^*\|_0 \}$, show that $\phi(\lambda)$ is a non-increasing function.
I've already shown that for $\lambda > f(0) - f^*$, $x^*=0$ is the unique minimizer and thus $\phi(\lambda) = 0$ is non-increasing for $\lambda > f(0) - f^*$. But I'm not sure how to show that for $0 < \lambda \leq f(0) - f^*$. My gut feeling is to use contradiction by assuming $0 < \lambda_2 < \lambda_1 \leq f(0) - f^*$, assume $\phi(\lambda_1) > \phi(\lambda_2)$ and then arrive at a contradiction, but so far hasn't worked. Any hints or suggestions will be much appreciated!
There is a general approach that works for any non-negative penalty, not just $\|\cdot\|_0$
Fix any $ \lambda\geq 0$ and any $\epsilon>0$. Let $x^*_{\lambda}$ and $x^*_{\lambda+\epsilon}$ be minimizers for the problem with $\lambda$ and $\lambda+\epsilon$ respectively. Then: $$ \left(f(x^*_{\lambda})+\lambda\|x^*_{\lambda}\|_0\right)+\epsilon\|x^*_{\lambda+\epsilon}\|_0 \leq \left(f(x^*_{\lambda+\epsilon})+\lambda\|x^*_{\lambda+\epsilon}\|_0\right)+\epsilon\|x^*_{\lambda+\epsilon}\|_0 $$ $$ =f(x^*_{\lambda+\epsilon})+(\lambda+\epsilon)\|x^*_{\lambda+\epsilon}\|_0 \leq f(x^*_\lambda)+(\lambda+\epsilon)\|x^*_\lambda\|_0 $$ Rearranging, we find $\|x^*_{\lambda+\epsilon}\|_0\leq \|x^*_\lambda\|_0$. Hence, $\phi$ is non-increasing.