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

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

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

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

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

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

МОСКВА - 2013

Работа выполнена в Лаборатории структурных методов

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

Официальные оппоненты: доктор физико-математических наук, профессор, академик РАН Евтушенко Юрий Гаврилович, Вычислительный центр им. А.А. Дородницына РАН, директор доктор физико-математических наук, профессор Тихомиров Владимир Михайлович, кафедра оптимального управления механико-математического факультета МГУ им. М.В.Ломоносова, профессор доктор технических наук Горнов Александр Юрьевич, лаборатория оптимального управления Института динамики систем и теории управления Сибирского отделения РАН, главный научный сотрудник

Ведущая организация: Институт проблем управления им. В.А.Трапезникова РАН

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

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

Автореферат разослан " " 2013 г.

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

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

Актуальность темы и степень ее разработанности Настоящая диссертация посвящена разработке новых методов решения нелинейных выпуклых задач оптимизации. Теория методов оптимизации является одной из самых востребованных областей численного анализа.

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

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

Однако, начиная с выдающейся работы Н.Кармаркара, опубликованной в 1985 г., и примерно до 2000 г. развитие теории и методов оптимизации Рокафеллар Р.Т. Выпуклый анализ. - М.: Мир, 1973 - 420с.

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

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

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

Может быть, даже более важным чем результаты предварительных численных экспериментов.

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

Цели и задачи В связи с этим в начале 2000х годов встал вопрос о частичной реабилитации почти забытых методов градиентного типа. Однако полностью вернуться на позиции середины 80х годов оказалось невозможным. Дело в том, Nesterov Yu., Nemirovskii A. Interior point polynomial methods in convex programming: Theory and Applications // Philadelphia: SIAM, 1994 - 520p.

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

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

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

Основной целью настоящей диссертации является разработка более мощных и быстрых методов оптимизации, которые значительно расширяют Поляк Б.Т. Введение в оптимизацию. - М.: Наука, 1983.-433.

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

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

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

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

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

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

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

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

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

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

• Верхняя аппроксимация для системы уравнений. Для уравнения F (x) = 0, где отображение F : Rn Rm имеет липшицев якобиан F с константой M, можно написать верхнюю оценку Минимизация этой оценки дает модифицированный метод ГауссаНьютона.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Положения, выносимые на защиту • Прямо-двойственные методы для минимизации негладких функций.

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

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

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

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

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

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

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

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

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

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

• Условие обратного зазора. Методы, основанные на этой интерпретации, позволяют применять технику сглаживания к более широкому классу задач, в частности включающему сильно выпуклые функции. Это улучшает оценку трудоемкости до O(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 Semidenite 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 semidenite 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 начинается с рассмотрения базовых градиентных методов, прямого и двойственного, которые применяются к задаче где Q - это выпуклое замкнутое ограниченное множество, и f CL (Q).

Обозначим через TQ (x) Q оптимальное решение следующей задачи минимизации:

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

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

Не ограничивая общности, будем считать что d(x0 ) = 0. Обозначим через брегмановское расстояние между точками x и y. Теперь мы можем определить брегмановскую проекцию:

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

Теорема 1.2.1 Пусть f CL (Q). Тогда для всех k 1 выполнено неравенство где xk = Двойственный метод пересчитывает простейшую модель целевой функции.

Инициализация: Положим 0 (x) = 1 (x0, x).

При k 0 повторяем: Вычисляем xk = arg min k (x).

Теорема 1.2.2 Пусть последовательность {xk }k0 сформирована методом (1.2.10). Обозначим yk = TQ (xk ), и yk = выполнено неравенство И, наконец, быстрый градиентный метод может рассматриваться как комбинация этих двух алгоритмов.

При k 0 повторяем следующие операции:

Вычисляем f (xk ) и f (xk ). Находим yk = TQ (xk ).

Теорема 1.2.3 Пусть последовательности и сформированы методом (1.2.18). Тогда при всех k 0 справедлива оценка Таким образом, где x - это оптимальное решение задачи (1.2.1).

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

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

Глава 2 посвящена современным методам субградиентного типа.

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

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

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

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

Лемма 2.1.15 При всех s E и 0 имеем: D (s) D + V (s).

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

Обычно, тестовые точки xi и веса i генерируются некоторым методом, а вектора (субградиенты) gi вычисляются оракулом G(·) типа черный ящик, Shor N.Z. Minimization Methods for Nondierentiable Functions. - Berlin: Springer-Verlag, 1985. - 312p.

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

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

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

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

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

Полезной является и сглаженная функция зазора При этом, для всех неотрицательных D и имеем: k (D) k (, D).

Поскольку множеств Q простое, значения функций зазора могут быть легко вычислены. При некоторых D эти значения могут быть отрицательными. Однако, если решение x нашей задачи существует, то для D d(x ) значение k (D) неотрицательно независимо от последовательностей Xk, k и Gk, используемых для его определения.

Рассмотрим теперь общую схему двойственных усреднений (ДУ).

Инициализация: Set s0 = 0 E. Choose 0 > 0.

3. Выбираем k+1 k. Полагаем xk+1 = k+1 (sk+1 ).

Теорема 2.1.30 Пусть последовательности Xk, Gk и k построены схемой (2.1.24). Тогда при всех k 0 и D 0 имеем:

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

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

Скорость роста этой последовательности оценивается так: 2k 1 k Имеются две стратегии для выбора параметров i : а) простые усреднения:

