# Convex programming without a lower bound on the feasible region size

I need to solve a convex minimization problem of the form: minimize $$f(x)$$ such that $$g_i(x)\leq 0$$, where the $$g_i$$ are convex functions given by a value oracle.

As far as I know, to use the ellipsoid method, I need an initial ball of size $$R$$ that contains the feasible region, and a positive number $$r such that, if the feasible region is not empty, then it contains a ball of radius $$r$$; then, the run-time complexity of the method is in $$O(\log(R/r))$$.

My question is: what can be done if the second condition cannot be fulfilled, that is, $$r$$ can be $$0$$ (it is possible that the feasible region is a single point)?

• Are there other polynomial-time methods that can be used in this case?
• Alternatively, can it be proved that, without a guarantee that $$r>0$$, the problem is NP-hard?

Note: I asked a similar question in cs.SE, but about the initial ellipsoid (the ball of radius $$R$$) rather than on the small radius $$r$$.