РАЗВИТИЕ АЛГОРИТМОВ НЕДИФФЕРЕНЦИРУЕМОЙ ОПТИМИЗАЦИИ И ИХ ПРИЛОЖЕНИЯ

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

Отсутствие эффективных методов негладкой оптимизации затрудняло решение указанных классов задач и заставляло либо изменять постановку задачи в ущерб адекватности модели, либо использовать различные приемы сглаживания. Последнее не всегда приводит к успеху, так как применение сглаживающих функций вызывает плохую обусловленность минимизируемой функции, что ухудшает вычислительную устойчивость таких эффективных методов гладкой минимизации, как квазиньютоновские и методы сопряженных градиентов. Таким образом, область приложений методов негладкой оптимизации весьма широка. Методы негладкой оптимизации оказались вполне конкурентоспособными как по надежности, так и по времени счета и точности результатов с наиболее эффективными методами решения гладких плохо обусловленных задач.

Цель нашего обзора - дать краткое описание разработанных в Институте кибернетики методов недифференцируемой оптимизации и показать их многочисленные приложения. В обзор включены следующие методы субградиентного типа: обобщенный градиентный спуск; методы субградиентного типа с растяжением пространства в направлении субградиента; r-алгоритмы, являющиеся мощным практическим средством решения задач недифференцируемой оптимизации.

Виктор Михайлович Глушков придавал большое значение исследованиям методов негладкой оптимизации. На самом высоком правительственном уровне он способствовал внедрению этих результатов в различных областях народного хозяйства. (В частности, он уделял большое внимание созданию системы автоматизированного планирования производства и распределения заказов в черной металлургии.)

В Институте кибернетики, начиная с 1962 года, были разработаны несколько вариантов ОГС. Эти результаты получены в период с 1962 по 1968 год и наиболее полно отражены в монографии [2], материал которой составила докторская диссертация Н.З.Шора 1970 года.

Регулировка шага была использована в методе ОГС, который был предложен в 1962 году в связи с решением транспортной задачи в сетевой форме [1]. Работа [1] была первым примером использования субградиентного процесса для минимизации выпуклых недифференцируемых функций.

Методы ОГС дали возможность решить большое число задач производственно-транспортного планирования с применением схем декомпозиции для задач большой размерности. Подробную информацию об этих задачах можно найти в [3]. Метод ОГС также послужил основой для создания стохастического аналога обобщенного градиентного спуска [4], который имеет большое практическое применение, в частности, при решении многоэтапных задач стохастического программирования. В [3] описано применение метода обобщенного стохастического градиента к решению двухэтапной стохастической транспортной задачи, связанной с определением объемов складов однородной продукции при случайном спросе.

Результаты по методам ОГС, полученные в Институте кибернетики, получили развитие в работах И.И.Еремина [5] и Б.Т.Поляка [6] для решения задач выпуклого программирования с ограничениями.

До 1974 года работы по ОГС были малоизвестны за рубежом, так как были опубликованы на русском языке в малодоступных изданиях. Они получили известность после публикации в [7] подробного обзора результатов и библиографии работ по недифференцируемой оптимизации, выполненных в СССР.

При анализе алгоритмов ОГС, сходящихся со скоростью геометрической прогрессии, существенную роль играли верхние границы синусов углов между направлением антиградиента в данной точке и направлением из нее на точку минимума. Медленная сходимость ОГС непреодолима в рамках этого метода в овражных задачах, когда верхняя граница указанных углов равна девяносто градусов.

Можно изменить ситуацию, используя линейные неортогональные преобразования пространства аргументов для улучшения обусловленности задачи. В случае когда антиградиенты образуют угол с направлением на точку минимума, близкий к , разумно применить операцию растяжения пространства в направлении градиента для уменьшения его "поперечной" составляющей. Эти эвристические соображения послужили основой создания семейства методов субградиентного типа с растяжением пространства. Операция растяжения пространства в направлении градиента первоначально введена Н.3.Шором [8, 9], [10] как эвристическая процедура для улучшения свойств обусловленности задачи.

При решении сложных задач недифференцируемой оптимизации средней размерности (до нескольких сот переменных) особенно эффективны оказались алгоритмы субградиентного типа с растяжением пространства в направлении разности двух последовательных субградиентов (r-алгоритмы). Они были предложены в 1971 году в работе [17].

По своей структуре и трудоемкости итерации r-алгоритмы близки к методам с растяжением пространства в направлении субградиента. Но между ними есть важное различие: методы ОГС с растяжением пространства в направлении субградиента в принципе не могут быть монотонными, в то же время r-алгоритмы при определенной регулировке шаговых множителей и коэффициентов растяжения пространства могут стать монотонными.

Алгоритмы недифференцируемой аппроксимации имеют широкую область практического применения. Приведем основные источники, порождающие задачи негладкой оптимизации.

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

Во-вторых, это задачи минимизации функции максимума.