k = 1; б) взвешенные усреднения: k = g1. Приведем схему ДУ-метода для первого способа.

Инициализация: Set s0 = 0 E. Выбираем > 0.

1. Вычисляем gk = G(xk ). Set sk+1 = sk + gk.

2. Выбираем k+1 = k+1. Полагаем t xk+1 = k+1 (sk+1 ).

Теорема 2.1.31 Предположим что gk L, k 0. Для метода (2.1.31) Покажем как эта техника работает на примере задачи где f - выпуклая на E функция и множество Q является выпуклым и замкнутым. В этом случае имеется следующая интерпретация функции зазора k (D). Обозначим Поскольку функция f (·) выпукла, в силу определения функции зазора (2.1.20) имеем:

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

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

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

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

Рассмотрим другое выпуклое множество P E. Нас будет интересовать их пересечение P = P Q, которое предполагается ограниченным.

Обозначим через x0 его условный аналитический центр:

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

где > 0 - это параметр сглаживания. Обозначим через u (s) единственное решение задачи максимизации (2.2.3).

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

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

Инициализация: Полагаем s0 = 0 E.

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

соотношению ln(1 ). Тогда где c(Q) = 1 если Q является конусом и барьер F (·) логарифмически однороден. В противном случае, c(Q) = 3.

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

любого x P0.

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

Теорема 2.2.2 Пусть задача (2.2.13) с f BM (P ) решается методом (2.2.14) с параметрами заданными в (2.2.19). Тогда при любом k 0 имеем:

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

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

где норма · евклидова ( h = Bh, h 1/2, B = B T 0), а L - положительная константа (в обычном градиентном отображении (·) 0). Теперь можно определить аналог градиентного направления для гладкой функции:

Если Q E и 0, то gL (y) = (y) f (x) при любых L > 0. Наше предположение о простоте функции означает в точности реализуемость операции (2.3.10). Теперь можно определить градиентную итерацию.

Полагаем:

Повторяем:

Пока не выполнится: (T ) mL (x; T ).

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

Можно показать что Nk, общее число вызовов оракула после k итераций метода (2.3.28) не может быть большим: Nk 1 + ln u · (k + 1) + ln1u · Теорема 2.3.4 Пусть функция f выпукла на Q. Предположим что она достигает своего минимума на Q в точке x и что ее множества уровня ограничены:

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

Полагаем: L := Lk.

Найти a из квадратного уравнения Ak +a = 2 1+µAk.

Полагаем: yk := y, Mk := L, ak+1 := a, Теорема 2.3.6 Предположим что градиент функции f удовлетворяет условию Липшица с константой Lf. И пусть параметр L0 (0, Lf ). Тогда скорость сходимости метода A(x0, L0, 0) оценивается следующим образом:

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

В Главе 3 рассматриваются методы решения вариационных неравенств.

Основные результаты этой главы опубликованы в работах [13, 20].

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

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

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

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

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

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

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

(двойственную экстраполяцию). Обозначим Зафиксируем некоторые положительные значения и. Рассмотрим отображение E, (s), которое переводит произвольную точку s E в новую точку s+ :

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

Метод решения гладких вариационных неравенств Инициализация: Выбираем x Q. Фиксируем = L и выбираем D > 0.

Итерация:

Теорема 3.1.2 Пусть оператор g(x) будет липшицевым на Q. Тогда Критерий прерывания в методе (3.1.20) обеспечивает неравенство fD (k ). Это критерий будет выполнен не более чем через 1 + LD итераций.

