Алгоритмическая выпуклая оптимизация

Нестеров, Юрий Евгеньевич

Алгоритмическая выпуклая оптимизация тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Нестеров, Юрий Евгеньевич АВТОР

доктора физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.07 КОД ВАК РФ

Диссертация по математике на тему «Алгоритмическая выпуклая оптимизация»

Автореферат диссертации на тему "Алгоритмическая выпуклая оптимизация"

На правах рукописи

Нестеров Юрий Евгеньевич

Алгоритмическая выпуклая оптимизация

7 НОЯ 2013

Специальность 01.01.07 - вычислительная математика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

МОСКВА - 2013

005537316

Работа выполнена в Лаборатории структурных методов анализа данных в предсказательном моделировании (ПреМоЛаб) Московского физико-технического института (государственного университета)

Официальные оппоненты: доктор физико-математических наук, профессс

академик РАН Евтушенко Юрий Гаврилов Вычислительный центр им. A.A. Дородницына РАН, директор

доктор физико-математических наук, профессор

Тихомиров Владимир Михайлович,

кафедра оптимального управления механико-математического факультета МГУ им. М.В.Ломоносова, профессор

доктор технических наук Горнов Александр Юрьевич,

лаборатория оптимального управления Института динамики систем и теории управле1 Сибирского отделения РАН, главный научный сотрудник

Ведущая организация: Институт проблем управления

им. В.А.Трапезникова РАН _ ^¡р

Защита состоится /у) Р час. на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (ГУ) по адресу: 141700, МО, г. Долгопрудный, Институтский пер. д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ). Автореферат разослан

11 <7 5" " Л^Р2013 г.

Ученый секретарь диссертационного совета Федько О.С.

Общая характеристика работы

Актуальность темы и степень ее разработанности

Настоящая диссертация посвящена разработке новых методов решения нелинейных выпуклых задач оптимизации. Теория методов оптимизации является одной из самых востребованных областей численного анализа. Наиболее продвинутая ее часть посвящена решению выпуклых задач. Эти постановки базируются на солидном математическом фундаменте, разработанном в основном в первой половине 20го столетия математиками Г.Минковским, К.Каратеодори, Э.Хелли, В.Фенхелем, А.Александровым и другими. Поначалу выпуклый анализ развивался независимо от теории экстремальных задач. Однако после основополагающей монографин Р.Т.Рокафеллара1, центр развития этой науки окончательно сместился в сторону теории оптимизации2. В настоящее время существует большое количество прекрасных книг как по выпуклому анализу, так и по его оптимизационным приложениям. Очень важно, что выпуклые задачи представляют собой практически единственный класс оптимизационных задач, допускающих построение методов с глобальными скоростными характеристиками, приемлемыми для большинства практических приложений. Это обстоятельство привело к появлению большого количества интересных методов и подходов. Основные приоритетные результаты в этой области принадлежат отечественным ученым А.Антипину, Ф.П.Васильеву, Е.Г.Гольштейну, В. Ф. Демьянову, Ю.Г.Евтушенко, Ю.М. Ермольеву, А.Д.Иоффе, В.Г.Карманову, Б.С.Мордуховичу, А.С.Немнровскому, Б.Т.Поляку, P.A.Поляку, Б.Н.Пшеничному, А.М.Рубинову, В.М.Тихомирову, Л.Г.Хачияну, Н.З.Шору, Д.В.Юдину, и другим. Результаты по теории сложности экстремальных задач могут рассматриваться как естественное развитие традиций, заложенных еще Л.В.Каиторовпчем3.

Однако, начиная с выдающейся работы Н.Кармаркара, опубликованной в 1985 г., и примерно до 2000 г. развитие теории и методов оптимизации

]Рокафеллар Р.Т. Выпуклый анализ. - М.: Мир, 1973 - 420с.

211оффе Л.Д.. Тихомиров В.М. Теория экстремальных задач. - М.: Наука, 1974 - 460с.

3Канторовнч Л.В. Функциональный аналих и прикладная математика / Успехи мат. наук - 1948. -Т.З, вын.1 - С.89-185.

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

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

Цели и задачи

4Ncsterov Yu., Nemirovskii A. Interior point polynomial methods in convex programming: Theory and Applications /7 Philadelphia: SIAM, 1994 - 520p.

что к 1985г. теория методов выпуклой оптимизации представляла собой цельный монолит5, завершенный в основном усилиями А.С.Немировского и Д.Б.Юдина. Разработанная ими теория сложности6, дающая верхние оценки на возможную эффективность методов минимизации для различных классов задач, была подкреплена оптимальными методами, которые эти оценки как раз и реализовывали. Предположения их вычислительной модели (оракул типа черный ящик) полностью соответствовали существовавшему тогда стилю написания оптимизационных пакетов программ, где пользователю предлагалось написать подпрограмму вычисления значения функции и градиента, закрытую для самого пакета7. Таким образом, в то время казалось что все важные вопросы в этой области были уже заданы и на (почти) все из них получены ответы.

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

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

Основной целыо настоящей диссертации является разработка более мощных и быстрых методов оптимизации, которые значительно расширяют

5Поляк Б.Т. Введение в оптимизацию. - М.: Наука, 1983.-433.

сНсмировский A.C., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. - М.: Паука, 1977. - 540с.

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

возможности, обрисованные в стандартной теории сложности.

Новизна, методология и методы исследования

Все приводимые ниже результаты являлись на момент их публикации новыми. Большинство из них было получено в 2002-2007 годах и опубликовано ближе к концу десятилетия в ведущих оптимизационных журналах. Все они связаны с разработкой новых методов оптимизации для различных классов выпуклых задач.

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

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

• Дикинский эллипсоид. Этот эллипсоид, определяемый гессианом самосогласованной функции, лежит в допустимой области.

• Аппроксимация 1го порядка. Для функции /(х), чей градиент удовлетворяет условию Липшица с константой Ь, можно написать следующую аппроксимацию:

/(у) < !{х) + (У}{х),у-х) + Щу-х\\2.

Минимизируя эту аппроксимацию на допустимом множестве, можно улучшить значение целевой функции.

• Аппроксимация 2го порядка. Для функции /(х), у которой гессиан является липшнцевым с константой , верна верхняя оценка

Ну) < Пх) + {УПх),у-х) + 1(ъ21(х)(у-х),у-х) + 1м\\у-х\\3.

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

• Верхняя аппроксимация для системы уравнений. Для уравнения Р(х) = 0, где отображение F : В!1 —> Дт имеет Липшицев якобиан VF с константой М, можно написать верхнюю оценку

\\р(У)\\ < тх)+ЪЕ{Х)(у-х)\\+1Л1\\у-хГ.

Минимизация этой оценки дает модифицированный метод Гаусса-Ньютона.

2. Алгебраические модели. В них описывается конкретный способ представления целевой функции. Для выпуклых функций естественной формой представления является максимум (дискретный или непрерывный) выпуклых функций. Например, может случиться, что нам известно следующее представление:

/(х) = тах{(Лх, и) — ф{и)}.

и&Ъ

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

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

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

моделей целевой функции (или их комбинаций). Мы приведем новые алгоритмы следующих типов.

• Прямо-двойственные субградиентные методы для решения негладких выпуклых задач (параграфы 3.1 и 3.2).

• Методы минимизации составных функций (параграф 3.3).

• Методы решения вариационных неравенств (Глава 4).

• Методы второго порядка (Глава 5).

• Алгоритмы техники сглаживания (Глава 6).

• Методы для нахождения решений выпуклых задач с относительной точностью (Глава 7).

Теоретическая и практическая значимость работы

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

• вычисление дополнительных характеристик решения (например, наряду с прямым решением аппроксимируется также и решение двойственной задачи или производится контроль точности решения);

• обладают гарантиями глобальной эффективности (например, новые методы второго порядка);

• сходятся быстрее, чем разрешает стандартная теория сложности (например, алгоритмы техники сглаживания).

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

Положения, выносимые на защиту

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

• Барьерный субградиентный метод. Позволяет минимизировать негладкие функции на множествах заданных самосогласованным барьером. Обладает оптимальной скоростью сходимости. Позволяет максимизировать положительные вогнутые функции с относительной точностью.

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

• Методы решения вариационных неравенств с гладким оператором. Обладают оптимальной скоростью сходимости. Являются двойственным аналогом экстраградиентного метода.

• Методы решения квазивариационных неравенств. Существенно расширен класс неравенств, обладающих единственным решением, и построен быстрый метод их решения.

• Кубическая регуляризация метода Ньютона. С помощью кубической верхней оценки целевой функции построен новый метод второго порядка. Метод работает и на невыпуклых функциях. На выпуклых задачах он сходится со скоростью 0(1/к2), где к - это счетчик итераций. Это первый метод второго порядка, обладающий такой скоростью сходимости на вырожденных выпуклых задачах.

