Abstract
An algorithm with space dilation is presented, which is the circumscribed ellipsoid method under a certain choice of dilation coefficient. It is shown that its special case is the Yudin–Nemirovsky–Shor ellipsoid method. The application of the algorithm to solving a convex programming problem and the problem of finding a saddle point of a convex-concave function are described.
Similar content being viewed by others
References
D. B. Yudin and A. S. Nemirovsky, “Information complexity and efficient methods to solve convex extremum problems,” Ekonomika i Mat. Metody, Issue 2 (1976), pp. 357–369.
N. Z. Shor, “Cut-off method with space extension in convex programming problems,” Cybernetics, Vol. 13, No. 1, 94–96 (1977).
P. I. Stetsyuk, “The general scheme of the ellipsoid method,” in: News Bulletin AMP No. 13, UrO RAN, Ekaterinburg (2015), pp. 59–60.
P. I. Stetsyuk, “A generalization of the classical ellipsoid method,” in: Proc. 6th All-Ukrainian Pract. Conf. Informatics and Systems Sciences (ISN–2015), Poltava, March 19–21, 2015, PUET, Poltava (2015), pp. 335–337.
N. Z. Shor, Minimization Methods for Non-Differentiable Functions, Springer-Verlag, Berlin (1985).
P. I. Stetsyuk, “An approximate method of ellipsoids,” Cybern. Syst. Analysis, Vol. 39, No. 3, 435–439 (2003).
N. Z. Shor, “New development trends in nondifferentiable optimization,” Cybernetics, Vol. 13, No. 6, 881–886 (1977).
A. Fischer, M. Herrich, and K. Schonefeld, “Generalized Nash equilibrium problems — recent advances and challenges,” Pesquisa Operacional, Vol. 34, 521–558 (2014).
A. N. Daryina and A. F. Izmailov, “Newton-type method for variational equilibrium problem,” in: Proc. 8th Moscow Intern. Conf. on Operations Research (ORM2016), Moscow, October 17– 22, 2016, Vol. 1, MAKS Press, Moscow (2016), pp. 21–22.
P. I. Stetsyuk, “Method of simple-body centroids,” Cybern. Syst. Analysis, Vol. 32, No. 5, 696–708 (1996).
P. I. Stetsyuk, Methods of Ellipsoids and r-Algorithms [in Russian], Eureka, Chisinau (2014).
P. I. Stetsyuk, “r-algorithms and ellipsoids,” Cybern. Syst. Analysis, Vol. 32, No. 1, 93–110 (1996).
Author information
Authors and Affiliations
Corresponding author
Additional information
*The study was supported by the National Academy of Sciences of Ukraine (projects No. 0117U000327, No. 0116U004558) and Volkswagen Foundation (grant No. 90 306).
Translated from Kibernetika i Sistemnyi Analiz, No. 4, July–August, 2018, pp. 70–80.
Rights and permissions
About this article
Cite this article
Stetsyuk, P.I., Fesiuk, O.V. & Khomyak, O.N. The Generalized Ellipsoid Method*. Cybern Syst Anal 54, 576–584 (2018). https://doi.org/10.1007/s10559-018-0058-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-018-0058-4