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<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$.
