Чебышевские и евклидовы проекции точки на линейное многообразие

Автор(ы): Губий Е.В., Зоркальцев В.И., Пержабинский С.М.

Выпуск: 80

Рубрика: Системный анализ

Год: 2019

Библиография: Губий Е.В., Зоркальцев В.И., Пержабинский С.М. Чебышевские и евклидовы проекции точки на линейное многообразие // Управление большими системами. Выпуск 80. М.: ИПУ РАН, 2019. С.6-19. DOI: https://doi.org/10.25728/ubs.2019.80.1

Дата опубликования: 31.07.2019

Ключевые слова: весовые коэффициенты, внутренние точки, линейное многообразие, метод наименьших квадратов, чебышевская проекция

Аннотация: Приведены результаты исследования свойств и взаимосвязей чебышевских и евклидовых проекций начала координат на линейное многообразие. В таком виде представляются многие задачи прикладной математики. Евклидовы проекции соответствуют использованию метода наименьших квадратов. Чебышевские проекции соответствуют минимизации максимального отклонения. Приводится и теоретически обосновывается алгоритм поиска чебышевской проекции, всегда дающей однозначный результат и позволяющей обходиться без трудно проверяемого и иногда нарушаемого условия Хаара. Алгоритм базируется на использовании лексикографической оптимизации, на каждом этапе которой отыскивается относительно внутренняя точка оптимальных решений. Свойством вырабатывать относительно внутренние точки оптимальных решений обладают алгоритмы метода внутренних точек. Множества чебышевских и евклидовых проекций начала координат на линейное многообразие формируется путем варьирования положительных весовых коэффициентов при отдельных компонентах векторов в чебышевских и евклидовых нормах. Доказано, что замыкания обоих этих множеств совпадают с множеством векторов линейного многообразия с Парето-минимальными абсолютными значениями компонент. Это в частности означает, что любая чебышевская проекция может быть получена с любой требуемой точностью, как и евклидова проекция, за счет выбора весовых коэффициентов. Это означает также, что любая евклидова проекция (т.е. при любом наборе положительных весовых коэффициентов в евклидовой норме) может быть получена за счет выбора весовых коэффициентов в виде чебышевской проекции.

Author(s): Gubiy E., Zorkaltsev V., Perzhabinsky S.

Article title: Chebyshev and euclidean projections of point on linear manifold

Issue: 80

Year: 2019

Keywords: weight coefficients, interior points, linear manifold, least square method, Chebyshev projection

Abstract: Results of research of properties and interrelations of Chebyshev and Euclidean projections of the origin on linear manifold are considered in the article. Many problems of applied mathematics can be presented in the such view. They are problems of linear approximations, problems of search solutions of balance models closed to the given infeasible solutions, search of pseudosolutions of the models with inconsistent conditions. Euclidean projections are corresponded to application of the least square method. Chebyshev projections are corresponded to minimization of a maximal deviation. We developed and theoretical justified algorithm of searching of Chebyshev projections. The algorithm gives single-valued result and allows to dispense without the difficult verified and sometimes violated Haar condition. The algorithm is based on using of lexicographic optimization. The relative interior point of set of optimal solutions is found on each stage of lexicographic optimization. The property of producing of relative interior points is the main property of algorithms of interior point method. The sets of Chebyshev and Euclidean projections of the origin on linear manifold are formed by way of varying of positive coefficients corresponding to components of vectors in Chebyshev and Euclidean norms. We justified that closure of these sets are equal with the set of vectors of the linear manifold with Pareto-efficient absolute meanings of the components. Consequently, any Chebyshev and Euclidean projection can be get with any required accuracy through choosing the weight coefficients. It was also proved any Euclidean projection with any set of positive weight coefficients in Euclidian norm can be get for the account of choosing the weight coefficients in the form of Chebyshev projection.