Для современной математической теории систем, равно как и для любой другой развивающейся теории, характерны две основные взаимодополняющие тенденции — это, во-первых, обобщение фундаментальных результатов в рамках общей теории и, во-вторых, развитие ее конкретных разделов, многие из которых лежат на стыке этой теории с ранее сложившимися. Наряду с предметными разделами, составляющими основу математической теории систем, такими как теория автоматического регулирования, оптимального управления, теория конечных автоматов, весьма интенсивно развиваются инструментальные разделы, к числу которых в первую очередь следует отнести теорию оптимизации.
Базируя свой аппарат на классическом анализе, теория оптимизации возникла как самостоятельная теория в связи с развитием кибернетического подхода к изучению функционирования сложных объектов, т. е. в связи с исследованием целенаправленных систем. В настоящее время теория систем рассматривает общую задачу оптимизации как одно из основных универсальных средств описания систем самого широкого класса. При этом вопрос о том, описывать ли систему в виде преобразования входных воздействий на выходные величины, или же представлять ее как целенаправленную систему, «сводится лишь к вопросу интерпретации или эстетической оценки» L15].
Следует особо подчеркнуть тот факт, что универсальность оптимизации как инструментального средства исследования систем достигается за счет возможности достаточно широко варьировать понятием целевой функции. Конструируя последнюю не только в соответствии с содержательной интерпретацией целенаправленного функционирования исследуемого объекта, но и исходя из целей самого исследования, можно существенно расширить спектр взглядов на данный объект. Однако при этом оптимизационные задачи часто становятся вырожденными. Исследованию методов решения таких задач и посвящена данная работа.
Развитие методов решения вырожденных задач математического программирования происходило по двум основным направлениям.
Первое направление связано с решением задачи выпуклого программирования с негладкой целевой функцией. Начало этому направлению было положено работой Н. З. Шора предложившего для решения задачи безусловной минимизации негладкой выпуклой функции метод субградиентного спуска. Методу субградиентного спуска были посвящены и работы Б. Т. Поляка.
LU] и Ю. М. Ермольева [ г ], в которых предлагались другие способы нормировки направлений движения в этом методе и конкретизировались правила выбора шагового множителя. Б. Т. Поляк предложил также специальный способ выбора шага в методе субградиентного спуска Ш использующий информацию об оптимальном значении целевой функции. При таком способе выбора шага для этого метода удалось получить оценку скорости сходимости порядка «где VC — число итераций метода.
Другой отправной точкой для дальнейшего развития методов негладкой минимизации стала работа А. Ю. Левина Г 1, в которой был предложен метод центров тяжести. Независимо от А. Ю. Левина метод центров тяжести был предложен и Д.Ньюменом.
Этот метод представляет в основном теоретический интерес, так как в нем на каждой итерации необходимо отыскивать центр тяжести Пмерного многогранника / KL — размерность пространства/. Но теоретическая ценность метода центров тяжести очень высока — ведь для него удается доказать сходимость со скоростью геометрической прогресвии, знаменатель которой зависит лишь от размерности пространства .
Среда других работ, посвященных методам негладкой оптимизации, необходимо особо выделить цикл статей А. С. Немировского и Д. Б. Юдина /итоги этих исследований подведены в монографии.
ВД/, в которых получены результаты о предельно возможных скоростях сходимости для весьма общего семейства методов минимизации на различных классах задач. Так, например, оказалось, что никакой метод негладкой выпуклой оптимизации не может в общем случае сходиться быстрее, чем со скоростью порядка J Я/ / «^ < - абсолютная константа • При этом ни у какого метода оценка скорости сходимости, равномерная по размерности пространства TL, не может быть лучше, чет порядка Of/pp) «где ^ ~ 411 сло итераций метода. Интересно отметить, что такими скоростями сходимости, как было показано в J, обладают соответственно метод центров тяжести и метод субградиентного спуска. Таким образом, два исторически первых метода, разработанных для решения задачи негладкой оптимизации, оказались неулучшаемыми по своим скоростным характеристикам.
Проанализировав недостатки метода центров тяжести, Д. Б. Юдин и А. С. Немировский предложили его модификацию — метод эллипсоидов, Однако платой за простоту каждой итерации в этом методе оказалось снижение скорости сходимости — метод эллипсоидов сходится со скоростью порядка О (О^), которая хуже оптимальной. Тем не менее, появление метода эллипсоидов вызвало в среде олтимизаторов большой резонанс, особенно после работы Л. Г. Хачияна Jf ис пользовавшего вдеи этого метода для конструктивного доказательства полиномиальной сложности задачи линейного программирования.
К методу эллипсоидов независимо пришел и Н. З. Шор {.ЪН 1, с именем которого связана интенсивная разработка методов растяжения пространства (см. [ as — 3SL ]). Оказалось, что метод эллипсоидов можно интерпретировать как метод растяжения пространства в направлении субградиента. Различные модификации метода эллипсоидов были предложены В. И. Гершовичем С Я.-4 ]. Методу эллипсоидов посвящены и многочисленные работы зарубежных авторов /см., например, Среди других методов растяжения пространства следует особо отметить так называемыйалгоритм [3 4−1, в котором используется операция растяжения пространства в направлении разности двух последовательных субграциентов. На практике этот метод обеспечивает такую же скорость сходимости, как и метод центров тяжести. К сожалению, теоретически обосновать скорость сходимостиалгоритма пока не удалось.
Для большинства из упоминавшихся методов теоретическое обоснование было проведено лишь для задачи минимизации выпуклой негладкой функции. Однако в связи с результатами о существенной неулучшаемости этих методов представляет интерес попытаться расширить их область применения. С другой стороны, для эффективного использования этих методов на практике, необходимо иметь четкое представление о том, как меняется скорость сходимости методов негладкой оптимизации при изменении различных свойств целевой функции, в частности, ее гладкости. Этим вопросам и посвящена первая глава настоящей работы. В ней предлагается некий общий подход к обоснованию скорости сходимости методов негладкой оптимизации, позволяющий охватить широкий класс задач — от негладких квазивыпуклых до гладких выпуклых. При этом сам способ доказательства оценок скорости сходимости каждого метода не зависит от свойств конкретной целевой функции. Окончательная оценка скорости сходимости метода получается с помощью мажоранты роста целевой функции и некоторой вспомогательной числовой последовательности, на скорость стремления к нулю которой свойства конкретной целевой функции не оказывают никакого влияния. С помощью предложенного подхода удается улучшить некоторые известные ранее оценки скорости сходимости методов негладкой минимизации. Основные результаты этой главы опубликованы автором в.
Вторая глава диссертационной работы посвящена методам решения выпуклых экстремальных задач, образованных гладкими компонентами.
Другое направление математического программирования — методы минимизации гладких функций — до последнего времени имело вполне законченный вид. Ясное представление о достижениях этого направления можно получить по работам Ю. И. Любича, Ф. Д. Майстровского Е.Г.Левитина, Б. Т. Поляка С ±2, ], монографиям В. Г. Карманова1Л 0 ], Б. Н. Пшеничного, Ю. М. Данилина t w ], Ф. П. Васильева с i 1. В.ф.Демьянова, А. М. Рубинова [ в ] ю.Г.ЕвтушенкоL^ 3.
Основным свойством всех методов гладкой выпуклой минимизации, с помощью которого удавалось доказывать глобальные оценки скорости сходимости, было свойство релаксационности минимизирующей последовательности. При этом оценки скорости сходимости методов выводились из неравенств, связывающих убывание целевой функции на итерации с разностью между текущим значением целевой функции и оптимальным значением. Без предположения о сильной выпуклости целевой функции такой подход позволял получать оценки скорости сходимости порядка D (ir), где К — число итераций метода.
Однако, А. С. Немировский и Д. Б. Юдин показали [16 ], что неулучшаемая оценка скорости сходимости методов решения задач такого типа имеет порядок 0(~j^r) • При этом, если для методов негладкой минимизации оптимальные методы удалось найти среди уже существующих, то для методов гладкой минимизации этого не произошло. Более того, оказалось, что ни метод градиентного спуска /с любым правилом выбора шага/, ни метод сопряженных градиентов /наиболее распространенные версии/," ни методы переменной метрики оптимальной скоростью сходимости вообще говоря не обладают — в построены соответствующие примеры. В связи с этим встал вопрос о построении метода гладкой выпуклой минимизации, обладающего скоростью сходимости порядка ОШ. Отметим, что важность этого вопроса не снижается существованием методов, обеспечивающих при минимизации произвольных выпуклых функций сходимость со скоростью геометрической прогрессии. Дело в том, что знаменатель геометрической прогрессии у таких методов зависит от размерности пространства.
П. Например, у метода центров тяжести он равен.
Поэтому при достаточно высокой размерности пространства методы со скоростью сходимости порядка будут обладать преимуществом перед методом центров тяжести. Так, для П. = 100 за тысячу итераций метод центров тяжести обеспечит погрешность по функции вообще говоря порядка.
Первые методы со скоростью сходимости порядка О (^) были предложены А. С. Немировским и Д. Б. Юдиным в работах [".за]. Однако, в практическом отношении эти методы имели некоторый дефект — на каждой итерации в них надо было с большой точностью решать вспомогательную задачу двумерной /вЦЗ?-]/ и одномерной /в13>$]/ минимизации.
Бо второй главе настоящей работы строятся методы решения задачи гладкого выпуклого программирования, обладающие скоростью сходимости порядка и не требующие во время работы решения вспомогательных задач минимизации целевой функции на подпространствах. Отметим, что предложенные методы вообще говоря не являются релаксационными. Кроме того, в рамках описываемых ниже схем можно строить методы с минимальной трудоемкостью каждой итерации — такие, что на каждой итерации вычисляется один градиент целевой функции и, в среднем, два ее значения.
Одним из достоинств предлагаемых методов является то, что их оценки скорости сходимости не зависят от размерности пространства.
Этот факт в сочетании с высокой скоростью сходимости и малой тру-доемкостноитерадии у этих методов свидетельствует о важности полученных результатов как с теоретической так и с практической точек зрения. Основные результаты второй главы опубликованы в [^ЗДО ]е.
Остановимся кратко на содержании работы.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ.
1. Предложен общий подход к установлению оценок скорости сходимости методов решения задачи математического программирования с, вообще говоря, негладкой квазивыпуклой целевой функцией. С помощью этого подхода можно получать оценки скорости сходимости исследуемых методов на различных классах целевых функций, не проводя при этом дополнительных доказательств.
2. Предложенный подход использован для вывода оценок скорости сходимости следующих методов: метода субградиентного спуска, метода центров тяжести, метода эллипсоидов /различные версии/, метода растяжения пространства в направлении субградиента.
3. Разработана общая схема методов отсечений, позволившая свя.
Q YU зать скорость убывания объемов некоторых специальных тел в ГЬ, локализующих точку минимума, со скоростью стремления к нулю вспомогательной числовой последовательности i^vt^ic^o •.
4. Предложен новый способ выбора шагового множителя в методе субградиентного спуска, использующий дополнительную информацию о целевой функции.
5. Улучшена известная ранее оценка скорости сходимости метода растяжения пространства в направлении субградиента.
6. Разработана общая схема получения эффективных методов решения гладких выпуклых задач безусловной минимизации. Оценка скорости сходимости таких методов не зависит от размерности пространства и имеет порядок О (^) «где 1С — число итераций.
7. В рамках предложенной схемы получены методы, оценка трудоемкости которых неулучшаема на рассмотренном классе задач. Таким образом, решена проблема построения оптимального алгоритма для решения задачи минимизации выпуклой функции с липшицевым градиентом.
8. Исследована устойчивость предложенной схемы относительно погрешности вычисления градиента целевой функции. Оценено влияние этой погрешности на скорость сходимости методов. Предложен метод безусловной минимизации, учитывающий при работе степень неточности вычисления градиента.
9. Разработана общая схема получения методов минимизации вообще говоря негладких функций, составленных из гладких выпуклых функций, Скорость сходимости таких методов — порядка 0[ у^х) -существенно превосходит скорость сходимости методов, предназначенных для минимизации негладких функций общего вида. Во многих практически важных частных случаях вспомогательная задача, которую в предложенных методах надо решать на каждой итерации, сводится к стандартной задаче квадратичного программирования.
10.Предложены методы решения гладких выпуклых задач условной минимизации, также обладающие скоростью сходимости порядка 0(fib) .
11.Проведена классификация особенностей целевых функций, влияющих на эффективность методов безусловной минимизации. Построен набор тестовых функций переменной размерности, моделирующих различные неприятные ситуации, с которыми может столкнуться метод при решении произвольной нелинейной задачи. Характер и степень проявления особенностей у этих функций можно изменять с помощью соответствующих параметров.
12.Проведено численное сравнении алгоритмической версии одного из методов, предложенного в § I главы II, со стандартной программой метода сопряженных градиентов Полака-Рибьера. Анализ результатов решения 50 выпуклых нелинейных задач различной размерности показал преимущество нового метода.