Full Text: PDF
DOI: 10.23952/cot.2023.21
Received November 14, 2022; Accepted February 24, 2023; Published May 15, 2023
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.
How to Cite this Article:
A. Fischer, O. Khomyak, P. Stetsyuk, The ellipsoid method and computational aspects, Commun. Optim. Theory 2023 (2023) 21.