C&SA | Contents

Volume 59 >>> № 5 SEPTEMBER — OCTOBER 2023

-->

UDC 519.85

P.I. Stetsyuk¹, A. Fischer², O.M. Khomiak³

¹ V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv, Ukraine

stetsyukp@gmail.com

² Technical University of Dresden, Institute for Computational Mathematics, Dresden, Germany

Andreas.Fischer@tu-dresden.de

³ V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv, Ukraine

khomiak.olha@gmail.com

UNIFIED PRESENTATION OF THE CLASSICAL ELLIPSOID METHOD

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 available 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 = BB^T. The applications of the algorithms for solving convex programming problems and for finding the saddle point of a convex-concave function are described.

Keywords: ellipsoid method, dilation of space, convex programming, saddle point.

full text

REFERENCES

Glushkov V.M. Fundamentals of paperless informatics [in Russian]. Ed. 2nd. Moscow: Nauka, 1987. 552 p.

Yudin D.B., Nemirovskiy A.S. Information complexity and efficient methods for solving convex extremal problems. Economics and mathematical methods. 1976. Iss. 2. P. 357–369.

Shor N.Z. Clipping method with space stretching for solving convex programming problems. Kibernetika. 1977. N 1. P. 94–95.

Shor N.Z., Biletsky V.I. Space stretching method for speeding up convergence in ravine type problems. Proc. Seminar Scientific Council of the Academy of Sciences of the Ukrainian SSR on Cybernetics "Theory of Optimal Decisions". Kyiv. 1969. N 2. P. 3–18.

Shor N.Z. Using the space stretching operation in problems of minimizing convex functions. Kibernetika. 1970. N 1. P. 6–12.

Stetsyuk P.I., Fischer A., Khomiak O.M. Ellipsoid methods with space scaling. Proc. of the 8th International Conference on Control and Optimization with Industrial Applications (COIA 2022) (24–26 Aug., 2022, Baku, Azerbaijan). 2022. Р. 402–404.

Nemirovsky A.S, Yudin D.B. Problem complexity and method efficiency in optimization. New York: John Wiley, 1983.

Khachiyan L.G. Polynomial algorithms in linear programming, USSR Comput. Math. Math. Phys. 1980. Vol. 20, N 1. Р 53–72.

Fischer A., Khomyak O., Stetsyuk P. The ellipsoid method and computational aspects. Commun. Optim. Theory. 2023. Vol. 21. P. 1–14.

Skokov V.A. A note on minimization methods using the space stretching operation. Kibernetika. 1974. N 4. P. 115–117.

Shor N.Z. Methods for minimizing non-differentiable functions and their applications [in Russian]. Kyiv: Nauk. Dumka, 1979. 200 p.

Gretschel M., Lovasz L., Schrijver A. Geometric algorithms and combinatorial optimization. Berlin: Springer-Verlag, 1988. 362 p.

Shor N.Z. New directions in the development of non-smooth optimization methods. Cybernetics. Kibernetika. 1977. N 6. P. 87–91.

Semenov V.V. Variational inequalities: theory and algorithms [in Ukrainian]. Kyiv: Kyiv University, 2021. 167 с.

Shor N.Z. Nondifferentiable optimization and polynomial problems. Amsterdam: Kluwer, 1998.

Stetsyuk P.I., Fesyuk A.V., Khomyak O.N. Generalized method of ellipsoids. Cybernetics and systems analysis. 2018. Vol.. 54, N 4. P. 70–80.

Stetsyuk P., Fischer A., Khomyak O. The generalized ellipsoid method and Its implementation. In: Jacimovic M., Khachay M., Malkova V., Posypkin M. (Еds.). Optimization and Applications. OPTIMA 2019. Communications in Computer and Information Science. Cham: Springer, 2020. Vol. 1145. P. 355–370.