Чебишовськi проекцiї на полiедр

Zorkaltsev, V. I. (2021). The Chebyshev Projections on Polyhedron. Journal of Numerical and Applied Mathematics, (2), 17–33. 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зуються.