В.И. Зоркальцев. Чебышевские проекции на линейное многообразие ... С. 44-55

УДК 519.6

MSC: 03C07, 03C60

DOI: 10.21538/0134-4889-2020-26-3-44-55

Работа выполнена в рамках научного проекта РАН № 0279-2019-0003 и при финансовой поддержке РФФИ (проект 19-07-00322).

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

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

СПИСОК ЛИТЕРАТУРЫ

1.   Еремин И. И. Противоречивые модели экономики. Москва: Наука, 1980. 160 с.

2.   Ватолин А. А. Об аппроксимации несовместных систем линейных уравнений и неравенств // Методы аппроксимации несобственных задач математического программирования. Свердловск: Изд-во УрО АН СССР, 1984. С. 39–54.

3.   Лоусон Ч., Хенсон Р. Численное решение задач методом наименьших квадратов. Москва: Наука, 1986. 232 с.

4.   Фролов В. Н. Оптимизация плановых программ при согласованных ограничениях. Москва: Наука, 1986. 165 c.

5.   Черкассовский Б. В. Задачи балансировки матриц // Методы математического программирования и программное обеспечение. Свердловск: Изд-во УрО АН СССР, 1984. С. 216–217.

6.   Зоркальцев В. И. Метод наименьших квадратов: геометрические свойства, альтернативные подходы, приложения. Новосибирск: Наука, 1995. 220 с.

7.   Аганбегян А. Г., Гранберг А. Г. Экономико-математический анализ межотраслевого баланса СССР. Москва: Мысль, 1968. 357 с.

8.   Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. Москва: Наука, 1968. 544 с.

9.   Самарский А. А., Гулин А. В. Численные методы: учеб. пособие для вузов. Москва: Наука, 1989. 432 с.

10.   Зоркальцев В. И. Октаэдрические и евклидовы проекции точки на линейное многообразие // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 18, №3. С. 106–118.

11.   Рокафеллар Р. Выпуклый анализ. Москва: Мир, 1973. 470 с.

12.   Мудров В. И., Кушко В. Л. Методы обработки измерений (квазиправдоподобные оценки). Москва: Сов. радио, 1976. 192 с.

13.   Мудров В. И., Кушко В. Л. Методы обработки измерений: квазиподобные оценки. Москва: Наука, 1983. 304 с.

14.   Лакеев А. В., Носков С. И. Метод наименьших модулей для линейной регрессии: число нулевых ошибок аппроксимации // Тр. XV Байкальской междун. школы-семинара “Методы оптимизации и их приложения”. Иркутск: РИО ИДСТУ СО РАН, 2011. Т. 2. С. 117–120.

15.   Черников С. Н. Линейные неравенства. Москва: Наука, 1968. 488 с.

16.   Зоркальцев В. И. Проекции точки на полиэдр // Журн. вычисл. математики и мат. физики. 2013. Т. 53, №1. С. 4–19.

17.   Еремин И. И., Астафьев Н. И. Введение в теорию линейного и выпуклого программирования. Москва: Наука, 1970. 141 с.

18.   Астафьев Н. И. Линейные неравенства и выпуклость. Москва: Наука, 1982. 162 с.

19.   Еремин И. И., Мазуров В. Д., Астафьев Н. И. Несобственные задачи линейного и выпуклого программирования. Москва: Наука, 1983. 336 с.

20.   Чебышев П. Л. Вопросы о наименьших величинах, связанных с приближенным представлением функций. Полное собрание сочинений. Москва; Ленинград: Изд-во АН СССР, 1944. С. 151–235.

21.   Демьянов В. Ф., Малоземов В. Н. Введение в минимакс. Москва: Наука, 1972. 368 с.

22.   Малоземов В. Н. Получение равномерного приближения функций нескольких аргументов // Журн. вычисл. математики и мат. физики. 1970. № 3. С. 575–586.

23.   Коллатц Л., Крабе В. Теория приближений. Чебышевские приближения и их приложения. Москва: Наука, 1978. 269 с.

