автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.02, диссертация на тему:Разработка и исследование методов решения вырожденных задач оптимизации

ВВЕДЕНИЕ.

Глава I. Исследование скорости сходимости методов решения негладких вырожденных задач. II

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

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

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

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

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

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

ВЫВОДЫ.

Глава II. Методы решения вырожденных задач минимизации, образованных гладкими выпуклыми функциями.

§ I. Методы решения задачи безусловной минимизации гладкой выпуклой функции.

§ 2. Методы минимизации составной функции.

§ 3. Методы решения задач с ограничениями.

ВЫВОДЫ.

Глава III. Численная проверка алгоритмов минимизации.

§ I. Построение тестовых функций.

§ 2. Результаты сравнения алгоритмов.

ВЫВОДЫ.ЪЯ

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

Базируя свой аппарат на классическом анализе, теория оптимизации возникла как самостоятельная теория в связи с развитием кибернетического подхода к изучению функционирования сложных объектов, т.е. в связи с исследованием целенаправленных систем. В настоящее время теория систем рассматривает общую задачу оптимизации как одно из основных универсальных средств описания систем самого широкого класса. При этом вопрос о том, описывать ли систему в виде преобразования входных воздействий на выходные величины, или же представлять ее как целенаправленную систему, "сводится лишь к вопросу интерпретации или эстетической оценки" 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 за тысячу итераций метод центров тяжести обеспечит погрешность по функции вообще говоря порядка <LO f в то время как методы со скоростью сходимости - порядка 40 , ^

Первые методы со скоростью сходимости порядка О(^) были предложены А.С.Немировским и Д.Б.Юдиным в работах [«.за]. Однако, в практическом отношении эти методы имели некоторый дефект - на каждой итерации в них надо было с большой точностью решать вспомогательную задачу двумерной /вЦЗ?-]/ и одномерной /в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 выпуклых нелинейных задач различной размерности показал преимущество нового метода.

1. Васильев Ф.П. Численные методы решения экстремальных задач.-М.: Наука,1980,520с.

2. Гершович В.И. Об одном методе отсечений, использующем линейные преобразования пространства.-В кн.:Теория оптимальных решений. Киев,ИК АН УССР,1979,с.15*23.

3. Гершович В.И. Об одном алгоритме эллипсоидов.-В кн.О некоторых алгоритмах негладкой оптимизации и дискретного программировав ния.Препринт 81-6 Ж АН УССР,I981,с.8-13.

4. Грюнбаум Б. Этюды по комбинаторной геометрии и теории выпуклых тел.-М.: Наука,1971,96с.

5. Демьянов В.Ф., Рубинов A.M. Приближенные методы решения экстремальных задач.-Л.: Изд-во ЛГУ, 1968.

6. Евтушенко Ю.Г. Методы решения экстремальных эадач и их применение в системах оптимизации.-М.: Наука,1982,432с.

7. Ермольев Ю.М. Методы решения нелинейных экстремальных задач.-Кибернетика,1966,М,с.I-I7.

8. Ермольев Ю.М. Методы стохастического программирования.-М: Наука 1976,240с.

9. Карманов В.Г. Математическое программирование.-М.: Наука,1975, 272с.

10. Ким К.В., Нестеров Ю.Е., Скоков В.А., Черкасский Б.В. Эффективный алгоритм вычисления производных и экстремальные задачи.-Экономика и матем.методы,1984,т.ХХ,вып.2,с.342-351.

11. Левин А.Ю. Об одном алгоритме минимизации выпуклых функций.-Докл.АН СССР, 1965,т.160,$6, с. 1244-1247.

12. Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений .-Ж.вычисл.матем. и матем. физики,1966,т.6,№5,с.787-823.

13. Любич Ю.И., Майстровокий Г.Д. Общая теория релаксационных процессов для выпуклых функционалов.-Успехи матем.наук, 1970,Ж, с.57-112.

14. Месарович М., Такахара Я. Общая теория систем: математические основы.-М: Мир,1978,311с.

15. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации.-М.: Наука,1979,384с.

16. Нестеров Ю.Е., Скоков В.А. К вопросу о тестировании алгоритмов безусловной минимизации первого порядка.-В кн.: Численные методы математического программирования,-М.: Изд-во ЦЭМИ АН СССР,1980,с.77-91.

17. Нестеров Ю.Е. Методы минимизации негладких выпуклых и квазивыпуклых функций.'-Экономика ж матем. методы,1984,т.20,вып.3, с.519-531.

18. Нестеров Ю.Е. Общая схема получения методов безусловной минимизации гладких выпуклых функций, обладающих скоростью сходимости порядка кн.: Тезисы 2-й конференции по оптимальному планированию и управлению народным хозяйством.-М., I983,c.I08-II0.

19. Нестеров Ю.Е. Метод решения задачи выпуклого программирования со скоростью сходимости ()^г^.-Докл.АН СССР, 1983,т.269,№3, с.543-547.

20. Поляк Б.Т. Один общий метод решения экстремальных задач.-Докл.АН СССР,1967,т.174,Ж,с.33-36.

21. Поляк Б.Т. Минимизация негладких функционалов.-Ж.вычисл.матем. и матем,физики,1969,т,9,Ш, с.509-521,

22. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах.-М.: Наука,1975,319с.

23. Скоков Б,А. Замечание к методам минимизации, использующим операцию растяжения пространства.-Кибернетика,1974,М,с.II5-II7.

24. Хачиян Л,Г. Полиномиальный алгоритм в линейном программировании.-Докл. АН СС CP,1979,т.244,№5,с.1093-1096•

25. Химмельблау Д. Прикладное нелинейное программирование.-М.: Мир, 1975,530с.

26. Шор Н.З. Применение метода градиентного спуска для решения сетевой транспортной задачи.-В кн.: Материалы науч.семинара по теор. и прикл. вопросам кибернетики и исслед. операций: Науч. совет по кибернетике АН УССР, Киев,1962,вып.I,с.9-17.

27. Шор Н.З., Билецкий В.И. Метод растяжения пространства для ускорения сходимости в задачах овражного типа.-В кн.:Тр.семинара Науч.совета АН УССР по кибернетике"Теория оптим.решений",Киев 1969,№2,с.3-18.

28. Шор Н.З. О скорости сходимости метода обобщенного градиентного спуска с растяжением пространства.-Кибернетика,I970,№2,с.80-85

29. Шор Н.З. Использование операций растяжения пространства в задачах минимизации выпуклых функций.-Кибернетика,1970,ЖЕ,с.6-12.

30. Шор Н.З., Журбенко Н.Г, Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов.-Кибернетика,1971,Л8,с.51-59.

31. Шор.Н.З, Исследование сходимости метода градиентного типа с растяжением пространства в направлении разности двух последовательных градиентов.-Кибернетика,I975,№4,с.48-53.

32. Шор Н.З. Обобщенные градиентные методы минимизации негладкихфункций и их применение к задачам математического программирования.-Экономика и матем,методы,1976,т.12,вып.2,с.337-356.

33. Шор Н.З. Методы отсечения с растяжением пространства для решения яадач выпуклого программирования.-Кибернетика,1977,М,с.94-95.

34. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения.-Киев: Наукова думка,1979,200с.

35. Юдин Д.Б.,Немиррвским А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач.-Экономика и матеы. методы,1976,т.12,вып.2,с.357-369.

36. Юдин Д.Б.,Немировский А.С. Информационная сложность строго выпуклого программирования.-Экономика и матем.методы,1977,т.13, вып.З,с.550-559.

37. Юдин Д.Б., Не миров ский А. С. Информационная сложность математического программирования.-Изв.АН СССР,Техн.кибернетика,1983,ЖЕ, с.88-117.м. в&хпс( а.&. 5 Todd и. 3.1. The method: а -ьилтге^,

38. Teclmuiai fUpoit* Уо. Н76; School of Орегotion Че^гагск аhd Indubtliai Еп^ьпеегЫ^ 5 80; 55 р. ^б.й. KlicLcliiaviA a^LtW-. a comment, ШМ Шьг* > 138О, р. 1Л4 1. P. ? LoTra^z L. Югаск^ап.'Vа^огсИшт. Pumat рго^тт^^ yyioctln. Рго^тт'т^ 14, 13 81,p. SI

39. Ч*. &оЫ#м&Ъ.>ТоЛ<1 м.1 lUodificatlon^1.the ^коЪ

40. Kkacklcm aiyotiikm |ог tine atpzo^^ammLn-Cj } Tec.kvi.lea£ Report /14т96 Zckoot o| operation, ге-^еагскundubbtLbi еи^ьпеегиад, согпеРИ1. UnivenLty, l^SO.hb. GzotbcheB M.^Loira^? L ^ck^dj vet A.

41. The. eiiLpboL<k metWod avuA ■4гшлет:е<> иг сот.$1иА"Ьогса£ optmu

42. V. KonL^ И., l°a^ackfce Ъ, On Kkackian'i <кЫо%Ltkm and tfttipboi.d

43. Tlu m e г 14 c. ke Watkemaiik, 13 SI, u:36, W.2., P- Н1-Ш.l/e-urmaa^.^. Location o-fik* maximum. on un.i.moc<a£ -^иг^&се^., •1. ACM, 1965,p. т-ЗЭ*.

44. Чб. Огеп. X.S. Oia "Lke. леЕ&сЬсоп. of раъа-ПгеЬггь иг -icatonq гюл'ьa1. VrLet^.icd ШойЬк. PboQ fcavrwung , p. Z.l-23.41. frozen ock И.И. fln. auttmatU method |ог Itndlna, tWe <^eatevt <mc( lea^tvaEue o| a lunctLoiaj Computer 1, 3,1*60, р.ш-т.

45. ЯсЬ.гас1гг Я. tllipbold method*.

46. Report /Vo. 8117У-OK *titut |иг. oktmomei^ce uwd ореъatLon^

47. Spedocato E . On a conjecture of Ъьхсж cmc( otke^ topcci In. vaKiaMe v^ebtU wietkod&, Tflatk. Pro^mva^

48. Vo£|e P. a ШсО^рКу fo* the Cen.tet, do^ktoaan. W^klU >оък , U Ар'г. -13 80, 6 p.