Метод для ВН с ограниченным изменением оператора Инициализация: Выбираем x Q и D > 0. Для k 0 положим Итерация:

Теорема 3.1.3 Предположим что оператор g(x) имеет ограниченное изменение на множестве Q:

Тогда для любого k 0 имеем: fD (k ) 2M ·(k+1). Критерий прерывания в методе (3.1.23) обеспечивает выполнение неравенства fD (k ). Этот критерий сработает не более чем за 1 + 4M 2D итераций.

В заключение параграфа мы показываем как применять полученные методы для вычисления седловых точек и для решения билинейных матричных игр, В параграфе 3.2 мы показываем как решать сильно монотонные ВН и квазивариационные неравенства. Рассмотрим непрерывный оператор g(x) :

Q E, который является сильно монотонным:

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

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

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

Инициализация: Выбираем x Q. Полагаем 0 = 1, и y0 = x.

Теорема 3.2.3 Если оператор g сильно монотонен и липшицев, то неравенства (КВН):

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

Обозначим через yN (Q, x) результат работы N -шагового метода (3.2.11), применяемого к решению ВН с оператором g на множестве Q и центральной точкой x = arg max x (x). Обозначим = 1 и предположим что оно положительно. Зададим Noor M. A., Oettli W. On general nonlinear complementarity problems and quasi-equilibria // Le Matematiche - 1994 - V.XLIX - 313-331p.

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

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

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

В параграфе 4.1 описывается кубическая регуляризация метода Ньютона.

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

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

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

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

Bennet A.A. Newton’s method in general analysis. // Proc. Nat. Ac. Sci. USA - 1916 - V.2, N10. - P.592–598.

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

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

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

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

Введем отображение где ”Arg” означает что TM (x) выбирается из множества глобальных минимумов соответствующей задачи минимизации. Пусть L0 (0, L] положительный параметр. Рассмотрим следующий метод.

Кубическая регуляризация метода Ньютона Инициализация: Выбираем x0 Rn.

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

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

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

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

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

Ускоренная версия кубической регляризации Инициализация: Выбираем x0 E. Полагаем M = 2L и N = 12L.

Вычисляем x1 = TL3 (x0 ) и полагаем 1 (x) = f (x1 ) + N x x0 3.

Итерация k, (k 1):

1. Вычисляем vk = arg min k (x) и полагаем yk = k+3 xk + k+3 vk.

2. Вычисляем xk+1 = TM (yk ) и пересчитываем k+1 (x) = k (x) + (k+1)(k+2) · [f (xk+1 ) + f (xk+1 ), x xk+1 ].

Теорема 4.2.2 Если последовательность точек {xk } сформирована методом (4.2.28), то для любого k 1 выполняется неравенство:

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

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

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

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

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

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

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

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

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

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

В параграфе 5.1 рассматривается задача минимизации Ortega J., Rheinboldt W. Iterative Solution of Nonlinear Equations in Several Variables. - NY: Academic Press, 1970. - 630p.

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

где выпуклое замкнутое множество Q1 в конечномерном вещественном пространстве E1 является ограниченным, а выпуклая функция f (x) непрерывна на Q1. Очень часто известна структура целевой функции в задаче (5.1.3):

где выпуклая функция f (x) непрерывна на Q1, выпуклое замкнутое множество Q2 из конечномерного вещественного пространства E ограничено, выпуклая функция (u) непрерывна на Q2, а линейный оператор A отображает E1 в E2. В этом случае задача (5.1.3) может быть переписана в сопряженной форме:

Рассмотрим прокс-функцию d2 (u) множества Q2 с параметром выпуклости 2 = 1. Обозначим через ее прокс-центр. И пусть d2 (u0 ) = 0. Выберем положительное µ в качестве параметра сглаживания. Рассмотрим следующую функцию:

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

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

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

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

Пользуясь обозначениями §5.1, заметим что при любых x Q1 и u Q выполняется неравенство Более того, при естественных предположениях в задачах (5.1.3), (5.1.5) будет нулевой зазор двойственности. Однако, fµ2 (x) f (x) и (u) µ1 (u). Такая ситуация открывает принципиальную возможность обеспечить выполнение условия обратного зазора:

при некоторых x Q1 и u Q2. Ясно что из условия (5.2.13) нетрудно получить оценку качества соответствующей прямо-двойственной пары (, u):

