Введение в выпуклую оптимизацию

Ю. Е. Нестеров

Введение
в выпуклую оптимизацию

Редакторы Б. Т. Поляк, С. А. Назин

Электронное издание

Издательство МЦНМО, Москва, 

УДК .
ББК .
Н

Нестеров Ю. Е.
Введение в выпуклую оптимизацию
Электронное издание
М.: МЦНМО, 
 с.
ISBN ----

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

Подготовлено на основе книги: Нестеров Ю. Е. Введение в выпуклую оптимизацию / Под ред. Б. Т. Поляка, С. А. Назина. –– М.:
МЦНМО, .

Издательство Московского центра
непрерывного математического образования
, Москва, Большой Власьевский пер., ,
тел. ()   .
http://www.mccme.ru

ISBN ----
© Нестеров Ю. Е., .
© МЦНМО, .

Оглавление

Предисловие


Благодарности


Введение



Нелинейная оптимизация

§ ..
Задачи нелинейной оптимизации
. . . . . . . . . . . . . .

...
Общая формулировка задачи
. . . . . . . . . . . . . . . .

...
Эффективность численных методов . . . . . . . . . . . .

...
Оценки вычислительной сложности задач глобальной оптимизации . . . . . . . . . . . . . . . . . . . . . . . .

...
Визитные карточки областей оптимизации . . . . . . .

§ .. Локальные методы безусловной оптимизации . . . . . .

...
Релаксация и аппроксимация . . . . . . . . . . . . . . . .

... Классы дифференцируемых функций . . . . . . . . . . .

... Градиентный метод . . . . . . . . . . . . . . . . . . . . . . .

... Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . .

§ .. Методы первого порядка в нелинейной оптимизации .

...
Градиентный метод и метод Ньютона: в чем разница?

... Сопряженные градиенты . . . . . . . . . . . . . . . . . . .

... Условная минимизация . . . . . . . . . . . . . . . . . . . .



Гладкая выпуклая оптимизация

§ .. Минимизация гладких функций . . . . . . . . . . . . . . . .

...
Гладкие выпуклые функции
. . . . . . . . . . . . . . . . .

... Нижние границы аналитической сложности
для класса ∞, 
L
(n) . . . . . . . . . . . . . . . . . . . . . .


Оглавление

... Сильно выпуклые функции . . . . . . . . . . . . . . . . . .

... Нижние границы аналитической сложности
для класса ∞,1
µ,L (n) . . . . . . . . . . . . . . . . . . . . . .

... Градиентный метод . . . . . . . . . . . . . . . . . . . . . . .

§ .. Оптимальные методы . . . . . . . . . . . . . . . . . . . . . . .

... Оптимальные методы
. . . . . . . . . . . . . . . . . . . . .

... Выпуклые множества . . . . . . . . . . . . . . . . . . . . . .

... Градиентное отображение . . . . . . . . . . . . . . . . . .

... Методы минимизации на простых множествах
. . . .

§ .. Задача минимизации функций с гладкими компонентами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
... Минимаксная задача . . . . . . . . . . . . . . . . . . . . . . 
... Градиентное отображение . . . . . . . . . . . . . . . . . . 
... Методы минимизации для минимаксной задачи . . . . 
... Оптимизация при функциональных ограничениях . . 
... Метод условной минимизации
. . . . . . . . . . . . . . . 


Негладкая выпуклая оптимизация

§ .. Выпуклые функции общего вида . . . . . . . . . . . . . . .

...
Мотивировка и определения . . . . . . . . . . . . . . . . .

... Операции с выпуклыми функциями . . . . . . . . . . . . 
... Непрерывность и дифференцируемость
. . . . . . . . .

... Теоремы отделимости . . . . . . . . . . . . . . . . . . . . . 
... Субградиенты . . . . . . . . . . . . . . . . . . . . . . . . . . . 
... Вычисление субградиентов . . . . . . . . . . . . . . . . . .

§ .. Методы негладкой минимизации . . . . . . . . . . . . . . . 
... Нижние границы сложности для общего случая . . . . 
... Основная лемма . . . . . . . . . . . . . . . . . . . . . . . . .

... Субградиентный метод
. . . . . . . . . . . . . . . . . . . . 
... Минимизация при функциональных ограничениях . . 
... Границы сложности в конечномерном случае
. . . . . 
... Методы отсекающей гиперплоскости . . . . . . . . . . . 
§ .. Методы с полной информацией . . . . . . . . . . . . . . . .

