Email this article Finite approximation methods for two-dimensional sets and their application to geometric optimization problems
- Authors: Nefedov V.N.1, Svoykin F.V.2, Garibyan B.A.1, Ryapukhin A.V.1, Korolko N.S.2
-
Affiliations:
- Moscow Aviation Institute (National Research University)
- Saint Petersburg State Forest Technical University under name of S. M. Kirov
- Issue: Vol 29, No 1 (2025)
- Pages: 129-157
- Section: Mathematical Modeling, Numerical Methods and Software Complexes
- URL: https://journals.rcsi.science/1991-8615/article/view/311046
- DOI: https://doi.org/10.14498/vsgtu2131
- EDN: https://elibrary.ru/DMJLWE
- ID: 311046
Cite item
Full Text
Abstract
This study investigates the problem of approximating closed bounded sets in two-dimensional real space by finite subsets with a given accuracy in the Hausdorff metric. The main focus is on developing an effective approximation method for the class of sets defined by stepwise systems of inequalities.
The proposed method is based on constructing special grid structures that allow controlling the approximation accuracy through a parameter $\tau > 0$. Corresponding theoretical statements about the properties of such approximations are proved.
The problem of finding an optimal piecewise-linear path between two points with a single turn under angle constraints is examined in detail. The developed methods are applicable for solving various geometric optimization problems.
Full Text
##article.viewOnOriginalSite##About the authors
Victor N. Nefedov
Moscow Aviation Institute (National Research University)
Email: nefedovvn54@yandex.ru
ORCID iD: 0000-0001-6053-2066
Scopus Author ID: 7103271245
ResearcherId: S-2650-2019
https://www.mathnet.ru/person63464
Cand. Phys. & Math. Sci., Associate Professor; Associate Professor; Dept. of Mathematical Cybernetics1
Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4Fedor V. Svoykin
Saint Petersburg State Forest Technical University under name of S. M. Kirov
Email: svoykin_fv@mail.ru
ORCID iD: 0000-0002-8507-9584
SPIN-code: 8938-6910
Scopus Author ID: 57217847423
ResearcherId: AAC-4074-2020
https://www.mathnet.ru/person228056
Cand. Techn. Sci., Associate Professor; Associate Professor; Dept. of Forestry Technology2
Russian Federation, 194021, Saint Petersburg, Institutskiy per., 5Boris A. Garibyan
Moscow Aviation Institute (National Research University)
Email: bagarib@yandex.ru
ORCID iD: 0000-0001-8309-3086
SPIN-code: 8622-4854
Scopus Author ID: 57202449216
ResearcherId: Y-6983-2018
https://www.mathnet.ru/person228057
Cand. Phys. & Math. Sci., Associate Professor; Associate Professor; Dept. of Mathematical Cybernetics1
Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4Anatoliy V. Ryapukhin
Moscow Aviation Institute (National Research University)
Author for correspondence.
Email: anatoliiruapukhin@yandex.ru
ORCID iD: 0000-0002-2208-6875
SPIN-code: 6693-0850
Scopus Author ID: 57211373896
ResearcherId: ABB-3999-2020
https://www.mathnet.ru/person145977
Senior Lecturer; Dept. of Design and Certification of Aviation Equipment1
Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4Nikolay S. Korolko
Saint Petersburg State Forest Technical University under name of S. M. Kirov
Email: kns89lta@mail.ru
ORCID iD: 0009-0009-6289-2984
SPIN-code: 6309-8365
Scopus Author ID: 57220187617
https://www.mathnet.ru/person228087
Postgraduate Research Student; Dept. of Forestry Technology2
Russian Federation, 194021, Saint Petersburg, Institutskiy per., 5References
- Vasil’ev F. P. Chislennye metody resheniia ekstremal’nykh zadach [Numerical Methods for Solving of Extremal Problems]. Moscow, Nauka, 1988, 550 pp. (In Russian). EDN: UTKWUO.
- Nesterov Yu. E. Vvedenie v vypukluiu optimizatsiiu [Introduction to Convex Optimization]. Moscow, Moscow Center for Continuous Mathematical Education, 2010, 280 pp. (In Russian). EDN: SDSFYV.
- Nefedov V. N. Some problems of solving Lipschitzian global optimization problems using the branch and bound method, Comput. Math. Math. Phys., 1992, vol. 32, no. 4, pp. 433–445. EDN: XKQMEC.
- Evtushenko Yu. G. Numerical methods for finding global extrema (Case of a non-uniform mesh), U.S.S.R. Comput. Math. Math. Phys., 1971, vol. 11, no. 6, pp. 38–54. EDN: XOYJSF. DOI: https://doi.org/10.1016/0041-5553(71)90065-6.
- Leonov V. V. The method of coverings for seeking a global maximum of a function of several variables, In: Issledovanie po kibernetike [Research in Cybernetics]. Moscow, Sov. Radio, 1970, pp. 41–52 (In Russian).
- Piyavskii S. A. An algorithm for finding the absolute extremum of a function, U.S.S.R. Comput. Math. Math. Phys., 1972, vol. 12, no. 4, pp. 57–67. EDN: TTTJWV. DOI: https://doi.org/10.1016/0041-5553(72)90115-2.
- Potapov M. A. Methods of non-uniform coverings and their application for solving problems of global optimization in a dialogue mode, Diss. Cand. Phys. Math. Sci. Moscow, 1984, 104 pp. (In Russian). EDN: NPAFWT.
- Nefedov V. N. On a method of global maximization of a function of several variables on a rectangular prism, Dep. in VINITI, 1.06.85, no. 377-85 DEP. Moscow, 1985 (In Russian).
- Evtushenko Yu. G., Rat’kin V. A. The method of half-divisions for global optimization of a function of many variables, Sov. J. Comput. Syst. Sci., 1987, vol. 25, no. 5, pp. 75–84.
- Nefedov V. N. The search for a global maximum of a function of several variables in a set specified by constraints of the inequality type, U.S.S.R. Comput. Math. Math. Phys., 1987, vol. 27, no. 1, pp. 23–32. DOI: https://doi.org/10.1016/0041-5553(87)90114-5.
- Ishenko A. V., Kireev I. V. The algorithm for generation of two-dimensional embedded grids, J. Sib. Fed. Univ. Math. Phys., 2009, vol. 2, no. 1, pp. 83–90 (In Russian). EDN: JWKGRP.
- Nefedov V. N. Approximation of a Pareto set, U.S.S.R. Comput. Math. Math. Phys., 1984, vol. 24, no. 4, pp. 19–28. DOI: https://doi.org/10.1016/0041-5553(84)90225-8.
- Nefedov V. N. Approximation of a set of Pareto-optimal solutions, U.S.S.R. Comput. Math. Math. Phys., 1986, vol. 26, no. 1, pp. 99–107. DOI: https://doi.org/https://doi.org/10.1016/0041-5553(86)90192-8.
- Hausdorff F. Set Theory. New York, Dover Publ., 1944, 307 pp.
- Skvortsov V. A. Primery metricheskikh prostranstv [Examples of Metric Spaces], Matematicheskoe Prosveshchenie, vol. 16. Moscow, Moscow Center for Continuous Mathematical Education, 2012, 27 pp. (In Russian). EDN: QJZGML.
Supplementary files
