2024, issue 1, p. 27-46
Received 12.03.2024; Revised 18.03.2024; Accepted 19.03.2024
Published 29.03.2024; First Online 31.03.2024
https://doi.org/10.34229/2707-451X.24.1.3
Previous | FULL TEXT (in Ukrainian) | Next
Using the Ellipsoid Method for Sylvester's Problem and its Generalization
Petro Stetsyuk 1 *
, Olha Khomiak 1
, Oleksander Davydov 2
1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
2 Taras Shevchenko National University of Kyiv, Ukraine
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Sylvester's problem or the problem of the smallest bounding circle is the problem of constructing a circle of the smallest radius that contains a finite set of points on the plane. In n-dimensional space, it corresponds to the problem of the smallest bounding hypersphere, which can be formulated as the problem of minimizing a convex piecewise quadratic function.
The article is dedicated to study of the ellipsoid method application for solving this problem and the minimax convex programming problem, which is equivalent to the generalized problem of the smallest bounding hypersphere. The generalized problem consists in finding the center of a sphere in an n-dimensional space that has a minimal radius and contains a finite set of n-dimensional spheres given by their centers and radii.
The article consists of 3 sections. Section 1 describes the emshor algorithm – the algorithm of the ellipsoid method for problem of minimization of an arbitrary convex function, proves its convergence theorems, gives a geometric interpretation of the algorithm, which is based on the use of a minimum volume ellipsoid. Octave implementation of the emshor algorithm is presented here, which can be successfully applied for non-smooth convex functions minimization if the number of variables is n = 2 ¸ 30.
In Section 2, the sylvester1 algorithm is built, which is an application of the emshor algorithm for solving the problem of minimizing a convex piecewise quadratic function, which is equivalent to the problem of finding a sphere of minimum radius for a finite set of points. In Section 3, the sylvester2 algorithm is built, which is an application of the emshor algorithm for solving the problem of minimization of a convex function, which is equivalent to the generalized problem of finding a sphere of minimum radius for a finite set of spheres with given centers and radii. The results of testing the sylvester1 and sylvester2 algorithms demonstrate high working speed for modern computers and high accuracy in terms of optimal value of the objective function when solving problems in n-dimensional spaces for small values n = 2 ¸ 30.
Keywords: ellipsoid method, convex function, Sylvester's problem, piecewise smooth function, minimax problem.
Cite as: Stetsyuk P., Khomiak O., Davydov O. Using the Ellipsoid Method for Sylvester's Problem and its Generalization. Cybernetics and Computer Technologies. 2024. 1. P. 27–46. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.1.3
References
1. Sylvester J.J. A question in the geometry of situation. Quarterly Journal of Mathematics. 1857. Т. 1. С. 79.
2. Yudyn D.B., Nemyrovskii A.S. Information complexity and efficient methods of solving convex extremal problems. Ekonomika i Mat. Metody. 1976. Iss. 2. P. 357–369.
3. 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
4. Shor N.Z., Biletskii V.I. The method of space dilation for accelerating convergence in ravine-type problems. Teoria optimalnyh resheniy. 1969. No. 2. P. 3–18.
5. Shor N.Z. Utilization of the operation of space dilatation in the minimization of convex functions. Cybern Syst Anal. 1972. Vol. 6. No. 1. P. 7–15. https://doi.org/10.1007/BF02341816
6. Shor N.Z. Methods of Minimization of Non-Differentiable Functions and their Applications. Kyiv: Naukova Dumka, 1979. 200 p. (in Russian)
7. Octave. http://www.octave.org (accessed: 12.03.2024)
8. Fischer A., Khomyak O., Stetsyuk P. The ellipsoid method and computational aspects. Commun. Optim. Theory. 2023. No. 21. P. 1–14.
9. Stetsyuk P.I., Fischer A., Khomiak O.M. Unified Representation of the Classical Ellipsoid Method. 2023. Cybern Syst Anal. Vol. 59. P. 784–793. https://doi.org/10.1007/s10559-023-00614-x
10. Smallest-circle problem. https://en.wikipedia.org/wiki/Smallest-circle_problem (accessed: 12.03.2024)
11. Khomiak O.M., Davydov O.O. The ellipsoid method for the minimum radius hypersphere. Proceedings of the 7th International Scientific Conference "Mathematical Modeling, Optimization and Information Technologies (MMOTI-2021)", November 15–19, 2021. P. 340–342. (In Ukrainian)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next