Наум Зуселевич Шор

Наум Зуселевич Шор

Дата рождения

1 января 1937 года

Место рождения

Киев, СССР

Дата смерти

25 февраля 2006 года

Место смерти

Киев, Украина

Награды и премии

Наум Зуселевич Шор (укр. Наум Зуселевич Шор) — советский и украинский математик и кибернетик, основатель направления недифференцируемой оптимизации в математическом программировании, академик Национальной академии наук Украины, доктор физико-математических наук, профессор, член Международного общества математического программирования.

Карьера

Наум Шор родился 1 января 1937 года в Киеве.

В 1958 году окончил механико-математический факультет Киевского национального университета имени Тараса Шевченко. В период учёбы занимался научной работой по проблемам дифференциальной алгебры под руководством В. М. Глушкова.

С 1958 года — инженер в Институте кибернетики АН Украинской ССР (Вычислительный центр АН Украинской ССР), где проработал всю жизнь (с 1983 года — заведующий основанного им отдела методов негладкой оптимизации, с 1990 года — заведующий отделом «Методы решения сложных задач оптимизации»). Таким образом, вся профессиональная жизнь Шора прошла в Институте кибернетики имени В.М. Глушкова.

В 1961 году предложил метод обобщенного градиентного спуска, который положил начало новому научному направлению в области математического программирования — численным методам негладкой (недифференцируемой) оптимизации.

9 апреля 1963 года женился на Елене Шор, с которой имел двоих детей, Евгению и Станислава.

В 1960-е годы разработка методов недифференцируемой оптимизации обеспечила возможность решения сложных практических задач оптимизации на базе вычислительной техники того времени. Создание и исследование этих методов составили наиболее значительную часть достижений Шора.

В 1964 году — кандидат физико-математических наук.

В 1970 году — доктор физико-математических наук.

В 1973 году — лауреат Государственной премии Украинской ССР.

В 1981 году — лауреат Государственной премии СССР.

В 1987 году — лауреат премии им. В.М. Глушкова НАН Украины, а в 1997 году — премии им.В.С. Михалевича НАН Украины.

В 1989 году — профессор (Шор преподавал в Киевском отделении МФТИ, Киевском политехническом институте, Киевском университете имени Тараса Шевченка и Международном Соломоновом университете).

В 1990 году был избран членом-корреспондентом АН Украинской ССР.

В 1993 году — лауреат Государственной премии Украины.

4 декабря 1997 года — академик Национальной академии наук Украины.

В 2000 году — лауреат Государственной премии Украины.

Автор свыше 200 научных работ, включая 10 монографий.

Области исследований: нелинейное и стохастическое программирование, субградиентные методы оптимизации, теория оптимальных решений в области планирования и проектирования. Тем самым, научные интересы Шора были связаны с теорией и численными методами оптимизации (последовательной оптимизацией, недифференцируемой оптимизацией, нелинейной и стохастической оптимизации, дискретными и матричными задачами оптимизации) и смежными областями математики.

Известность получил метод последовательного анализа вариантов («киевский веник»), разработанный В.С. Михалевичем и Н.З. Шором. Данный метод был использован для решения ряда важных всесоюзных народнохозяйственных задач: задачи оптимального проектирования продольных профилей железных дорог (БАМ), магистральных газопроводов, транспортных и электрических сетей, задачи оптимальной загрузки прокатных станов Советском Союзе и т. д.

Результаты учёного по методам негладкой оптимизации можно разделить на три направления:

• первое – методы обобщенного градиентного спуска (ОГС) (1962–1971), которые положили начало новому направлению математического программирования – численным методам негладкой оптимизации;
• второе – субградиентные методы с растяжением пространства в направлении субградиента, которые по сравнению с методами ОГС имеют ускоренную сходимость. Частным случаем этого семейства алгоритмов является метод эллипсоидов, скорость сходимости которого зависит лишь от размерности пространства. Использование метода эллипсоидов позволило решить ряд важных вопросов в теории сложности задач математического программирования;
• третье направление – это субградиентные методы с растяжением пространства в направлении разности двух последовательных субградиентов, так называемые r-алгоритмы. До настоящего времени r-алгоритмы являются одним из наиболее эффективных средств решения задач недифференцируемой оптимизации. При минимизации гладких функций они конкурентоспособны с наиболее удачными реализациями методов сопряженных направлений и методов квазиньютоновского типа.

