Широкую известность и признание получил метод последовательного анализа вариантов («киевский веник»), разработанный В. С. Михалевичем и Н. З. Шором. Этот метод был использован для решения ряда важных всесоюзных народнохозяйственных задач: задачи оптимального проектирования продольных профилей железных дорог (БАМ), магистральных газопроводов, транспортных и электрических сетей, задачи оптимальной загрузки прокатных станов СССР и др.
В 60-х годах разработка методов недифференцируемой оптимизации обеспечила возможность решения сложных практических задач оптимизации на базе вычислительной техники того времени. Создание и исследование этих методов составили наиболее значительную часть творческого наследия Н. З. Шора.
Результаты Н. З. Шора по методам негладкой оптимизации можно разделить на три направления:
первое — методы обобщённого градиентного спуска (ОГС) (1962—1971), которые положили начало новому направлению математического программирования — численным методам негладкой оптимизации;
второе — субградиентные методы с растяжением пространства в направлении субградиента, которые по сравнению с методами ОГС имеют ускоренную сходимость. Частным случаем этого семейства алгоритмов является метод эллипсоидов, скорость сходимости которого зависит лишь от размерности пространства. Использование метода эллипсоидов позволило решить ряд важных вопросов в теории сложности задач математического программирования;
третье направление — это субградиентные методы с растяжением пространства в направлении разности двух последовательных субградиентов, так называемые r-алгоритмы. До настоящего времени r-алгоритмы являются одним из наиболее эффективных средств решения задач недифференцируемой оптимизации. При минимизации гладких функций они конкурентоспособны с наиболее удачными реализациями методов сопряжённых направлений и методов квазиньютоновского типа.
Большое значение имеют работы Н. З. Шора, связанные с применением методов недифференцируемой оптимизации для получения двойственных лагранжевых оценок в многоэкстремальных квадратичных задачах. Для улучшения этих оценок используется расширение исходных квадратичных постановок задач путём добавления к ним функционально избыточных ограничений. Получение оценок очень важно для дискретных, NP-трудных экстремальных задач на графах и др. Такой подход даёт возможность среди NP-трудных невыпуклых квадратичных задач выделить такие подклассы, для которых проблема нахождения значения глобального минимума целевой функции разрешима за полиномиальное время.
Проблема точности двойственной оценки для определённой квадратичной задачи, соответствующей задаче нахождения глобального минимума полинома, оказалась тесно связана с исследованиями Гильберта о представлении неотрицательных полиномов в виде суммы квадратов полиномов меньших степеней (так называемая 17-я проблема Гильберта). Наиболее полная по материалам этой тематики монография Н. З. Шора вышла за рубежом на английском языке.
Михалевич В.С., Шор Н.З., Галустова Л.А. Вычислительные методы выбора оптимальных проектных решений. — Киев: Наукова думка, 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.
Примечания
↑Шор Наум Зуселевич(укр.). Национальная академия наук Украины. Дата обращения: 12 февраля 2011. Архивировано из оригинала 20 июня 2008 года.
