Unified Presentation of the Generalized Ellipsoid Method
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Buch/Sammelband/Gutachten › Beigetragen › Begutachtung
Beitragende
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, 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=BB⊤. 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.
Details
| Originalsprache | Englisch |
|---|---|
| Titel | Theory, Algorithms, and Experiments in Applied Optimization |
| Redakteure/-innen | Boris Goldengorin |
| Erscheinungsort | Cham |
| Herausgeber (Verlag) | Springer, Cham |
| Seiten | 345-376 |
| Seitenumfang | 32 |
| ISBN (elektronisch) | 978-3-031-91357-0 |
| ISBN (Print) | 978-3-031-91356-3, 978-3-031-91359-4 |
| Publikationsstatus | Veröffentlicht - 2025 |
| Peer-Review-Status | Ja |
Publikationsreihe
| Reihe | Springer Optimization and Its Applications |
|---|---|
| Band | 226 |
| ISSN | 1931-6828 |
Externe IDs
| Mendeley | 2ab44c13-d839-3a4d-9459-cf6da6cfac7d |
|---|---|
| Scopus | 105021309562 |
Schlagworte
Forschungsprofillinien der TU Dresden
DFG-Fachsystematik nach Fachkollegium
Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis
Ziele für nachhaltige Entwicklung
ASJC Scopus Sachgebiete
Schlagwörter
- Space dilation, Lagrangian bounds, Subgradient algorithm, Nonsmooth optimization, Saddle point problem, Convex programming, Ellipsoid method