Functions that are easy to compare to a norm

Question

Let $X$ be a subset of $\mathbb{R}^d$, let $\|\cdot \|_p$ be a norm with $1\leq p\leq\infty$, and let $f:\mathbb{R}^d\to\mathbb{R}$ be a function. I'm trying to find examples of $X$, $p$, and $f$ for which it is computationally tractable to minimize the function $$\|x\|_p-f(x)$$ over $x\in X$, and in particular, to test if there exists a point where the above quantity is negative. One example would be the case where $X$ is convex and $f$ is concave, in which case the above expression is convex and therefore can be minimized in a tractable fashion. If $f$ is convex instead, then we have a special case of the "difference of convex functions", which (as far as I know) is not generally known to be tractable. Are there any other special cases that might work as well?

Answer 1

If $f$ is homogeneous, you can just try to minimize it on the unit ball (which is a Lagrange multiplier problem, which does not mean it's easy), and see if any of your critical values are smaller than $1\dots$