Let S⊆ℝ’n be a convex set for which there is an oracle with the following property. Given any point z∈ℝn the oracle returns a ‘Yes’ if z∈S; whereas if zℝS then the oracle returns a ‘No’ together with a hyperplane that separates z from S. The feasibility problem is the problem of finding a point in S; the convex optimization problem is the problem of minimizing a convex function over S. The paper presents a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. The present algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.
