2024, issue 3, p. 48-59
Received 03.09.2024; Revised 09.09.2024; Accepted 10.09.2024
Published 24.09.2024; First Online 30.09.2024
https://doi.org/10.34229/2707-451X.24.3.5
Previous | FULL TEXT (in Ukrainian) | Next
Three Ellipsoids for External Approximation of the Half-Ball
Olha Khomiak 
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Ellipsoids that approximate the half-ball in Rn (n ≥ 2) and their volume is smaller than the volume of the ball can be used to construct algorithms for solving the problem of minimization of a convex (smooth or non-smooth) function, the problem of minimization of a convex function on a sphere, a general problem convex programming, saddle point problems of convex-concave functions and others. The speed of convergence of such algorithms will be determined by the ratio of the volume of the approximating ellipsoid to the volume of the ball.
The purpose of the work is to describe properties of three ellipsoids for approximation of a n-dimensional half-ball, the volume reduction factor of which depends only on n – dimension of space. The first is the well-known ellipsoid of minimum volume, which is used in the classical Yudin-Nemirovsky-Shor ellipsoid method. It provides a minimum volume reduction factor and can be used if n ≥ 2. If n = 1, then the classical ellipsoid method replaces the dichotomy method. The other two ellipsoids are close to the minimum volume ellipsoid and at large n guarantee volume reduction coefficients close to the minimum.
The results. It is shown that when n = 1 the first approximate ellipsoid provides a coefficient of reduction of the segment length equal to 2–√2 ≈ 0.5858. The second approximate ellipsoid is new and the volume reduction factor for it is slightly larger than the factor for the first approximate ellipsoid. If n = 1, then it provides a coefficient of reduction of the segment length equal to (√5–1)/2 ≈ 0.6180. For three ellipsoids, comparative results are given in terms of volume reduction coefficients (n = 1÷20) and the number of iterations for solving problems with relative accuracy 10–10 (n = 1÷30).
Conclusions. A new ellipsoid has been constructed to approximate the n-dimensional half-ball, which is close in volume to the minimal ellipsoid. The volume reduction factor of the proposed ellipsoid is approximated by an asymptotic formula 1–1/(2n)+1/n2, which differs little from the formula 1–1/(2n) for an ellipsoid of minimum volume.
Keywords: ball, ellipsoid, space dilation, ellipsoid method, dichotomy method.
Cite as: Khomiak O. Three Ellipsoids for External Approximation of the Half-Ball. Cybernetics and Computer Technologies. 2024. 3. P. 48–59. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.3.5
References
1. Shor N. Z. Methods of Minimization of Non-Differentiable Functions and their Applications. Kyiv: Nauk.Dumka, 1979. 200 p. (in Russian)
2. Stetsyuk P.I., Fischer A., Khomiak O.M. Unified Representation of the Classical Ellipsoid Method. Cybern Syst Anal. 2023. Vol. 59. P. 784–793. https://doi.org/10.1007/s10559-023-00614-x
3. Yudin D.B., Nemirovsky A.S. Information complexity and efficient methods of solving convex extremal problems. Ekonomika i Mat. Metody. 1976. Iss. 2. P. 357–369. (in Russian)
4. Shor N.Z. Cut-off method with space extension in convex programming problems. Cybern Syst Anal. 1977. Vol. 13, No. 1. P. 94–96. https://doi.org/10.1007/BF01071394
5. Stetsyuk P.I. An approximate method of ellipsoids. Cybern Syst Anal. 2003. Vol. 39, No. 3. P. 435–439. https://doi.org/10.1023/A:1025717729043
6. Stetsyuk P.I., Fesiuk A.V., Khomyak O.N. The generalized ellipsoid method. Cybern Syst Anal. 2018. Vol. 54, No. 4. P. 576–584. https://doi.org/10.1007/s10559-018-0058-4
7. Stetsyuk P., Fischer A., Khomyak O. The generalized ellipsoid method and its implementation. In: Jacimovic M., Khachay M., Malkova V., Posypkin M. Optimization and Applications, OPTIMA 2019. Communications in Computer and Information Science. Springer, Cham. 2020. Vol. 1145. P. 355–370. https://doi.org/10.1007/978-3-030-38603-0_26
8. Grötschel M., Lovász L., Schrijver A. Geometric Algorithms and Combinatorial Optimization. Berlin: Springer-Verlag, 1988. 362 p. https://doi.org/10.1007/978-3-642-97881-4
9. Nemirovsky A.S., Yudin D.B. Problem Complexity and Method Efficiency in Optimization. New York: John Wiley, 1983.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next