The ellipsoid method and computational aspects

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

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

OriginalspracheEnglisch
Aufsatznummer21
Seitenumfang14
Fachzeitschrift Communications in optimization theory : COT
Jahrgang2023
PublikationsstatusVeröffentlicht - 2023
Peer-Review-StatusJa

Externe IDs

Scopus 105020082137

Schlagworte

DFG-Fachsystematik nach Fachkollegium

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis