Convergence Rates of the Ellipsoid Method on General Convex Functions

摘要

The ellipsoid method is applied to the unconstrained minimization of a general convex function. The method converges at a geometric rate, which depends only upon the dimension of the space but not on the actual function. This rate can be improved somewhat if the function satisfies some Lipschitz-type condition, or if the minimum set has dimension greater than zero. If the ellipsoid entirely contains the optimal set, equating the Steiner polynomial associated to the optimal set, and the volume of the ellipsoid at a given iteration, will give an upper bound on the minimum recorded function value. (Author)