где D1 = max d1 (x), и D2 = max d2 (u).

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

Для x Q1 определим прямое градиентное отображение:

Теорема 5.2.1 Пусть точки x Q1 и u Q2 удовлетворяют условию обратного зазора (5.2.13) при некоторых положительных µ1 и µ2.

Зафиксируем (0, 1) и выберем µ+ = (1 )µ1, Тогда пара (+, u+ ) удовлетворяет условию (5.2.13) с параметрами сглаживания µ+ и µ2 при всех не слишком больших :

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

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

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

Пусть функция одной вещественной переменной f ( ) задана рядом с ak 0 при k 2. Предположим что ее область определения dom f = { :

| | < R} не пуста. Для симметрической матрицы X рассмотрим следующую симметричную функцию собственных значений:

Ясно что dom F = {X Sn : max (X) < R, min (X) > R}.

Теорема 5.3.1 Для любого X dom F и H Sn имеем С помощью этого факта можно оценивать степень гладкости различных симметричных функций собственных значений. Приведем два примера.

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

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

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

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

Соответствующие результаты опубликованы в статьях [15, 17].

В параграфе 6.1 рассматривается коническая задача безусловной минимизации где выпуклая функция f (x) является однородной степени единица, C - это p n-матрица, и b = 0. Основное предположение о задаче (6.1.1) выглядит так:

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

Зафиксируем некоторую норму параметры 0 1 удовлетворяют следующему условию:

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

Обозначим через x0 проекцию начала координат на аффинное подпространство L относительно нормы · :

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

Теорема 6.1. 1. Для любого x Rn имеем Таким образом, функция f (x) липшицева на Rn относительно нормы · с константой 1. Более того, 2. Для любого оптимального решения x задачи (6.1.1) имеем:

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

Теорема 6.1.2 Для фиксированного из (0, 1) выберем Тогда f (GN ()) (1 + ) · f.

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

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

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

Последняя из этих точек удовлетворяет неравенству f (T ) (1 + )f.

Общее число градиентных шагов в процессах нижнего уровня (6.1.14) не превосходит В заключительной части этого параграфа мы показываем как можно еще снизить трудоемкость получения -решения в случае когда целевая функция является составной. А именно, мы предполагаем что f (x) = F (A(x)), где A(x) - линейный оператор, а F (v) - простая нелинейная выпуклая однородная функции. Тогда, комбинируя операцию сглаживания с применением быстрого градиентного метода, можно добиться трудоемкости O(1/) (см. теорему 6.1.5).

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

Эллипсоиды Wr (v, G) E представляются в следующей форме:

0 - линейный оператор из E в E. Если v = 0, то мы переходим где G к обозначению Wr (G). Эллипсоид W1 (v, G) называется -аппроксимацией выпуклого множества C E, ( 1) если Параметр называется радиусом эллипсоидальной аппроксимации.

Сначала приводятся алгоритмы, работающие с центральносимметричными телами и с выпуклыми телами общего вида, близкие к алгоритму Хачияна18. Доказывается что они получают приемлемую аппроксимацию за O(n) шагов, где n - размерность пространства. Далее мы рассматриваем знако-инвариантные тела. Показывается, что они допускают O(n1/2 )-аппроксимацию, которая обеспечивается диагональной матрицей.

Нахождение такой матрицы также требует O(n) итераций.

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

В заключении приводятся основные результаты и выводы диссертации.

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

Более того, мы показали, что информация, полученная из "черного ящика позволяет ускорять эти методы, превышая даже максимально возможные скорости, полученные в теории сложности. По-видимому, в Khachiyan L.G. Rounding of polytopes in the real number model of computation. // Mathematics of Operations Research - 1996 - V.21, N2. - P.307-320.

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

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

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

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

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

174-176.

4. Нестеров Ю.Е. Полиномиальные методы для задач линейного и квадратичного программирования // Известия АН СССР - 1988 - вып. 5. Нестеров Ю.Е. Об одном подходе к разработке оптимальных методов минимизации гладких выпуклых функций // Экономика и мат.методы - 1988 - Т.24, вып.3 - С. 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 semidenite 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. Modied 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 ecient gradient methods for linear programming problems // Optimization Methods and Software - - 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.159Nesterov 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 quasivariational inequalities // Discrete and Continuous Dynamical Systems V.31, N4. - P.1383-1296.

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

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

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

АВТОРЕФЕРАТ

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