Accession Number:

ADA099291

Title:

Convergence Rates of the Ellipsoid Method on General Convex Functions.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s):

Report Date:

1981-01-01

Pagination or Media Count:

42.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE