A cutting plane algorithm for minimizing a convex function subject to constraints defined by a separation oracle is presented. The algorithm is based on approximate analytic centers. The nonlinearity of the objective function is taken into account, yet the feasible region is approximated by a containing polytope. This containing polytope is regularly updated either by adding a new cut at or by shifting an existing cut to the test point. In the first phase of the algorithm, the test point is an approximate analytic center of a containing polytope. In the second phase, it becomes an approximate analytic center of the intersection of a containing polytope and a level set of the nonlinear objective function. We prove that the algorithm converges and establish its complexity. In the case where the oracle generates a finite number of cuts, the algorithm is polynomial in this number, while it is a polynomial approximation scheme (in the dimension of the space) in the case where the oracle can generate an infinite number of cuts.