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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.