• Ускоренный метод Ньютона. За счет использования небольшой памяти кубический метод Ньютона удается ускорить. Теперь он сходится как 0(1/к3).

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

• Сглаживание явной модели целевой функции. Для подходящей модели эта техника позволяет решать негладкие задачи с трудоемкостью 0( 1/е) итераций метода градиентного типа, где е - это требуемая точность решения. Тем самым преодолевается неулучшаемая оценка 0( 1/е2), справедливая для черноящичных методов.

• Условие обратного зазора. Методы, основанные на этой интерпретации, позволяют применять технику сглаживания к более широкому классу задач, в частности включающему сильно выпуклые функции. Это улучшает оценку трудоемкости до 0( 1 /е1|/2).

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

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

• Эллипсоидальная аппроксимация выпуклых тел используется для нахождения правильной евклидовой нормы, позволяющей существенно ускорить скорость сходимости методов оптимизации.

Публикации и апробация результатов

Результаты, включенные в данную работу, опубликованы в 19 статьях в ведущих отечественных и международных журналах (см. [1-6, 9-18, 20-22]). В работе также использовались фрагменты из монографий автора [7], [8] и русской версии [19]. В двух работах [11] и [20], написанных в соавторстве,

соискателю принадлежат результаты, указанные в положениях, выносимых на защиту данной диссертации.

Результаты, включенные в диссертацию, неоднократно докладывались на научных семинарах в ведущих университетах России и за рубежом: семинар кафедры Оптимальное Управление, МехМат МГУ, руководитель -профессор В.М.Тихомиров (апрель 2012); семинар лаборатории Адаптивных и робастных систем им. Я.З.Цыпкина, ИПУ РАН, руководитель -профессор Б.Т.Поляк (март 2011); семинар лаборатории ПреМоЛаб, МФТИ, руководитель - профессор В.Г.Спокойный (декабрь 2011, апрель 2012); семинар по оптимизации, Технологический Университет Джорджии (США), руководитель - профессор А.С.Немировский (апрели 2008 - 2012гг.); семинар по исследованию операций института IFOR (ETHZ, Zurich), руководитель -профессор H.-J.Luethi (март 2008, сентябрь 2011).

В качестве пленарных и приглашенных докладов, результаты автора докладывались на многочисленных международных конференциях:

International Conference on Operations Research, Цюрих, 2011;

International conference "Foundations of Computational Mathematics", Будашешт, 2011;

International Conference on Machine Leraning (NIPS), Ванкувер, 2010;

International Conference on Optimization and Applications (CIRM), Барселона, 2010;

International Workshop on Quadratic Optimization, Левен, 2010;

IPAM Workshop on Continuous Optimization, Лос Апжелес, 2010;

International Congress of Mathematicians, Хпдерабад, 2010;

International conference OPTIMA, Будва, 2009;

20th International Symposium on Mathematical Programming, Чикаго, 2009;

7th EUROPT Workshop on Operations Research, Реманген, 2009;

7th Brazilian Conference on Continuous Optimization, Кампинас, 2008;

International Conference on Optimization and Operations Research, Северобайкальск, 2008;

School "New Paradigms in Optimization", Аскона, 2008;

International conference "High Performance Optimization", Амстердам, 2008;

INFORMS meeting on Continuous Optimization, Атланта, 2008;

School on Continuous Optimization, Эйн Геди, 2007;

International Conference on Continuous and Discrete optimization, Ватерлоо, 2007;

International Conference on Nonlinear Optimization, Люмини, 2007; School on Operations Research and Optimization, Зиналь, 2007; International Workshop on Continuous Optimization VOCAL, Будапешт, 2006;

International Symposium on Mathematical Programming, Рио-де-Жанейро, 2006;

International Conference on Semidefinite Programming, Сингапур, 2006; Annual INFORMS meeting. Сан-Франциско, 2005; International conference on positive polynomials, Люмини, 2005; International Workshop on Nonlinear Optimization, Обервольфах, 2005; French-German-Spain conference on Operations Research, Авиньон, 2004; International conference "High Performance Optimization", Амстердам, 2004; International workshop on semidefinite programming, Ватерлоо, 2004.

На основе результатов диссертации подготовлены курсы лекций, которые были прочитаны в различных европейских университетах:

• Университет г.Льеж (Бельгия), 2012;

• Независимый московский университет, Москва, 2012;

• Ecole nationale de la statistique et de l'administration économique (Paris Tech), Париж (Франция), 2012;

• Университет г.Вены (Австрия), 2013;

• Традиционная Математическая Школа по Управлению и Оптимизации, Сенеж, Моск. обл., 2013.

Структура и объем работы

Диссертация состоит из введения, шести глав, заключения, и списка литературы. Полный объем составляет 367 страниц, список литературы содержит 125 наименований.

Основное содержание работы

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

Глава 1 является вводной и содержит всс необходимые вспомогательные результаты. В параграфе 1.1 вводятся различные классы выпуклых функций, ранжированные по степени гладкости и выпуклости. Доказываются полезные неравенства.

Параграф 1.2 начинается с рассмотрения базовых градиентных методов, прямого и двойственного, которые применяются к задаче