24.   Haare A. Die Minkowskische Geometrie und die AnnЈaherung an stetige Funktionen // Math. Ann. 1918. Vol. 78, № 3. P. 415–127.

25.   Зоркальцев В. И. Метод внутренних точек: история и перспективы // Журн. вычисл. математики и мат. физики. 2019. Т. 59, №10. С. 1649–1665.

26.   Зоркальцев В. И., Киселева М. А. Системы линейных неравенств (учеб. пособие). Иркутск: Иркут. гос. ун-т, 2007. 128 с.

27.   Губий Е. В., Зоркальцев В. И., Пержабинский С. М. Чебышевские и евклидовы проекции точки на линейное многообразие // Управление большими системами. 2019. Вып. 80. С. 6–19.

28.   Зоркальцев В. И. Чебышевские приближения могут обходиться без условия Хаара // Материалы междун. симпозиума “Динамические системы, оптимальное управление и математическое моделирование” / Иркут. гос. ун-т. Иркутск, 2019. C. 29–33.

Поступила 03.06.2020

После доработки 25.07.2020

Принята к публикации 10.08.2020

Зоркальцев Валерий Иванович
д-р техн. наук, профессор
ведущий науч. сотрудник
Лимнологический институт СО РАН
г. Иркутск
e-mail: zork@isem.irk.ru

Ссылка на статью: В.И. Зоркальцев. Чебышевские проекции на линейное многообразие // Тр. Ин-та математики и механики УрО РАН. 2020. Т.26, № 3. С. 44-55 

English

V.I. Zorkal’tsev. Chebyshev projections to a linear manifold

Many problems of applied mathematics are presented in the form of the problem of finding the point of a linear manifold closest to the origin. In particular, this problem may take the form of a minimization problem for the Euclidean (least squares method) or Chebyshev norms. The use of these norms means that the Euclidean or Chebyshev projection of the origin onto a linear manifold is sought. By introducing and varying positive weight coefficients at the components of vectors in these norms, sets of Euclidean and Chebyshev norms are obtained that generate sets of Euclidean and Chebyshev projections. The search for the Chebyshev projection onto a linear manifold is represented as a linear program, which may have a nonunique solution. Moreover, some of its solutions may be clearly unsatisfactory with regards to the essence of the problem. In order to overcome the arising difficulties, the Haar condition is used in the Chebyshev approximation. This condition corresponds to the uniqueness requirement for the solution of the linear programming problem and is not always easy to check; moreover, it is not clear what to do if the condition is not met. We present an algorithm that always leads to an unambiguous determination of the Chebyshev projection. The algorithm is based on finding relatively interior points of optimal solutions to a finite sequence of linear programming problems with lexicographically ordered objective functions. It is proved that the set of Chebyshev projections (produced by the presented algorithm) coincides with the set of Euclidean projections. This statement allows us to extend the previously proved properties of Euclidean projections to the set of Chebyshev projections, including the established facts of boundedness and connectedness of the set of Euclidean projections. The proved statement about the coincidence of the sets of Euclidean and Chebyshev projections also confirms the correctness of the introduced definition of the Chebyshev projection by means of the lexicographic optimization algorithm.

Keywords: lexicographic optimization, linear manifold, Haar condition, Chebyshev and Euclidean norms, Chebyshev projections

Received June 3, 2020

Revised July 25, 2020

Accepted August 10, 2020

Funding Agency: This work was supported by the Russian Academy of Sciences (project no. 0279-2019-0003) and by the Russian Foundation for Basic Research (project no. 19-07-00322).

Valeriy Ivanovich Zorkaltsev, Dr. Tech. Sci., Prof., Limnological Institute SB RAS, Irkutsk, 664033 Russia, e-mail: zork@isem.irk.ru

Cite this article as: V.I. Zorkal’tsev. Chebyshev projections to a linear manifold, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 44–55.

[References -> on the "English" button bottom right]