Важное значение имеют работы Шора, связанные с применением методов недифференцируемой оптимизации для получения двойственных лагранжевых оценок в многоэкстремальных квадратичных задачах. Для улучшения этих оценок используется расширение исходных квадратичных постановок задач путём добавления к ним функционально избыточных ограничений. Получение оценок очень важно для дискретных, NP-трудных экстремальных задач на графах и др. Такой подход дает возможность среди NP-трудных невыпуклых квадратичных задач выделить такие подклассы, для которых проблема нахождения значения глобального минимума целевой функции разрешима за полиномиальное время.

Проблема точности двойственной оценки для определенной квадратичной задачи, соответствующей задаче нахождения глобального минимума полинома, оказалась тесно связана с исследованиями Гильберта о представлении неотрицательных полиномов в виде суммы квадратов полиномов меньших степеней (17-я проблема Гильберта).

Умер 25 февраля 2006 года в Киеве.

Труды

• Михалевич В.С., Шор Н.З., Галустова Л.А. Вычислительные методы выбора оптимальных проектных решений. — К.: Наукова думка, 1977. — 178 с.
• Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. — К.: Наукова думка, 1979. — 199 с.
• Shor N.Z. Minimization Methods for Non-Differentiable Functions. — Berlin: Springer-Verlag, 1985. — 178 с.
• Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. Модели, методы, алгоритмы. — М.: Наука, 1986. — 260 с.
• Шор Н.З., Соломон Д.И. Декомпозиционные методы в дробно-линейном программировании. — Кишинев: Штиинца, 1989. — 204 с.
• Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. — К.: Наукова думка, 1989. — 208 с.
• Shor N.Z. Nondifferentiable optimization and polynomial problems. — Boston; Dordrecht; London: Kluwer Academic Publishers, 1998. — 394 с.
• Шор Н.З., Сергієнко І.В. та ін. Задачі оптимального проектування надійних мереж. — К.: Наукова думка, 2005. — 230 с.
• Бакаєв О.О., Брановицька С.В., Міхалевич В.С., Шор Н.З. Визначення характеристик транспортної сітки методом послідовного аналізу варіантів // Доповіді Академії наук УРСР. — 1962. — № 4.
• Галустова Л.А., Шор Н.З. Определение наивыгоднейшего варианта сети 35-10 кв с проверкой на минимальный режим // Кибернетика и техника вычислений. — К.: Наукова думка, 1964. — С. 144—147.
• Ермольев Ю.М., Шор Н.З. Метод случайного поиска для задач двухэтапного стохастического программирования и его обобщение // Кибернетика. — 1968. — № 1. — С. 90—92.
• Шор Н.З. Использование операций растяжения пространства в задачах минимизации выпуклых функций // Кибернетика. — 1970. — № 1. — С. 6—12.
• Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов // Кибернетика. — 1971. — № 3. — С. 51—59.
• Шор Н.З., Гамбурд П.Р. Некоторые вопросы сходимости обобщенного градиентного спуска // Кибернетика. — 1971. — № 6. — С. 82—84.
• Шор Н.З., Галустова Л.А., Момот А.И. Применение математических методов при оптимальном проектировании единой газоснабжающей системы с учетом динамики её развития // Кибернетика. — 1978. — № 1. — С. 69—74.
• Беляева Л.В., Билецкий В.И., Шор Н.З. О декомпозиционном алгоритме выбора оптимального профиля железной дороги // Кибернетика. — 1983. — № 3. — С. 76—79.
• Шор Н.З., Бардадым Т.А., Журбенко Н.Г., Стецюк П.И., Лиховид А.П. Использование методов негладкой оптимизации в задачах стохастического программирования // Кибернетика и системный анализ. — 1999. — № 5. — С. 33—47.
• Shor N.Z., Setstyuk P.I. Lagrangian bounds n multiextremal polynomial and discrete optimization problems // Journal of Global Optimization. — 2002. — № 23. — С. 1—41.