... Модель негладкой функции . . . . . . . . . . . . . . . . . .

... Метод Келли . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
... Метод уровней . . . . . . . . . . . . . . . . . . . . . . . . . . 
... Условная минимизация . . . . . . . . . . . . . . . . . . . . 



Оглавление


Структурная оптимизация

§ .. Самосогласованные функции
. . . . . . . . . . . . . . . . . 
...
Концепция «черного ящика» в выпуклой оптимизации 
... Как работает метод Ньютона? . . . . . . . . . . . . . . . . 
... Определение самосогласованной функции
. . . . . . . 
... Основные неравенства . . . . . . . . . . . . . . . . . . . . . 
... Минимизация самосогласованных функций . . . . . . . 
§ .. Самосогласованные барьеры . . . . . . . . . . . . . . . . . . 
... Мотивировка . . . . . . . . . . . . . . . . . . . . . . . . . . . 
... Определение самосогласованных барьеров . . . . . . . 
... Основные неравенства . . . . . . . . . . . . . . . . . . . . . 
... Метод отслеживания траектории . . . . . . . . . . . . . . 
... Нахождение аналитического центра . . . . . . . . . . . . 
... Задачи с функциональными ограничениями . . . . . . 
§ .. Приложения структурной оптимизации . . . . . . . . . . 
... Границы параметров самосогласованных барьеров . . 
... Линейная и квадратичная оптимизация . . . . . . . . . 
... Полуопределенная оптимизация . . . . . . . . . . . . . . 
... Экстремальные эллипсоиды . . . . . . . . . . . . . . . . . 
... Сепарабельная оптимизация . . . . . . . . . . . . . . . . . 
... Выбор схемы минимизации . . . . . . . . . . . . . . . . . 

Библиографический комментарий


Литература




Предисловие редактора

Новая эра в нелинейной оптимизации открылась выдающейся статьей Н. Кармаркара, появившейся в середине -х гг. Значение этой
работы, в которой предлагался новый полиномиальный алгоритм для
задач линейной оптимизации, состояло не только в установлении
границ вычислительной сложности. В то время совершенно замечательной особенностью этого алгоритма являлось то, что теоретические оценки его высокой эффективности блестяще подтверждались
результатами численных экспериментов. Этот необычный по тем временам факт радикально изменил стиль и направление исследований
в области нелинейной оптимизации.
С тех пор появление новых методов все чаще стало сопровождаться теоретическим анализом их вычислительной сложности, который
теперь обычно рассматривается как более веское доказательство их
качества, чем численные эксперименты. В новой и быстро развивающейся области оптимизации, получившей название полиномиальные
методы внутренней точки, такое обоснование стало обязательной
нормой.
Основные результаты первых пятнадцати лет серьезных исследований вошли в монографии [, , ––]. Однако эти книги труднодоступны российскому читателю. Более того, они не решают задачи
изложения нового взгляда на предмет и цели выпуклой оптимизации. Дело в том, что к тому времени лишь теория методов внутренней точки для задач линейной оптимизации была разработана
достаточно подробно, а общая теория самосогласованных функций
существовала в печатном виде лишь в форме монографии []. Кроме того, было понятно, что новая теория методов внутренней точки
представляет собой только часть общей теории выпуклой оптимизации –– технически довольно сложной дисциплины, включающей
такие разделы, как границы вычислительной сложности, оптимальные методы и т. д.

Предисловие