Третий источник негладких задач - это лагранжевы оценки в задачах математического программирования.

Четвертый источник - это задачи минимизации функции максимума, характерные для моделей игрового характера, "многокритериальных" моделей оптимального планирования и исследования операций. К такого рода задачам сводятся задачи решения систем уравнений и неравенств, определения коэффициентов нелинейной регрессии, когда в качестве критерия используется чебышевский критерий минимизации максимума невязки (модуля невязки).

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

Шестой источник - это задачи оптимального управления с непрерывным и дискретным временем. Использование принципа максимума или дискретного принципа максимума во многих случаях приводит к задачам минимизации функций с разрывным градиентом. Эти задачи можно рассматривать как специальные задачи нелинейного программирования, для решения которых применимы схемы декомпозиции или метод негладких штрафных функций.

Седьмой источник задач - это задачи дискретного программирования или задачи смешанного дискретно-непрерывного типа. Многие задачи такого рода достаточно успешно могут решаться с использованием метода ветвей и границ с получением оценок путем решения двойственной задачи. Двойственная задача обычно оказывается задачей минимизации выпуклой кусочно-линейной функции с огромным числом "кус И наконец, функции с разрывным градиентом могут непосредственно входить в модель задачи оптимального планирования, проектирования или исследования операций как результат кусочно-гладкой аппроксимации технико-экономических характеристик реальных объектов.

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

Многочисленные приложения алгоритмов негладкой оптимизации для указанных классов задач можно найти в монографиях Н.З.Шора [2], [3], [21], [22].

Н.З.ШОР, Н.Г.ЖУРБЕНКО, А.П.ЛИХОВИД, П.И.СТЕЦЮК

Литература

1. Шор Н.З. Применение метода градиентного спуска для решения сетевой транспортной задачи. - В кн.: Материалы на науч. семинара по теорет. и прикл. вопр. кибернетики и исследования операций: Науч. совет по кибернетике АН УССР. Киев, 1962, вып. 1, С. 9-17.
2. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. - Киев: Наукова думка, 1979. - 199с.
3. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. Модели, методы, алгоритмы. // - М.: Наука, - 1986. - 260с.
4. Ермольев Ю.М., Шор Н.З. Метод случайного поиска для задач двухэтапного стохастического программирования и его обобщение. - Кибернетика, 1968, №1. - С. 90-92.
5. Еремин И.И. О методе "штрафов" в выпуклом программировании. - Кибернетика, 1966, №4. - С. 63-67.
6. Поляк Б.Т. Один общий метод решения екстремальных задач. - Докл. АН СССР, 1967, 174, №1. - С.33-36.
7. Balinski M.L., Wolfe P. (eds). Nondifferentiable optimization. Math. Programming Study, 3. - North-Holland, Amsterdam, 1975. - 178 p.
8. Шор Н.З., Билецкий В.И. Метод растяжения пространства для ускорения сходимости в задачах овражного типа. - В кн. Тр. семинара Науч. совета АН УССР по кибернетике "Теория оптимальных решений", Киев, 1969, №2. - С. 3-18.
9. Шор Н.З. Использование операций растяжения пространства в задачах минимизации выпуклых функций // Кибернетика. - 1970. - №1. - С. 6-12.
10. Шор Н.З. О скорости сходимости обобщенного градиентного спуска с растяжением пространства // Кибернетика. - 1970. - №2. - С. 80-85.
11. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач // Экономика и мат. методы. - 1976. - Вып.2. - C. 357-359.
12. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования // Кибернетика. - 1977. - №1. - С. 94-95.
13. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ДАН СССР. - 1979. - Т.244, №5. - C.1093-1096.
14. Grotschel M., Lovasz L., Schrijver A. Geometric Algorithms and Combinatorial Optimization. - Springer-Verlag, Berlin. - 1988. - 362 p.
15. Bachem A., Grotschel M., Korte B. (eds). Mathematical Programming: The State of Art, Bonn, 1982. - Springer-Verlag. 1983. - 655 p.
16. Shor N.Z. Generalized gradient methods of nondifferentiable optimization employing space dilatation operations. - In [15], P. 501-529.
17. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов // Кибернетика. - 1971. - №3. - С. 51-59.
18. Журбенко Н.Г. Построение семейства методов сопряженных направлений на основе использования оператора растяжения пространства // Теория и приложения методов оптимизации. - Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1998. - С. 12-18.
19. Журбенко Н.Г. Квазиньютоновские алгоритмы минимизации на основе использования оператора растяжения пространства // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1999. - С. 45-50.
20. Шор Н.З. Монотонные модификации r-алгоритмов и их приложения // Кибернетика и систем. анализ. - 2002. - N6. - С. 74-95.
21. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. - Киев: Наукова думка, 1989. - 208с.
22. Shor, N.Z. Nondifferentiable Optimization and Polynomial Problems, // Kluwer Academic Publishers, Boston / Dordrecht / London. - 1998. - 412 p. .