Unified Presentation of the Generalized Ellipsoid Method

Petro Stetsyuk (), Andreas Fischer () and Olha Khomiak ()
Additional contact information
Petro Stetsyuk: National Academy of Sciences of Ukraine, V. M. Glushkov Institute of Cybernetics
Andreas Fischer: Technische Universität Dresden, Faculty of Mathematics
Olha Khomiak: National Academy of Sciences of Ukraine, V. M. Glushkov Institute of Cybernetics

A chapter in Theory, Algorithms, and Experiments in Applied Optimization, 2025, pp 345-376 from Springer

Abstract: Abstract The paper reviews classical and some recent developments in the field of ellipsoid methods and its applications. Based on a parametrization of the generalized ellipsoid method, it is demonstrated that for certain values of the space scaling parameter λ > 0 $$\lambda >0$$ , the method reduces to well-known special cases of the ellipsoid method, namely, to those of Shor, Nemirovsky and Yudin, and of Khachiyan. Moreover, convergence properties of two theoretically equivalent algorithmic versions of the parameterized generalized ellipsoid method are derived. The first version is based on updating an asymmetric matrix B, whereas the second one updates a symmetric matrix H = B B ⊤ $$H=BB^\top $$ . Numerical differences of these versions are highlighted. Several applications of the parametrized generalized ellipsoid method are described, e.g., convex optimization problems and finding saddle points of convex-concave functions. This also includes more detailed examples related to Lagrangian upper bounds for Boolean optimization, the minimization of ravine functions, and the numerical solution of a problem by Sylvester. Finally, a software implementation is discussed.

Keywords: Nonsmooth optimization; Convex programming; Saddle point problem; Lagrangian bounds; Ellipsoid method; Space dilation; Subgradient algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-91357-0_16

Ordering information: This item can be ordered from
http://www.springer.com/9783031913570

DOI: 10.1007/978-3-031-91357-0_16

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().