Автор настоящей книги, предлагаемой вниманию читателя, предпринял попытку преодолеть все эти трудности и изложить сложные
вопросы в элементарной форме. На мой взгляд, попытка оказалась
успешной. Ю. Е. Нестеров внес выдающийся вклад в развитие современной теории и методов выпуклой оптимизации. Еще в -е годы
прошлого века он развил теорию эффективных методов оптимизации; см. []. Позже он совместно с А. С. Немировским предложил
новый подход, основанный на самосогласованных функциях и барьерах (см. []), что привело к созданию полиномиальных методов
оптимизации. В последние годы он опубликовал много работ, посвященных усовершенствованию методов для основных классов
оптимизационных задач. Это помогло ему умело произвести отбор
материала для книги. Ключевыми стали такие понятия, как вычислительная сложность оптимизационных задач и гарантированная
эффективность численных методов, подкрепленная анализом границ сложности. При этом жесткие рамки объема книги обусловили
прагматизм изложения –– каждое понятие или факт, приводимые
в монографии, абсолютно необходимы для полноценного анализа
по крайней мере одной оптимизационной схемы. До некоторой степени удивительным оказалось то, что при изложении совершенно
не потребовалось сведений из теории двойственности, и поэтому
этот раздел полностью опущен. Основная цель книги –– добиться
правильного понимания сложности различных задач оптимизации, и цель эта выбрана не случайно. Пользователи постоянно
интересуются тем, какой численный метод наиболее разумен для
оптимизационных моделей, которыми они заняты. Оказывается, если модель построена без учета возможностей численных процедур,
то шансы найти приемлемое численное решение близки к нулю.
Что бы ни создавал человек в любой области своей деятельности,
он знает заранее, почему действует так, а не иначе, и
что собирается делать с тем, что получится. И лишь в области численного
моделирования картина почему-то совершенно иная: сначала создается модель, а затем начинаются поиски численного метода.
Если учесть сложность оптимизационных задач, становится ясно,
что шансы на успех при таком подходе крайне невелики.
Книга состоит из четырех глав, которые в большой степени независимы друг от друга и могут использоваться самостоятельно. Книга рассчитана на широкую аудиторию; от читателя предполагаются



Предисловие

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

Английский вариант книги (Nesterov Yu. «Introductory lectures on
convex optimization: a basic course») был выпущен издательством
Kluwer в  г. и встретил заинтересованный отклик. Я надеюсь,
что издание монографии Ю. Е. Нестерова на русском языке будет
заметным событием и даст возможность российским читателям
впервые познакомиться с новым перспективным направлением
исследований.

Б. Т. Поляк



Моей жене Светлане

Благодарности

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

Благодарности

В конце концов мне повезло обосноваться в Центре исследования
операций и эконометрики (CORE) в Лёвен-ла-Нёв, Бельгия, который при ближайшем рассмотрении оказался миниатюрной копией моего родного института ЦЭМИ РАН (Москва). Замечательные
условия работы в этом научном центре и исключительное окружение помогали мне все эти годы. Трудно переоценить значение той
атмосферы научных исследований, которую продолжают неустанно поддерживать мои коллеги из CORE и Центра системных исследований и прикладной механики (CESAME): Винсент Блондель, Ив
Жене, Мишель Геверс, Этьен Лут, Ив Поше, Ив Смеерс, Поль ван Доорен, Лоуренс Вулси. Моя работа в течение многих лет финансировались Бельгийской общенациональной программой по развитию
фундаментальных исследований, созданной по инициативе правительства Бельгии и Комитета по научной политике.
Я признателен Б. Т. Поляку и Московскому центру непрерывного математического образования за смелую инициативу перевода
и издания этой книги на русском языке.



Введение

Задачи оптимизации совершенно естественно возникают в различных прикладных областях. Во многих жизненных ситуациях
у нас появляется желание или необходимость организовать свою
деятельность наилучшим из возможных способов. Это намерение,
облеченное в математическую форму, приобретает вид той или
иной оптимизационной задачи. В зависимости от конкретной области приложения это может быть задача оптимального управления
или задача оптимального размещения, составление оптимальной
диеты или задача оптимального раскроя. Однако уже следующий
шаг –– нахождение решения поставленной модельной задачи –– совсем нетривиален. На первый взгляд, все выглядит просто: на рынке
имеется огромное количество легкодоступных коммерческих программных оптимизационных пакетов, и любой пользователь может
получить «решение» задачи простым нажатием на иконку на экране
своего персонального компьютера. Вопрос заключается в том, что
именно он получит в качестве решения и насколько можно доверять
результату.
Одна из целей данной книги –– показать, что, несмотря на всю
свою привлекательность, «решения» общих оптимизационных задач, получаемые таким образом, очень часто не соответствуют
ожиданиям доверчивого пользователя. На мой взгляд, главное, что
следует знать каждому работающему с оптимизационными моделями, –– это то, что задачи оптимизации, вообще говоря, численно
неразрешимы. Это утверждение, часто не упоминаемое в стандартных курсах по оптимизации, крайне необходимо для понимания
теории оптимизации и ее развития как в прошлом, так и в будущем.
Во многих практических приложениях процесс формализации
и приведения реальной проблемы к какому-либо стандарному виду требует большого времени и усилий. Поэтому исследователь
должен иметь ясное представление о свойствах модели, которую