Найти /* = min f(x), (1.2.1)

xeQ

где Q - это выпуклое замкнутое ограниченное множество, и / Ç C^IQ). Обозначим через Tq{x) £ Q оптимальное решение следующей задачи минимизации:

mm {{Vf(x),y - х) + \L\\y - z||2 : у е Q} . (1.2.2)

В этой вспомогательной задаче норма может и не быть евклидовой.

Для описания простейших методов нам потребуется понятие брегмановской проекции. Обозначим через d(x) некоторую прокс-функцию множества Q. Предполагается что функция d(x) является непрерывной и сильно выпуклой на Q с параметром выпуклости единица. Для простоты предположим что d{x) дифференцируема. Обозначим через х0 ее центр:

xq = argmin{d(x) : х S Q}.

Не ограничивая общности, будем считать что d(xо) = 0. Обозначим через р{х,у) = d(y) - d{x) - (Vd(x),y -х), х,у <Е Q,

брегмановское расстояние между точками х и у. Теперь мы можем определить брегмановскую проекцию:

Вд{х,д) = а^тт{{<7, у - х) +р{х,у) : у <Е (?}.

В терминах этого отображения удобно записывать методы мизимизации первого порядка.

(1.2.7)

Теорема 1.2.1 Пусть / е С¿^(С?)- Тогда для всех к > 1 выполнено неравенство

№)-Г < ШПъ)-Г] < (1.2.8)

¿=1

где

г=1

Двойственный метод пересчитывает простейшую модель целевой функции.

Двойственный градиентный метод Инициализация: Положим фо(х) = \р{ха,х).

При к> 0 повторяем: Вычисляем хк = аг§тт

хеЯ

_Пересчитываем г1>м{х) = фк(х) + х[/(£&) + (У/(жь),ж - хк}}.

(1.2.10)

Теорема 1.2.2 Пусть последовательность {хк}к>о сформирована методом

(1.2.10). Обозначим ук = Тд(хк), иУк = ¿т ^У1,к> 0. Тогда при всех к > О

¿=о

выполнено неравенство

Прямой градиентный метод

хк+1 = Вя{хк, \4}\хк)), к = 0,1,....

И, наконец, быстрый градиентный метод может рассматриваться как комбинация этих двух алгоритмов.

Быстрый градиентный метод При к > 0 повторяем следующие операции:

Вычисляем f(xk) и V/(:хк). Находим ук = TQ(xk).

Находим zk = arg min < Ld{x) + Y1 ^[/(^i) + (V/(xj),a; — x*}] : x € Q ■r l ¿=o

Полагаем xk+1 = + _

(1.2.18)

Теорема 1.2.3 Пусть последовательности {^fcjfcio и о

сформированы методом (1.2.18). Тогда при всех к > 0 справедлива оценка

"+Т+2)/Ы < min |Ld(x) + £Д[/(х*) + (V/(xO,x - Xi)} : х € q| .

(1.2.19)

Таким образоль,

/Ы " /(**) * Ääy (L2-2°)

где х* - это оптимальное решение задачи (1.2.1).

Этот параграф заканчивается описанием модификаций этих методов, предназначаемых для минимизации сильно выпуклых функций. Сначала показывается что понятие сильной выпуклости у гладких функций естественным образом связывается только с евклидовой нормой (для этого доказывается что число обусловленности в ¿j-норме не может быть меньше размерности пространства). Затем приводятся оценки скорости сходимости простейших градиентных методов, которые являются непрерывными по параметру сильной выпуклости.

В последнем параграфе 1.3 этой главы приводятся необходимые сведения из теории самосогласованных барьеров (см. |19]). Эти результаты необходимы для обоснования сложности решения вспомогательных задач в методах градиентного типа.

Глава 2 посвящена современным методам субградиентного типа. Основные результаты этой главы опубликованы в работах [18, 21, 22]. В

параграфе 2.1 описываются новые прямо-двойственные субградиентные методы для минмимизации негладких функций. Первые (прямые) субградиентные методы были предложены в работах Н.З.Шора8 и Б.Т.Поляка9. Двойственный субградиентный метод был известен под именем зеркального спуска10. Однако в обоих случаях методы имели только одну управляющую последовательность шаговых множителей. В этом параграфе мы показываем что требуются две такие последовательности: одна для движения в прямом пространстве, и одна - для движения в двойственном. В результате получаемые методы освобождаются от излишних логарифмических множителей в оценках трудоемкости. Остановимся подробнее на структуре предлагаемых методов.

Пусть выпуклое замкнутое множество Q снабжено прокс-функцией d{x). Это множество может быть неограниченным. Нам потребуются две вспомогательные функции для множества Q опорного типа:

£r>(s) = max{(s,a: — жо) : d(x) < D},

xeQ (2.1.11) Vg(s) = max{(s,x — xo) — 0d(x)},

xeQ

где D > 0 и (3 > 0 являются параметрами. Первая функция является обычной опорной функцией множества То = {х 6 Q : d(x) < D}. Вторая функция представляет собой сглаженный вариант первой. Заметим что обе функции положительны. Нам потребуется следующее соотношение между функциями (2.1.11).

Лемма 2.1.15 При всех s <= Е* и (3 > 0 имеем: Cd(s) < ¡3D + Vp(s).

Рассмотрим следующие последовательности:

Хк = {х,-},*=о С Q, Gk = Ы1о С Е\ Ак = {Aj^o С R+.

Обычно, тестовые точки Xi и веса А; генерируются некоторым методом, а вектора (субградиенты) вычисляются оракулом Q{-) типа черный ящик,

9i = G(xi), г > О,

8Shor N.Z. Minimization Methods for Nondifferentiable Functions. - Berlin: Springer-Verlag, 19S5. - 312p.

9Поляк Б.Т. Общий метод решения экстремальных задач // ДАН СССР - 19G7 - Т.8 - С.593-597.

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

связанным с конкретной выпуклой задачей.

Мы собираемся приближать прямые и двойственные решения нашей задачи с помощью следующих усредненных объектов:

к к

sfc+1 = sfc+1 = s:sk+1,

г=0

¿=o г=о (2.1.19)

где хо = хо и во = 0. Качество последовательности Хк естественным образом описывается следующей функцией зазора:

8к{0) = тах - х) : х € Тв Л , В > 0. (2.1.20)

х и=о )

Полезной является и сглаженная функция зазора

Дк(/3, О) + Хг - Х0) + У0{-Зк+1).

¿=0

При этом, для всех неотрицательных Б и /3 имеем: 5к(0) < Ак(0,В).

Поскольку множеств С} простое, значения функций зазора могут быть легко вычислены. При некоторых В эти значения могут быть отрицательными. Однако, если решение х* нашей задачи существует, то для О > х*) значение 5к(0) неотрицательно независимо от последовательностей Хк, Л/,- и Ск, используемых для его определения. Рассмотрим теперь общую схему двойственных усреднений (ДУ).

Инициализация: Set so = 0 е Е*. Choose 0о > 0. Итерация (к > 0):

1. Вычисляем дк = G(xk).

2. Полагаем А^ > 0. Set sk+i = sк + Хкдк.

3. Выбираем (Зм > (Зк. Полагаем хк+1 = npk+l(-sk+i).

(2.1.24)

Теорема 2.1.30 Пусть последовательности Хк, и Ак построены схемой (2.1.24)- Тогда при всех к > 0 и й > 0 имеели

5к(Б) < Ак((Зк+1,0) < + (2.1.25)

г—0

Форма неравенств (2.1.25) приводит к естественной стратегии выбора параметров . Определим последовательность:

/?о = Л = 1, Д+1 = Д- + А, г> 1.

Разумность ее определения подтверждается соотношением рк+\ = Т'

г—0 №

к > 0. Таким образом, эта последовательность может использоваться для балансировки двух членов, возникающих в правой части неравенства (2.1.25). Скорость роста этой последовательности оценивается так:

Имеются две стратегии для выбора параметров А;: а) простые усреднения: \к = 1; б) взвешенные усреднения: Ак = щр Приведем схему ДУ-метода для первого способа.

Метод Простых "Усреднений

Инициализация: Set so = О G Е*. Выбираем 7 > 0. Итерация (к > 0):

1. Вычисляем gk = Q{xk). Set sfc+i = sk + gk.

2. Выбираем = 7/?fc+i. Полагаем t = npk+i(—Sk+i).

(2.1.31)

Теорема 2.1.31 Предположим что < L, к > 0. Для метода (2.1.31) имеем Sk = к + 1 и 5k{D) < ßk+1 (7D + .

Покажем как эта техника работает на примере задачи

min{/(x) : xeQ}, (2.1.32)

где / - выпуклая на Е функция и множество Q является выпуклым и замкнутым. В этом случае имеется следующая интерпретация функции зазора Sk(D). Обозначим

h{x) = Е Hf(xi) + (5г.х ~ яг)]". (9i е df(xi))

г—0

fk{D) = min{lk(x) : х 6 FD},

f*D = min{/(a*) : x €

Поскольку функция /(•) выпукла, в силу определения функции зазора (2.1.20) имеем:

j-MD) = à È Лi/fc) - HD) > f(xk+1) - rD-i=0

Таким образом, в силу Теоремы 2.1.31, имеем

Соответствующая алгоритмическая схема выглядит так:

Xk+i = argminj ¿y J2[fixi) + (9i,x - х{)] + j , к > О,

zsy ^ i=o )

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

В параграфе 2.2 предлагается барьерный су б градиентный метод (БСМ). В нем сглаживание функции зазора производится с помощью самосогласованного бартера. Пусть выпуклое замкнутое множество Q С Е не содержит прямых и снабжено ^-самосогласованным барьером F. Для произвольного х € int Q введем следующую локальную норму:

Ml = (MV2^)]-1*)1/2, seE*.

Рассмотрим другое выпуклое множество Р С Е. Нас будет интересовать их пересечение Р = PÇ\Q, которое предполагается ограниченным. Обозначим через Xq его условный аналитический центр:

xq = arg min F(x) € P0 = P(~]mtQ С P.

■те p0 1 1

Для множества Р, введем гладкую аппроксимацию ее опорной функции:

Uß{s) = max{{s,x - х0) - ß[F(x) - F(x0)]}, s G E*, (2.2.3)

где ¡3 > 0 - это параметр сглаживания. Обозначим через единственное

решение задачи максимизации (2.2.3).

Рассмотрим задачу выпуклой оптимизации в следующей форме:

Найти /* =Г тах{/(ж) : х € Р}, (2.2.13)

где / - это вогнутая функция. Мы предполагаем что / супер-дифференцируема на Ро и что множество Р является простым. Приведем общую схему БСМ.

Инициализация: Полагаем во = 0 € Е*. Итерация (к > 0):

1. Выбираем > 0 и вычисляем хк = м^Дв*).

2. Выбираем А* > 0 и полагаем = вк + А¿V/(а;^).

(2.2.14)

Для анализа скорости БСМ нам потребуется следующие функции зазора:

Ь(у) = Е-М^Дх{),у~хг), 1*к =£ тах 1к(у), к > 0.

¿=о УеР

Теорема 2.2.1 Пусть паралгетры метода (2.2.14) удовлетворяют соотношению

< рк < рк+1, к> 0. (2.2.15)

к к / \ Обозначим = £ Л»> и Ак = £ ), где ы„(т) = -т -

г—0 «=0 4 '

1п(1 — т). Тогда

< Ак + рк+1и [1 + 21п (1 + + с^^ЦУ/ЫЦ^ )] , А>0,

(2.2.16)

где с{0) = 1 если С} является конусом и барьер логарифмически

однороден. В противном случае, с(С]) = 3.

Оценим теперь скорость сходимости БСМ при решении некоторых специальных задач.

Определение 2.2.1 Мы говорим что / е Вм{Р) если ||У/(:т)||* < М для любого х ё Ро.

Для функции / € Вм(Р), в БСМ можно выбрать следующие значения параметров:

= 1, к > 0, ßo = ßu ßk = M-(l + y/fj,k> 1. (2.2.19)

Теорема 2.2.2 Пусть задача (2.2.13) с f £ Вм{Р) решается методом (2.2.14) с параметрами заданными в (2.2.19). Тогда при любом к > 0 имеем:

Ы ^ + + (2.2.20)

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

В параграфе 2.3 рассматриваются градиентные методы для минимизации составных функций. Предполагается что целевая функция задачи имеет вид

ф{х) = /(х) + Щх), (2.3.1)

где f(x) - дифференцируемая функция заданная черноящичным оракулом, а Ф(х) - выпуклая замкнутая простая функция общего вида. Для любого у € Q определим составное градиентное отображение:

mL{y\x) = f(y) + (V/(y), х — у) + ~\\х — у\\2 + Ф(а:),

TL{y) = arg min mL(y;x), (2.3.10)

xeQ

где норма ||-|| евклидова (||/j|| = {Bh, h)1?2, В = BT >- 0), a L- положительная константа (в обычном градиентном отображении Ф(-) = 0). Теперь можно определить аналог градиентного направления для гладкой функции:

gL(y) = L ■ В(у — Ti(y)) е Е\ 21

(2.3.11)

Если <5 = Е и Ф = 0, то дь{у) = Vф(у) = У/(ж) при любых Ь > 0. Наше предположение о простоте функции Ф означает в точности реализуемость операции (2.3.10). Теперь можно определить градиентную итерацию.

Градиентная итерация Я(х, М)

полагаем: Ь := М.

повторяем: Т \= Ть(х),

Если ф(Т) > ть[х\ Т) то Ь := Ь ■ 7„, Пока не выполнится: ф{Т) < ть{х\Т).

ВЫХОД:

д(х,м).т = т, д{х,м).ь = ь, д{х,М).Б = 5ь(х).

(2.3.26)

Обычно выбирают = И — 2. Теперь можно рассмотреть прямой градиентный метод.

Прямой градиентный метод ОМ(уо, Ь0)

Ук+1 = д(ук,ьк).т, мк = д(Ук,ьк).ь, Ьк+1 = тах{£0, А4/7Л"

(2.3.28)

Можно показать что Ик, общее число вызовов оракула после к итераций метода (2.3.28) не может быть большим: А^. < 1 + ■ (к + 1) + ^ .

Теорема 2.3.4 Пусть функция / выпукла на <5- Предположим что она достигает своего минимума на <5 в точке х* и что ее множества уровня ограничены:

\\у-х*\\ < Я Ууе<Э:ф(у)<ф(уо). (2.3.35)

Если ф(уо)—ф(х*) > -уиЬ/П2, то ф{у\)—ф{х*) < 1и1£п . В противном случае,

ФЫ)-Ф(х*) < к> о.

(2.3.36)

К составным функциям можно применять и быстрый градиентный метод.

Быстрый градиентный метод Л(хо, Ьо, ¡1)

Инициализация: Фо{х) — 2IIх — хо||2, А) = 0-

Итерация к > 0

Полагаем: Ь := Ьк.

Повтор: Найти а из квадратного уравнения Аа+а = 21+^Лк. Полагаем у = и вычисляем Ть(у).

если: (ф'ту)),у-ть{у))>{\\ф'{п{у))\\1 То СТОП Повтор Иначе Ь = Ь- 7„.

полагаем: Ук := у, мк := Ь, ак+1 := а, Ьк+1 := Мк/~1Л, хк+г := ТМк(ук), ■фк+1(х) := фк(х) + ак+1[/(хк+1) + {\7/(хк+1),х - хк+х) + Ф(аг)].

(2.3.52)

Теорема 2.3.6 Предположим что градиент функции / удовлетворяет условию Липшица с константой Ь]. И пусть паральетр Ьо 6 (О,Ь/). Тогда скорость сходимости метода Л(хо, Ьо, 0) оценивается следующим образом:

ф(хк)-ф(х*) < к > 1. (2.3.53)

Мы видим что составное градиентное отображение полностью устраняет негативное влияние простой добавки на скорость сходимости соответствующих градиентных методов.

В Главе 3 рассматриваются методы решения вариационных неравенств. Основные результаты этой главы опубликованы в работах [13, 20].

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

пВаГшберг М. М. Вариационный метод л метод монотонных операторов в теории нелинейных уравнений. - М.: Наука. 1972. - 385с.

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

Нас будет интересовать следующая задача решения вариационного неравенства:

Найти х* eQ : (g(x), х - х') > 0 Vx € Q, (3.1.1)

где оператор g монотонен. Пусть функция d{x) является сильно выпуклой на Q с параметром выпуклости и > 0. Определим брегмановское расстояние

р(х,у) = d(y) - d(x) - (Vd(x),y - х), х £ Q, y€Q.

Выберем произвольную точку х 6 Q в качестве центра множества Q. Заметим что множество Q может быть неограниченным. Мы будем описывать качество произвольной точки х G Q как приближенного решения задачи (3.1.1) с помощью следующей условной функции близости:

fD(x) = max{{g(y),x-у) : р{х,у) < D},

y&Q

где D - фиксированный положительный параметр.

Теперь мы можем определить основной шаг нашего метода [двойственную экстраполяцию). Обозначим

Tß(z, s) = argmax{(s, х — z) — ßp{z, x) : x £ Q}.

Зафиксируем некоторые положительные значения ß и А. Рассмотрим отображение £pt\(s), которое переводит произвольную точку s G Е* в новую точку

{х = Tß(x, s), У = Tß(x,-\g(x)), s+ = s — A g(y).

Этот шаг может применяться для решения ВН различной степени гладкости.

Метод решения гладких вариационных неравенств

Инициализация: Выбираем х (Е <5- Фиксируем /3 = ~ и выбираем Б > 0.

Задаем точность е > 0. Полагаем = 0 ё £".

Итерация: (яьУь^) = £^,1(51-1), ^ > 0.

: Если £<5(уг),2Л - я) < б ■ {к +1),то Стоп.

г=0

Результат: у,, = ^Ьт И

_¿=о_

(3.1.20)

Теорема 3.1.2 Пусть оператор д(х) будет липшицевым на <5. Тогда

Мт) < к > 0. (3.1.21)

Критерий прерывания в методе (3.1.20) обеспечивает неравенство /о(ук) < е. Это критерий будет выполнен не более чем через 1 + итераций.

Метод для ВН с ограниченным изменением оператора

Инициализация: Выбираем х £ и Б > 0. Для к > 0 положим Рк = М^Щ. Выберем точность е > 0. Положим = 0 € Е*.

Итерация: {хк,Ук,зк) = к> 0.

Остановка: Если ^2(в{Уг),Уг -х)+ Ы^-) < е ■ {к + 1),то Стоп. ¿=0

Результат: к г=0

(3.1.23)

Теорема 3.1.3 Предположим что оператор д(х) имеет ограниченное изменение на множестве <5:

\\д{Х1) - д(х2)\и < М Ухьх2ед. 25

Тогда для любого к > О имеем: /о(Ук) < ^^у g-(t+i)- Критерий прерывания в методе (3.1.23) обеспечивает выполнение неравенства foiVk) < с- Этот критерий сработает не более чел1 за 1 + 2PJ итераций.

В заключение параграфа мы показываем как применять полученные методы для вычисления седловых точек и для решения билинейных матричных игр,

В параграфе 3.2 мы показываем как решать сильно монотонные ВН и квазивариационные неравенства. Рассмотрим непрерывный оператор д(х) : Q —> Е*, который является сильно монотонным.

(g(z)-g{v),x-y) > v\\x-y\\\ (3.2.2)

Мы будем искать решение следующего ВН:

Найти x*{Q) е Q : {g{x*(Q)),y - x*(Q)) > 0 Уу е Q. (3.2.3)

Для описания качества приближенного решения задачи (3.2.3), нам потребуется следующая мера близости:

f(x) = sup {{g(y),x - у) + у - *||2} . (3.2.4)

yeQ

Для /3 > 0, обозначим

= {g{y),y-x)-\(3\\x-yf,

Ых) = Sfc = E лг.

г=0 г=0

Пусть оператор g является липшицевым с константой L. Для простоты предположим что константы fiu L нам известны. Обозначим через ■у = jf > 1 число обусловленности оператора д.

Метод для силыю монотонных ВН

Инициализация: Выбираем х G Q. Полагаем Ао = 1, и г/о = х.

Итерация (к > 0): хк = а^тахФ/Дх), xsQ ук+1 = arg шах (х), xeQ ^fc+i = ^ • sk.

Результат: Ук = XiVi-i=0

(3.2.11)

Теорема 3.2.3 Если оператор д сильио монотонен и Липшицев, то

М1У*-*Ч<?)112 < №) < /(¿)-72-ехр{-^т}; к> 0. (3.2.12)

Во второй части параграфа рассмативаются квазивараиционные неравенства (КВН):

Найти xt е Q{xt) : (g{xt),y - х») >0, Vj/ G Q{xt), (3.2.14)

где точечно-множественное отображение Q : E —> 2е принимает выпуклые и замкнутые значения. Существование решения этой задачи гарантируется только при малой скорости изменения множеств Q(x)12: существует а < такая что

\Ых)(г) - nQ(y]{z)\\ < а\\х - у\\, Vx,y,z£E. (3.2.15)

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

Обозначим через y^(Q,x) результат работы iV-шагового метода (3.2.11), применяемого к решению ВН с оператором д на множестве Q и центральной точкой х = argmaxj/jJ^x). Обозначим J =f 1 — cry и предположим что оно

xeQ

положительно. Зададим

^=[2(7+1)11x^ + 1,

12Noor М. A., Oettli W. On general nonlinear complementarity problems and quasi-cquilibria // Lc Matem-atiche - 1994 - V.XL1X - 313-331p.

7(7+\Л2-1)

и рассмотрим следующую двухуровневую схему.

Выбираем щ е Е. Для к > О повторяем: ^ ^^^

Хк = KQ(Uk){uk), Uk+1 = 2/jv(Q(Ufc),

Теорема 3.2.8 Пусть 5 > 0. Тогда существует единственное решение х* КВН (3.2.Ц), и метод (3.2.30) сходится со следующей скоростью:

\\uk-x4 < I.exp{-|ft}-||uo-T(«o)||. (3.2.31)

В Главе 4 рассматриваются методы второго порядка. Представленные результаты опубликованы в работах [14, 16, 11].

В параграфе 4.1 описывается кубическая регуляризация метода Ньютона. Метод с таким названием появился впервые в статье А.Беннета13. Первый результат о локальной квадратичной сходимости метода принадлежит Л.В.Канторовичу14. Однако оценки глобальной скорости сходимости этого метода на вырожденных задачах так и не были получены15.

Мы рассматриваем задачу безусловной минимизации функции f с липшицевым Гессианом:

l|V2/(:r) - V2f(y) II < L\\x - у II, Vx,y e Rn.

Тогда нетрудно видеть что вспомогательная функция

ЬЛу) = Я*) + (V/(x), у-х) + i(v2f(x){y -X),y-X) + I\\y-

является верхней оценкой второго порядка для целевой функции:

f{y) < ЬАу) VyeRn-

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

(4.1.1)

13Bonnot A.A. Newton's method in general analysis. // Proc. Nat. Ac. Sei. USA - 1916 - V.2, N10. - P.592-598.

14Канторовнч Л.В. Функциональный анализ и прикладная математика // Успехи мат. наук - 1948 - T.3, вып.1 - С.89-185.

15Сош1 A.B., Gould N.I.M., Toint Pli.L. Trust Region Methods - Philadelphia: SIAM, 2000. - 1005p.

xk+1 e Arg min &,Xk{y)

(здесь Argmin обозначает глобальный минимум). Этот подход называется кубической регуляризацией метода Ныотона. Заметим что задача (4.1.1) может быть невыпуклой и может иметь много локальных минимумов. Однако, наш подход реализуем за полиномиальное время так как эта вспомогательная задача оказывается эквивалентной задаче минимизации специальной выпуклой функции одной пременной.

Положим ¡м(х) = min [/(х) + (V/(x), у - х) + UV2f(x){y -х),у-х) +

Введем отображение

Тм(х) е Arg min [(V/(x),y - х) + ¡(V2f(x)(y - х),у - х) + f || у - х||%.1

где "Arg" означает что Тщ(х) выбирается из множества глобальных минимумов соответствующей задачи минимизации. Пусть Lq 6 (О, L] -положительный параметр. Рассмотрим следующий метод.

(4.1.16)

Поскольку )'м[х) < /(х), этот процесс является монотонным: f(xk+1) < /(xfc). Про эту схему удается доказать много интересных результатов.

• Для невыпуклых функций, для нормы градиента справедлива глобальная оценка 0(l/fc2//3), где к - это счетчик итераций. В невырожденной ситуации, метод обладает локальной квадратичной скоростью сходимости. Невырожденные стационарные точки и точки максимума являются точками отталкивания для минимизирующей последовательности.

• В выпуклой ситуации, глобальная скорость сходимости по невязке по функции составлет 0(1/к2).

• Получены глобальные оценки скорости сходимости для звездно-выпуклых функции, градиснтно доминируемых функций и функций,

Кубическая регуляризация метода Ныотона Инициализация: Выбираем хо 6 Я.п.

Итерация к, (к > 0):

1. Находим Мк € [Ьа, 2Ь] такое что

1{ТМь{хк)) < 1мЛхк)-

2. Полагаем хк+1 = Тмк(хк).

оценивающих невязку в системе нелинейных невырожденных уравнений.

В параграфе 4.2 описывается ускоренная версия кубической регуляризации метода Ньютона, применяемой для минимизации выпуклой функции. Ускорение стало возможным за счет применения аппарата оценочных функций (см. §§ 2.2 и 3.3).

Ускоренная версия кубической регляризации Инициализация: Выбираем xq € Е. Полагаем М = 2L и N = 12L. Вычисляем х\ = 7l3(xо) и полагаем ф\(х) = f(xi) + — Жо||3. Итерация к, (к > 1):

1. Вычисляем vk = arg min фк(х) и полагаем ук = ¿rj^fc + T^vk-хеЕ

2. Вычисляем хк+\ = Тм(ук) и пересчитываем фк+1(х) = фк{х) + ÍM±2) . lf(xk+1) + (Vf(xk+1),x-xM)}.

(4.2.28)

Теорема 4.2.2 Если последовательность точек {xjJjiLi сформирована методом (4-2.28), то для любого к>\ выполняется неравенство:

- я*-) * Г (4-2-29)

где х* - оптимальное решение задачи.

В параграфе 4.3 описывается модифицированный метод Гаусса-Ньютона. Он применяется для нахождения приближенного решения уравнения

F(x) = 0, х G JEi. (4.3.4)

Для измерения качества такого решения, вводится функция близости ф(и), и 6 Е2, которая выпукла, неотрицательна и обнуляется только в начале координат. Она должна удовлетворять условию Липшица с единичной константой и иметь острый минимум в нуле:

Ф(и) > 7plM|, Vu е Е2, (4.3.5)

при некотором 7ф £ (0,1]. Например, можно взять ф(и) = ||и||. Тогда = 1.

Таким образом, задача (4.3.4) преобразуется в следующую задачу безусловной минимизации:

min{ Дх) = 4>{F(x)) } ^ f. (4.3.6)

xeEi

Рассматривая локальную модель нашей целевой функции:

ф(х-у) = ф (F{x) + WF{x)(y - х)), ye Ei, приходим к следующему методу Гаусса-Ньютона

Xk+1 е Arg min t/;(xfc; у).

yeEi

Такие схемы очень хорошо изучены16,17. Однако глобальная эффективность таких методов до сих пор неизвестна.

В этом параграфе, для функций с липшицевым якобианом

|| VF(x)-VF(y)\\<L\\x-y\\, Vx,y<=F, (4.3.7)

предлагается модифицированный метод Гаусса-Ньютона:

хм G Arg min [ф(х;у) + \М\\у - х||2] ,

yeEi

где "Arg" означает что точка x^+i выбрана из множества глобальных минимумов соответствующей задачи минимизации. Этот процесс обеспечивает монотонное убывание целевой функции. Более того, при условии глобальной невырожденности системы уравнений удается доказать глобальную оценку скорости сходимости процесса. При естественных предположениях, локальная сходимость будет квадратичной.

В Главе 5 описывается техника сглаживания, применяемая для построения ускоренных методов минимизации негладких функций. Основные результаты главы опубликованы в работах [9, 10, 12].

В параграфе 5.1 рассматривается задача минимизации

Find J* = пнп{/(ж) : х € Q:}, (5.1.3)

16Ortcga Л., Rheinboldt \V. Iterative Solution of Nonlinear Equations in Several Variables. - NY: Academic Press, 1970. - 630p.

I7Conn A.B., Gould N.I.M., Toint Pli.L. Trust Region Methods. - Philadelphia: SIAM, 2000. - 1005p.

где выпуклое замкнутое множество <51 в конечномерном вещественном пространстве Ег является ограниченным, а выпуклая функция /(х) непрерывна на <5ь Очень часто известна структура целевой функции в задаче (5.1.3):

/(х) =/(х) + тах{(Ах, и)2 - ф(и) : и € <3г}, (5.1.4)

где выпуклая функция /(х) непрерывна на <51, выпуклое замкнутое множество из конечномерного вещественного пространства Е2

ограничено, выпуклая функция ф(и) непрерывна на а линейный

оператор А отображает Е\ в ЕВ этом случае задача (5.1.3) может быть переписана в сопряженной форме:

тах{()!>(г() : и 6 ¿З2} г,

(5.1.5)

ф(и) = —ф(и) + тт{(Лх, и)2 + /(х) : х € С^г}.

Рассмотрим прокс-функцию ¿2(11) множества <22 с параметром выпуклости <72 = 1. Обозначим через

и0 = а^тт{е?2(м) : и € (¿2}

ее прокс-цептр. И пусть (^(ыо) = 0. Выберем положительное /х в качестве параметра сглаживания. Рассмотрим следующую функцию:

/„(х) = шах{(Лх, и)2 - ф(и) - цй2{и) : и е <32}- (5.1.6)

Обозначим через и^(х) единственное оптимальное решение этой задачи.

Можно показать что функция ft¡ является (9(/л)-аппроксимацией исходной функции. С другой стороны, ее градиент является липшицевым с константой 0{ 1/ц). Это обстоятельство позволяет находить е-решение задачи (5.1.3) за 0{ 1/е) итераций быстрого градиентного метода (см. §1.2), применяемого к задаче минимизации сглаженной функции /,,. Получаемые оценки трудоемкости на порядок улучшают нижние оценки трудоемкости черноящичных методов, полученных в теории сложности.

В конце параграфа рассматриваются применения техники сглаживания для нахождения решений матричных игр, непрерывной задачи размещения,

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

В параграфе 5.2 рассматривается ситуация когда прямая и сопряженная форма задачи (5.1.3) имеют одинаковую сложность. В этом случае можно применять симметричные методы, которые чередуют шаги в прямом и сопряженном пространстве.

Пользуясь обозначениями §5.1, заметим что при любых х £ и и £ С5г выполняется неравенство

Более того, при естественных предположениях в задачах (5.1.3), (5.1.5) будет нулевой зазор двойственности. Однако, //(2(ж) < /(х) и ф(и) < ф^^и). Такая ситуация открывает принципиальную возможность обеспечить выполнение условия обратного зазора:

при некоторых х € (¿1 п и € <22• Ясно что из условия (5.2.13) нетрудно получить оценку качества соответствующей прямо-двойственной пары (х, й):

О < max{/(i) - Г, Г - ф{й)} < f{x) - ф(й) < + /х2Д>, (5.2.14)

где D1 = max di(x), и D2 = max ¿2(4). xeQi ueQ2

Оказывается условие обратного зазора (5.2.13) можно поддерживать при параметрах сглаживания стремящихся к нулю. Покажем как это можно сделать, уменьшив и не меняя Ц2-

Для х € Q\ определим прямое градиентное отображение:

Т„(х) = argmin {(V/;t2(x),y - х)г + \Ь^„2)\\у - r||?} . (5.2.16)

v&Q 1

Теорема 5.2.1 Пусть точки х € С)\ и и € (^2 удовлетворяют условию обратного зазора (5.2.13) при некоторых положительных Дх и

ф(и) < f(x).

(5.2.12)

f,,2(x) < ф^{и)

(5.2.13)

Зафиксируем т G (0,1) и выберем ^ = (1 — т)р\,

х = (1 - т)х +TXßl(ü),

й+ = (1 -т)й + ти^(х), (5.2.19)

х+ = Tß2(x).

Тогда пара (х+,й+) удовлетворяет условию (5.2.13) с паралктрами сглаживания ц^ и ¡¿2 при всех не слишком больших т:

(5-2.20)

Это правило пересчета, применяемое поочередно в прямом и сопряженном пространстве, позволяет решать задачи минимизации со структурой (5.1.4) за 0(1/е) итераций. В конце параграфа мы также рассматриваем сильно выпуклый случай и показываем как построить алгоритм его решения с трудоемкостью 0( 1 /е1/2) итераций.

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

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

Пусть функция одной вещественной переменной /(г) задана рядом

ос

/(т) = а0 + £ актк k= 1

с ßfe > 0 при к > 2. Предположим что ее область определения dorn / = {т : |т| < R} не пуста. Для симметрической матрицы X рассмотрим следующую симметричную функцию собственных значений:

i= 1

Ясно что dorn F = {X G Sn : Xmax{X) < R, Amin(X) > -R}. Теорема 5.3.1 Для любого X € dorn F и H G Sn имеем

(V2F(X)H, H) < £v2/(Aw(m))(A(,)(|tf|))2.

! = 1

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

1. Квадрат матричной /р-нормы. Для целого р > 1 рассмотрим следующую функцию:

ад = \\\\{х)\\\21>) = \(х^,1п)^.

Тогда для любого матричного направления Н имеем:

<У2адЯ,Н)Л/ < (2р — 1)||Л(Я)||(2Р) = (2р- 1)||Я||22р).

2. Энтропийное сглаживание максимального собственного

значения. Рассмотрим функцию Е(Х) = 1п ^ еА''х\ Тогда при любом Н

(S72E(X)H,H)M <

¿=i

¿ел«>т 1 ¿еЛ(,)(^)(л(г)(|я|))2 < \\н\\2(ос).

г=1

Li=l

В заключение параграфа показывается как можно использовать сглаженные функции для минимизации максимального собственного значения и спектрального радиуса семейства симметрических матриц, линейно зависящих от параметров. Оценка трудоемкости соответствующих методов имеет порядок 0(1/е).

В Главе 6 приводятся алгоритмы, позволяющие получать приближенные решения экстремальных задач с относительной точностью. Соответствующие результаты опубликованы в статьях [15, 17].

В параграфе 6.1 рассматривается коническая задача безусловной минимизации

Найти /* = min{/(x) : х в С},

(6.1.1)

С = {х G Rn : Сх = b}, где выпуклая функция f(x) является однородной степени единица, С - это р х n-матрица, и ¿> ф 0. Основное предположение о задаче (6.1.1) выглядит так:

dorn / = Я™, 0 eint 5/(0). (6.1.2)

Отсюда следует что /* > 0 и задача отыскания решения задачи (6.1.1) с некоторой относительной точностью поставлена корректно.

Зафиксируем некоторую норму || • || в Яп. Пусть положительные параметры 7о 71 удовлетворяют следующему условию:

%1,.МСЗ/(0)С%.(71). (6.1.3)

Обозначим а = ^ < 1. Этот параметр определяет сложность нахождения решения задачи (6.1.1) с некоторой относительной точностью.

Обозначим через хо проекцию начала координат на аффинное подпространство £ относительно нормы || • ||:

||х0|| = тш{||х|| : Сх = Ь}.

Эта точка снабжает нас важной информацией о размере оптимального решения.

Теорема 6.1.1

1. Для любого х (Е К12 имеем

70-1И1 </(*) <71"М1- (6-1.6)

Таким образом, функция /(х) липшицева на Я71 относительно нормы || • || с константой 71. Более того,

а/Ы < 7о • 1Ы1 < /* < /(х0) < 71 " 1Ы1- (6.1.7)

2. Для любого оптимального решения х* задачи (6.1.1) имеем:

\\Х0-Х'\\<%Г<%ГЫ- (6.1.8)

Простейший метод решения задачи (6.1.1) выглядит так.

Субградиентный метод С\-{П) Для к := 0... N повторяем

Вычисляем /(х^).и д(хк).

:= пс (хк - ^ • .

Результат:

СN(11) = argmin{/(x) : х = х0;...

(6.1.10)

Теорема 6.1.2 Для фиксированного 8 из (0,1) выберем Тогда /(Слг(р)) < (1 + 6) ■ /*.

(6.1.13)

Этот метод можно ускорить засчет правильной стратегии обновления. Положим

N =

где е - число Эйлера. Рассмотрим следующий процесс. Полагаем £о = жо, и для / > 1 повторяем следующие операции:

если /(¿;) > тоТ:={и СТОП.

Теорема 6.1.3 Число точек в процессе (6.1.14) ограничено:

Т < 1 + 21п -.

(6.1.14)

(6.1.15)

Последняя из этих точек удовлетворяет неравенству /(£т) < (1 + 5)1* ■ Общее число градиентных шагов в процессах нижнего уровня (6.1.14) не превосходит

£.(1 + !)2-(1+21П1). (6.1.16)

В заключительной части этого параграфа мы показываем как можно еще снизить трудоемкость получения ¿-решения в случае когда целевая функция является составной. А именно, мы предполагаем что /(х) = Е(А(х)), где А(х) - линейный оператор, а Е(и) - простая нелинейная выпуклая однородная функции. Тогда, комбинируя операцию сглаживания с применением быстрого градиентного метода, можно добиться трудоемкости 0(1/5) (см. теорему 6.1.5).

В параграфе 6.2 мы показываем как можно еще снизить трудоемкость нахождения ¿-решения за счет предварительного вычисления подходящей евклидовой нормы. Мы начинаем с описания эффективных алгоритмов построения эллипсоидов Джона для различных типов выпуклых множеств. Эллипсоиды \Уг(и, С) С Е* представляются в следующей форме:

\Vriv.G) = {з€Е* : Ця--

,С~\з-у)у/2<г},

где G >- 0 - линейный оператор из Е в Е*. Если v = 0, то мы переходим к обозначению Wr(G). Эллипсоид W\(v, G) называется ß-аппроксимацией выпуклого множества С С Е*, (ß > 1) если

Wx(v,G) С. С С W0(v, G).

Параметр ß называется радиусом эллипсоидальной аппроксимации.

Сначала приводятся алгоритмы, работающие с центрально-симметричными телами и с выпуклыми телами общего вида, близкие к алгоритму Хачияна18. Доказывается что они получают приемлемую аппроксимацию за 0(п) шагов, где п - размерность пространства. Далее мы рассматриваем знако-инвариантные тела. Показывается, что они допускают 0(п1,'2)-аппроксимацию, которая обеспечивается диагональной матрицей. Нахождение такой матрицы также требует 0(п) итераций.

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

4е(1 + ln{2^/n))V2n\nm (1 + |) (6.2.34)

(см. теорему 6.2.5).

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

Более того, мы показали, что информация, полученная из "черного ящика позволяет ускорять эти методы, превышая даже максимально возможные скорости, полученные в теории сложности. По-видимому, в

18Khachiyan L.G. Rounding of polytopes in the real number model of cornputation. // Mathcmatics of Operations Research - 1996 - V.21, N2. - P.307-320.

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

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

Основные публикации автора по теме диссертации

1. Нестеров Ю.Е. Метод минимизации выпуклых функций со скоростью сходимости 0(\/к2) // Докл. АН СССР - 1983 - Т.269, вып.З - С. 543-547.

2. Нестеров Ю.Е. О классе методов безусловной минимизации с высокой скоростью сходимости // Журн. выч.мат. и мат.физ. - 1984 - Т.24, вып.7

- С. 1090-1093.

3. Нестеров Ю.Е. Метод линейного программирования с трудоемкостью 0(п3Ь) операций // Экономика и мат. методы - 1988 - Т.24, вып.1 - С. 174-176.

4. Нестеров Ю.Е. Полиномиальные методы для задач линейного и квадратичного программирования // Известия АН СССР - 1988 - вып.З

- С. 119 - 128.

5. Нестеров Ю.Е. Об одном подходе к разработке оптимальных методов минимизации гладких выпуклых функций // Экономика и мат.методы

- 1988 - Т.24, вып.З - С. 509-517.

6. Нестеров Ю.Е. Двойственные полиномиальные алгоритмы для линейного программирования // Кибернетика - 1989 - вып.1 - С. 34-54.

7. Нестеров Ю.Е. Эффективные методы нелинейного программирования.

- М.: Радио и Связь, 1989. - 280с.

8. Yu. Nesterov. Introductory lectures on convex optimization. A basic course.

- Boston: Kluwer, 2004. - 236p.

9. Nesterov Yu. Smooth minimization of non-smooth functions // Mathematical Programming - 2005 - V.103, N1.-P.127-152.

10. Nesterov Yu. Excessive gap technique in non-smooth convex minimizarion // SIAM J. Optim. - 2005 - V.16, N1. - P.235-249.

11. Nesterov Yu., Polyak B. Cubic regularization of Newton's method and its global performance // Mathematical Programming - 2006 - V.108, N1. -P. 177-205.

12. Nesterov Yu. Smoothing technique and its applications in semidefimte optimization // Mathematical Programming - 2007 - V.110, N2. - P.245-259.

13. Nesterov Yu. Dual extrapolation and its application for solving variational inequalities and related problems // Mathematical Programming - 2007 -V.109, N2-3. - P.319-344.

14. Nesterov Yu. Modified Gauss-Newton scheme with worst-case guarantees for its global performance // Optimization Methods and Software - 2007 -V.22, N3. - P.469-483.

15. Nesterov Yu. Rounding of convex sets and efficient gradient methods for linear programming problems // Optimization Methods and Software - 2008

- V.23, N1. - P.109-128.

16. Nesterov Yu. Accelerating the cubic regularization of Newton's method on convex problems // Mathematical Programming - 2008 - V.112, N1. - P.159-181.

17. Nesterov Yu. Unconstrained Convex Minimization in Relative Scale // Mathematics of Operations Research - 2009 - V.34, N1. - P.180-193.

18. Nesterov Yu. Primal-dual subgradient methods for convex problems // Mathematical Programming - 2009 - V.120, N1. - P.261-283.

19. Нестеров Ю.Е. Методы выпуклой минимизации. - М.: Изд. МЦНМО, 2010. - 263с.

20. Nesterov Yu., Scrimali L. Solving strongly monotone variational and quasi-variational inequalities // Discrete and Continuous Dynamical Systems -2011 - V.31, N4. - P.1383-1296.

21. Nesterov Yu. Barrier subgradient method // Mathematical Programming -2011 - V.127, N1. - P.31-56.

22. Nesterov Yu. Gradient methods for minimizing composite функцияэ // Mathematical Programming - 2013 - V.140, N1. - P.125-161.

Нестеров Юрий Евгеньевич

Алгоритмическая выпуклая оптимизация

АВТОРЕФЕРАТ

Подписано в печать 19.09.2013. Формат 60 х 84 1/16. Усл. печ. л. 1.9 Тираж 150 экз. Заказ номер 906 Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Московский физико-технический институт (государственный университет)" Отдел оперативной полиграфии "Физтех-полиграф" 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Текст научной работы диссертации и автореферата по математике, доктора физико-математических наук, Нестеров, Юрий Евгеньевич, Москва

Московский физико-технический институт (государственный университет) Лаборатория структурных методов анализа данных в предсказательном моделировании (ПреМоЛаб)

05201450204

Нестеров Юрий Евгеньевич Алгоритмическая выпуклая оптимизация

Диссертация на соискание ученой степени доктора физико-математических наук

по специальности 01.01.07 - вычислительная математика

На правах рукописи УДК 519.8

МОСКВА - 2013

Оглавление

Введение 6

1 Предварительные результаты 14

1.1 Классификация выпуклых функций ..............................................14

1.1.1 Нормы и производные........................................................14

1.1.2 Классы гладких функций....................................................16

1.1.3 Равномерно выпуклые функции............................................20

1.1.4 Сильно выпуклые функции ................................................23

1.2 Методы гладкой минимизации первого порядка..................................25

1.2.1 Прямой и двойственный градиентные методы............................25

1.2.2 Быстрый градиентный метод................................................28

1.2.3 Минимизация гладких сильно выпуклых функций......................32

1.3 Самосогласованные функции и барьеры..........................................35

1.3.1 Определение и свойства самосогласованных функций ..................35

1.3.2 Минимизация самосогласованных функций..............................47

1.3.3 Самосогласованные барьеры и метод отслеживания траектории ... 52

1.3.4 Конструирование самосогласованных барьеров..........................68

2 Современные субградиентные методы 78

2.1 Прямо-двойственные методы для негладких задач..............................78

2.1.1 Введение......................................................................78

2.1.2 Основные алгоритмические схемы..........................................82

2.1.3 Минимизация на простых множествах....................................88

2.1.4 Седловые задачи..............................................................96

2.1.5 Вариационные неравенства..................................................99

2.1.6 Стохастическая оптимизация........................101

2.1.7 Приложения в моделировании.......................103

2.1.8 Обсуждение .................................109

2.2 Барьерный субградиентный метод.........................111

2.2.1 Введение...................................111

'2.2.2 Сглаживание с помощью самосогласованного барьера.........113

2.2.3 Барьерный субградиентный метод.....................116

2.2.4 Максимизация положительной вогнутой функции ...........120

2.2.5 Приложения.................................122

2.2.6 Оптимизация в реальном времени как альтернатива стохастическому программированию.............................126

2.3 Градиентные методы минимизации составных функций............131

2.3.1 Введение...................................131

2.3.2 Составное градиентное отображение...................133

2.3.3 Составной градиентный метод.......................138

2.3.4 Быстрый градиентный метод........................144

2.3.5 Примеры применения............................151

2.3.6 Вычислительные эксперименты......................155

2.4 Приложение: барьерная проекция на симплекс .................166

3 Вариационные неравенства 169

3.1 Вариационные неравенства с гладким оператором ...............169

3.1.1 Введение...................................169

3.1.2 Двойственная экстраполяция........................170

3.1.3 Алгоритмические схемы ..........................176

3.1.4 Вычисление седловых точек........................179

3.1.5 Билинейные матричные игры .......................183

3.1.6 Обсуждение .................................188

3.2 Сильно монотонные операторы и квазивариационные неравенства......189

3.2.1 Введение...................................189

3.2.2 Решение сильно монотонных вариационных неравенств........191

3.2.3 Квазивариационные неравенства .....................196

3.2.4 Оператор релаксации для квазивариационного неравенства......198

4 Методы второго порядка 205

4.1 Кубическая регуляризация метода Ньютона...................205

4.1.1 Введение...................................205

4.1.2 Кубическая регуляризация квадратичной аппроксимации.......208

4.1.3 Общие результаты о сходимости......................211

4.1.4 Глобальные оценки эффективности для специальных классов задач . 215

4.1.5 Вычислительные детали ..........................224

4.1.6 Обсуждение .................................230

4.2 Ускоренная кубическая регуляризация метода Ньютона............232

4.2.1 Введение...................................232

4.2.2 Итерация кубической регуляризации метода Ньютона.........234

4.2.3 Ускоренный метод..............................237

4.2.4 Глобальная невырожденность для методов второго порядка......241

4.2.5 Минимизация сильно выпуклых функций................243

4.2.6 Ложное ускорение..............................245

4.2.7 Обсуждение .................................247

4.3 Модифицированный метод Гаусса-Ньютона...................248

4.3.1 Введение...................................248

4.3.2 Модифицированный метод Гаусса-Ньютона...............250

4.3.3 Процесс минимизации............................255

4.3.4 Глобальная скорость сходимости......................257

4.3.5 Обсуждение .................................261

5 Техника сглаживания 265

5.1 Сглаживание для явной модели целевой функции................265

5.1.1 Введение...................................265

5.1.2 Гладкие аппроксимации негладких функций...............267

5.1.3 Примеры приложений............................270

5.1.4 Вычислительные аспекты..........................279

5.1.5 Вычислительные эксперименты......................284

5.2 Условие обратного зазора в негладкой выпуклой минимизации........286

5.2.1 Введение...................................286

5.2.2 Описание структуры задач.........................287

5.2.3 Условие обратного зазора..........................288

5.2.4 Метод с градиентным отображением...................289

5.2.5 Метод с брегмановской проекцией.....................292

5.2.6 Анализ скорости сходимости........................294

5.2.7 Минимизация сильно выпуклых функций................296

5.3 Техника сглаживания в полуопределенной оптимизации............302

5.3.1 Введение...................................302

5.3.2 Гладкие симметричные функции собственных значений........304

5.3.3 Минимизация максимального собственного значения симметрической матрицы ...................................308

5.3.4 Минимизация спектрального радиуса симметрических матриц .... 310

6 Оптимизация с относительной точностью 315

6.1 Однородная модель.................................315

6.1.1 Введение...................................315

6.1.2 Коническая задача безусловной минимизации..............317

6.1.3 Субградиентная аппроксимирующая схема................321

6.1.4 Минимизация составной функции.....................324

6.1.5 Примеры приложений............................328

6.2 Эллипсоидальная аппроксимация выпуклых тел ................335

6.2.1 Введение...................................335

6.2.2 Вычисление эллипсоидов Джона......................337

6.2.3 Минимизация максимального модуля линейных форм.........348

6.2.4 Билинейные матричные игры с неотрицательными коэффициентами 353

Заключение 357

Литература 359

Введение

Актуальность темы и степень ее разработанности

Настоящая диссертация посвящена разработке новых методов решения нелинейных выпуклых задач оптимизации. Теория методов оптимизации является одной из самых востребованных областей численного анализа. Наиболее продвинутая ее часть посвящена решению выпуклых задач. Эти постановки базируются на солидном математическом фундаменте, разработанном в основном в первой половине 20го столетия математиками Г.Минк-овским, К.Каратеодори, Э.Хелли, В.Фенхелем, А.Александровым и другими (см., например, [74, 56, 6, 1]). Поначалу выпуклый анализ развивался независимо от теории экстремальных задач. Однако после основополагающей монографии Р.Т.Рокафеллара [25] центр развития этой науки окончательно сместился в сторону теории оптимизации [13]. В настоящее время существует большое количество прекрасных книг, как по выпуклому анализу, так и по его оптимизационным приложениям (см., например, [2, 3, 4, 5, 8, 10, 13]). Очень важно, что выпуклые задачи представляют собой практически единственный класс оптимизационных задач, допускающих построение методов с глобальными скоростными характеристиками, приемлемыми для большинства практических приложений. Это обстоятельство привело к появлению большого количества интересных методов и подходов. Основные приоритетные результаты в области выпуклой оптимизации принадлежат отечественным ученым А.Антипину, Ф.П.Васильеву, Е.Г.Голыитейну, В.Ф.Демьянову, Ю.Г.Евтушенко, Ю.М. Ермольеву, А.Д.Иоффе, В.Г.Карманову, Б.С.Мордуховичу, А.С.Немировскому, Б.Т.Поляку, P.A.Поляку, Б.Н.Пшеничному, А.М.Рубинову, В.М.Тихомирову, Л.Г.Хачияну, Н.З.Шору, Д.Б.Юдину, и другим (см., например, [7, 8, 9, 11, 12, 50, 14, 23, 24, 117]). Результаты по теории сложности экстремальных задач могут рассматриваться как естественное развитие традиций, заложенных еще Л.В.Канторовичем [61].

Однако начиная с выдающейся работы Н.Кармаркара, опубликованной в 1985г., и примерно до 2000г. развитие теории и методов оптимизации было в основном связано с прогрессом в теории полиномиальных методов внутренней точки. Были получены новые и очень эффективные методы решения задач линейного программирования, которые существенно подняли планку соревнования с традиционным симплекс-методом. Была разработана общая теория самосогласованных функций [95], которая позволяла строить полиномиальные методы внутренней точки для всех выпуклых задач с явной структурой.

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

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

Цели и задачи

В связи с этим в начале 2000х годов встал вопрос о частичной реабилитации почти забытых методов градиентного типа. Однако полностью вернуться на позиции середины 80х годов оказалось невозможным. Дело в том, что к 1985г. теория методов выпуклой оптимизации представляла собой цельный монолит [24], завершенный в основном усилиями А.С.Немировского и Д.Б.Юдина. Разработанная ими теория сложности [79], дающая верхние оценки на возможную эффективность методов минимизации для различных классов задач, была подкреплена оптимальными методами, которые эти оценки как раз и реализовывали. Предположения их вычислительной модели (оракул типа черный ящик) полностью соответствовали существовавшему тогда стилю написания оптимизационных пакетов программ, где пользователю предлагалось написать подпрограмму вычислеиия значения функции и градиента, закрытую для самого пакета [12]. Таким образом, в то время казалось, что все важные вопросы в этой области были уже заданы и (почти) все отвечены.

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

не были черноящичными.

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

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

Новизна, методология и методы исследования

• Дикинский эллипсоид. Этот эллипсоид, определяемый гессианом самосогласованной функции лежит в допустимой области.

• Аппроксимация 1го порядка. Для функции f{x), чей градиент удовлетворяет условию Липшица с константой Ь, можно написать следующую аппроксимацию:

/Ы < /(х) + (Ч/(х),у-х) + ±Ц\у-х\\2.

Минимизируя эту аппроксимацию на допустимом множестве можно улучшить значение целевой функции.

• Аппроксимация 2го порядка. Для функции /(ж), у которой гессиан является липпш-цевым с константой , верна верхняя оценка

Ду) < /(.х) + (У/(х),у-.т) + |(У2/(.т)(у-.г),у-.х) + |М||у-.т||3.

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

• Верхняя аппроксимация для системы уравнении. Для уравнения -Г(.т) = 0, где отображение F : Кп —» Мт имеет Липшицев якобиан VF с константой М, можно написать верхнюю оценку

|Щу)|| < \\Е{х) + УГ{х){у-х)\\ + \М\\у-х\\\ Минимизация этой оценки дает модифицированный метод Гаусса-Ньютона.

2. Алгебраические модели. В них описывается конкретный способ представления целевой функции. Для выпуклых функций естественной формой представления является максимум (дискретный или непрерывный) выпуклых функций. Например, может случиться что нам известно следующее представление:

/(.т) = тах{(Ах,и) — ф(и)}.

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

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

• Прямо-двойственные субградиептные методы для решения негладких выпуклых задач (параграфы 2.1, 2.2 ).

• Методы минимизации составных функций (параграф 2.3).

• Методы решения вариационных неравенств (Глава 3).

• Методы второго порядка (Глава 4).

• Алгоритмы техники сглаживания (Глава 5).

• Методы для нахождения решений выпуклых задач с относительной точностью (Глава 6).

Теоретическая и практическая значимость работы

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

• вычисление дополнительных характеристик решения (например, наряду с прямым решением, аппроксимируется также и решение двойственной задачи, или производится контроль точности решения);

• обладают гарантиями глобальной эффективности (например, новые методы второго порядка);

• сходятся быстрее, чем разрешает стандартная теория сложности (например, алгоритмы техники сглаживания).

Положения выносимые на защиту

• Прямо-двойственные методы для минимизации негладких функций. Обладают неулуч-шаемой оценкой �