Unified representation of the classical ellipsoid method

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

A parametric version of the ellipsoid method with space scaling by a scalar parameter λ > 0 is considered. For certain values of the parameter λ, it is reduced to the well-known versions of the ellipsoid method, namely, the Shor, Khachiyan, Nemirovsky, and Yudin ones. The properties of two algorithmic implementations of the parameterized ellipsoid method are proved. The first algorithm is based on updating the asymmetric matrix B, and the second one updates the symmetric matrix H = BBT. The applications of the algorithms for solving convex programming problems and finding the saddle point of a convex-concave function are described.

Details

Original languageEnglish
Pages (from-to)784-793
Number of pages10
JournalCybernetics and Systems Analysis
Volume59
Issue number5
Publication statusPublished - Sept 2023
Peer-reviewedYes

External IDs

Scopus 85173251021
Mendeley 610f84cf-6ed1-3e66-80d0-181eabe3efea

Keywords

Research priority areas of TU Dresden

DFG Classification of Subject Areas according to Review Boards

Subject groups, research areas, subject areas according to Destatis

Keywords

  • convex programming, ellipsoid method, saddle point, space dilation

Library keywords