ЧЕБИШОВСЬКI ПРОЕКЦIЇ НА ПОЛIЕДР
DOI:
https://doi.org/10.17721/2706-9699.2021.2.02Ключові слова:
полiедр, чебишовськi норми, чебишовськi апроксимацiїАнотація
Задача мiнiмiзацiї зваженої чебишовської норми на опуклому полiедрi, який визначається як множина розв’язкiв системи лiнiйних нерiвностей, може мати не єдиний розв’язок. Причому серед розв’язкiв цiєї задачi можуть виявитись такi, що зовсiм не пiдходять на роль найближчих до нульового вектора точок полiедра. Це ускладнює, зокрема, чебишовську апроксимацiю. З метою подолання проблем, якi при цьому виникають, використовується умова Хаара, яка означає вимогу єдиностi розв’язку наведеної задачi. Цю вимогу не завжди легко перевiрити i не зрозумiло що робити, якщо вона не виконується. Наведено алгоритм, який будує завжди єдиний розв’язок наведеної задачi, i заснований на пошуку вiдносно внутрiшнiх точок оптимальних розв’язкiв скiнченої послiдовностi задач лiнiйного програмування. Розв’язок, що будується, названо чебишовською проекцiєю початку координат на полiедр. Доведено, що цей розв’язок є вектором полiедра з парето-мiнiмальними абсолютними значеннями компонент. Доведено, що спiвпадають множини чебишовських (за введеним алгоритмом) i евклiдових проекцiй початку координат на полiедр, якi утворюються при варiюваннi позитивних вагових коефiцiєнтiв в евклiдових та чебишовських нормах, що мiнiмiзуються.
Посилання
Eremin I. I. Theory of linear optimization. Ekaterinburg: Publishing House of the Ural Branch of the Russian Academy of Sciences, 1999. (In Russian)
Rockafellar R. Convex analysis. M.: Mir, 1973. (In Russian)
Zorkal'tsev V. I., Kiseleva M. A. Systems of linear inequalities: Textbook. Irkutsk: IGU, 2007. (In Russian)
Zorkal'tsev V. I. Projections of a point onto a polyhedron. Zh. Vychisl. Mat. Mat. Fiz. 2013. V. 53. No. 1. P. 4–19. (In Russian)
Zorkal'tsev V. I. Octahedral projections of a point onto a polyhedron. Comput. Math. Math. Phys. 2018. V. 58. No. 5. P. 813–821.
Haar A. Die Minkowskishe Geometrie und die Annaherung an stetige Funktionen. Math Ann. 1918. Vol. 78. No. 3. P. 299–311.
Collatz L., Krabs V. Approximation Theory. Chebyshev approximations and their applications. Moscow: Nauka, 1978. (In Russian)
Chernikov S. N. Linear inequalities. Moscow: Nauka, 1968. (In Russian)
Zorkal'tsev V. I. Chebyshev and other projections of a point onto a polyhedron. Abstracts of the report of the international. conf. "Constructive non-smooth analysis and related issues", dedicated to the memory of Professor V. F. Demyanov. Part II. St. Petersburg: VVM Publishing House, 2017, pp. 264–270. (In Russian)
Zorkal'tsev V. I. Interior point method: history and prospects. Zh. Vychisl. Mat. Mat. Fiz. 2019. V. 59. No. 10. P. 1649–1665 (In Russian)
Gubiy E. V., Zorkal'tsev V. I., Perzhabinsky S. M. Chebyshev and Euclidean projections of points onto a linear manifold. Management of large systems. 2019. No. 80. P. 6–19. (In Russian)
Zorkal'tsev V. I. Chebyshev projections onto a linear manifold. Proceedings of the Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences. 2020. No. 3. P. 44–55. (In Russian)
Chebyshev P. L. Questions about the smallest quantities related to the approximate representation of a function. Full coll. op. Vol. 2, M.–L., 1947, pp. 151–235. (In Russian)
Kolmogorov A. N. Remarks on P. L. Chebyshev polynomials that deviate least from a given function. Uspekhi math. nauk. 1948. Vol. III, no. 1(23). P. 216–221. (In Russian)
Zukhovitsky S. I., Krein M. G. Remarks on one possible generalization of the theory of A. Haar and A. N. Kolmogorov. Uspekhi math. nauk. 1950. Vol. V, no. 1(35). P. 217–229. (In Russian)
Dolganov R. L. Chebyshev approximation by asymptotically convex families of functions. Izv. VUZov. Mathematics. 1972. No. 7. P. 35–41. (In Russian)
Aleksandrenko V. L. An algorithm for constructing an approximate uniformly best solution to a system of inconsistent linear equations. Algorithms and algorithmic languages. 1968. Issue. 3. P. 57–64. (In Russian)
Demyanov V. F., Malozemov V. N. Introduction to minimax. Moscow: Nauka, 1972. (In Russian)
Kalenchuk-Porkhanova A. A. The best Chebyshev approximation of functions of one and several variables. Cybernetics and system analysis. 2009. No. 6. P. 155–164. (In Russian)
Levin V. L. Application of E. Helly's theorem in convex programming, problems of best approximation and related issues. Mathematicheskyi Sbornik. 1969. Vol. 79 (21), No. 2 (6). P. 250–263. (In Russian)
