Convergence Rates of the Ellipsoid Method on General Convex Functions.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1981
- Accession Number
- ADA099291
Entities
People
- Jean-louis Goffin
Organizations
- Stanford University