The ellipsoid method and computational aspects

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

This paper gives an overview of particular older and recent results for the ellipsoid method with respect to the contributions by Naum Zuselevich Shor. Therefore, we present this method as a subgradient algorithm with space dilation. For a certain choice of the dilation coefficient, this is a method of outer approximation of semi-ellipsoids by ellipsoids with monotonous decrease in their volume. The paper shows results on properties and applications of the ellipsoid method including computational aspects. Two forms of the ellipsoid method are described which differ in the way of updating the inverse space transformation matrix. The applicability of the ellipsoid method to several problem classes, like convex programs and saddle point problems for convex-concave functions, is discussed. Finally, the acceleration of the ellipsoid method by deeper ellipsoid approximations is also dealt with.

Details

Original languageEnglish
Article number21
Number of pages14
Journal Communications in optimization theory : COT
Volume2023
Publication statusPublished - 2023
Peer-reviewedYes

External IDs

Scopus 105020082137

Keywords

DFG Classification of Subject Areas according to Review Boards

Subject groups, research areas, subject areas according to Destatis