Разработка и исследование методов решения вырожденных задач оптимизации

• Автор: Нестеров, Юрий Евгеньевич
• Шифр специальности: 05.13.02
• Научная степень: Докторская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 106 c. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

Глава I. Исследование скорости сходимости методов

решения негладких вырожденных задач. II

I. Постановка задачи. Вспомогательные результаты.II

2. Субградиентный метод.

3. Методы отсечений. Общая схема

4. Метод центров тяжести.

5. Метод эллипсоидов

6. Метод растяжения пространства.

ВЫВОДЫ.
Глава II. Методы решения вырожденных задач минимизации,
образованных гладкиш выпуклыми функциями
I. Методы решения задачи безусловной минимизации гладкой
выпуклой функции
2. Методы минимизации составной функции
3. Методы решения задач с ограничениями
ВЫВОДЫ.
Глава III. Численная проверка алгоритмов
минимизации.
I. Построение тестовых функций
2. Результаты сравнения алгоритмов
ВЫВОДЫ.3
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.3
ЛИТЕРАТУРА


На практике этот метод обеспечивает такую же скорость сходимости, как и метод центров тяжести. К сожалению, теоретически обосновать скорость сходимости -алгоритма пока не удалось. Для большинства из упоминавшихся методов теоретическое обоснование было проведено лишь для задачи минимизации выпуклой негладкой функции. Однако в связи с результатами о существенной неулучшаемости этих методов представляет интерес попытаться расширить их область применения. С другой стороны, для эффективного использования этих методов на практике, необходимо иметь четкое представление о том, как меняется скорость сходимости методов негладкой оптимизации при изменении различных свойств целевой функции, в частности, ее гладкости. Этим вопросам и посвящена первая глава настоящей работы. В ней предлагается некий общий подход к обоснованию скорости сходимости методов негладкой оптимизации, позволяющий охватить широкий класс задач - от негладких квазивыпук-лых до гладких выпуклых. При этом сам способ доказательства оценок скорости сходимости каждого метода не зависит от свойств конкретной целевой функции. Окончательная оценка скорости сходимости метода получается с помощью мажоранты роста целевой функции и некоторой вспомогательной числовой последовательности, на скорость стремления к нулю которой свойства конкретной целевой функции не оказывают никакого влияния. С помощью предложенного подхода удается улучшить некоторые известные ранее оценки скорости сходимости методов негладкой минимизации. Вторая глава диссертационной работы посвящена методам решения выпуклых экстремальных задач, образованных гладкими компонентами. Другое направление математического программирования - методы минимизации гладких функций — до последнего времени имело вполне законченный вид. Ясное представление о достижениях этого направления можно получить по работам Ю. И.Любича, Ф. Д.Майстровского [lH], Е. Г,Левитина, Б. Т.Поляка [ li ], монографиям В. Г,КармановаГЛ0], Б. Н,Пшеничного, Ю. М.Данилина L № 1 , Ф. В. Ф. Демьянова, А. М.Рубинова [ 6 1 ^ Ю. Г, Евтушенко L? Основным свойством всех методов гладкой выпуклой минимизации, с помощью которого удавалось доказывать глобальные оценки скорости сходимости, было свойство релаксационности минимизирующей последовательности, При этом оценки скорости сходимости методов выводились из неравенств, связывающих убывание целевой функции на итерации с разностью между текущим значением целевой функции и оптимальным значением. Без предположения о сильной выпуклости целевой функции такой подход позволял получать оценки скорости сходимости порядка 0(~иг) , где VC - число итераций метода. Одаако, А. С.Немировский и Д. Б.Юдин показали Cle 1 , что неулучшаемая оценка скорости сходимости методов решения задач такого типа имеет порядок Ofjci) • При этом, если для методов негладкой минимизации оптимальные методы удалось найти среди уже существующих, то для методов гладкой минимизации этого не произошло. СЛу? Ли*/ . Отметим, что важность этого вопроса не снижается существованием методов, обеспечивающих при минимизации произвольных выпуклых функции сходимость со скоростью геометрической прогрессии. Дело в том, что знаменатель геометрической прогрессии у таких методов зависит от размерности пространства П . Например, у метода центров тяжести он равен (1~5) Поэтому при достаточно высокой размерности пространства методы со скоростью сходимости порядка 0(~^т) будут обладать преимуществом перед методом центров тяжести. Так, для П, = 0 за тысячу итераций метод центров тяжести обеспечит погрешность по функции вообще говоря порядка 4. Первые методы со скоростью сходимости порядка 0{? А.С. Немировским и Д. Г *]/ и одномерной /в 1. Отметин, что предложенные методы вообще говоря не являются релаксационными. Кроме того, в рамках описываемых ниже схем можно строить методы с минимальной трудоемкостью каждой итерации - такие что на каждой итерации вычисляется один градиент целевой функции и, в среднем, два ее значения. Одним из достоинств предлагаемых методов является то, что их оценки скорости сходимости не зависят от размерности пространства.