Convex optimization

Введение

Данное пособие написано на основе лекций, которые авторы читали в разное время в Физтех-школе ПМИ МФТИ (Москва), ФКН ВШЭ (Москва), ДВФУ (Владивосток), КФУ имени В.И. Вернадского (Симферополь), АГУ (республика Адыгея), университете Гренобль-Альпы (Гренобль, Франция).

В первую очередь при написании пособия авторы ориентировались на программу двухсеместрового курса лекций по оптимизации, который читается студентам Физтех-школы ПМИ МФТИ. Первая глава пособия содержит материалы первого семестра (<<Основы выпуклого анализа и оптимизации>>), вторая и третья главы — материалы второго семестра (<<Численные методы выпуклой оптимизации>>). В пособие не вошли некоторые материалы, которые включают сейчас в лекции второго семестра (например, элементы невыпуклой оптимизации и стохастической оптимизации). Эти материалы подробно изложены в книге , более точно заточенной на программу второго семестра университетского курса по методам оптимизации.

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

Авторы выражают благодарность за помощь в оформлении данного пособия студентам кафедры математических методов в экономике ДВФУ Владиславу Хазову, Марии Рудь, Алексею Луценко, Валерии Волосевич, Екатерине Шавыровой, Алине Влучко, Марии Романовой, Екатерине Маникаевой, Валентине Шальтис, студентам кафедры алгебры и функционального анализа КФУ им. В.И. Вернадского Сейдамету Аблаеву и Константину Алексееву, а также старшему преподавателю кафедры алгебры и функционального анализа КФУ им. В.И. Вернадского Инне Баран.

Ряд ценных замечаний был получен от Дарины Двинских (МФТИ, Институт Вейерштрасса, ИППИ РАН), Анастасии Ивановой (ВШЭ, университет Гренобль-Альпы), Адриена Тейлора (INRIA), Павла Двуреченского (Институт Вейерштрасса, МФТИ, ИППИ РАН), Александра Тюрина (Научно-технологический университет имени короля Абдаллы, Саудовская Аравия), Aлександра Титова (МФТИ), Дмитрия Пасечнюка (МФТИ) и Артема Комарова (МФТИ). Также хотелось бы выразить благодарность профессору Е. А. Нурминскому (ДВФУ, Владивосток), профессору А. С. Немировскому (Технологический институт Джорджии, Атланта, США), профессору Б. Т. Поляку (ИПУ РАН, Москва), профессору Б. Ш. Мордуховичу (университет Уэйна, США) и профессору А. В. Назину (МФТИ).

Работа Е. А. Воронцовой и Ф. С. Стонякина над пособием была поддержана грантом РФФИ 18-29-03071 мк. Работа А. В. Гасникова над пособием была выполнена при поддержке Министерства науки и высшего образования Российской Федерации (госзадание) № 075-00337-20-03, номер проекта 0714-2020-0005.

Если вы обнаружили какие-либо опечатки, ошибки или неточности в данном пособии, большая просьба сообщить о них по адресу vorontsovaea@gmail.com.

Обозначения и сокращения

В пособии используются следующие сокращения:

БШС — модель вычислений Блюм–Шуба–Смейла;

$\displaystyle\boldsymbol{1}$ — вектор из единиц;

$\displaystyle\|a\|_{\infty}=\max\limits_{i}|a_{i}|$ — бесконечная норма вектора $\displaystyle a$;

$\displaystyle A\succ 0$ — матрица $\displaystyle A$ – положительно определена;

$\displaystyle A\succeq 0$ — матрица $\displaystyle A$ – неотрицательно определена;

$\displaystyle A\prec 0$ — матрица $\displaystyle A$ – отрицательно определена;

$\displaystyle\textnormal{Arg}\min_{x\in Q}\psi(x)$ — множество точек минимума $\displaystyle\psi(x)$ на множестве $\displaystyle Q$;

$\displaystyle\arg\min_{x\in Q}\psi(x)$ — некоторый элемент множества $\displaystyle\textnormal{Arg}\min_{x\in Q}\psi(x)$;

$\displaystyle\mbox{conv }M$ — выпуклая оболочка множества $\displaystyle M$;

$\displaystyle\text{diag}(x)$ — диагональная матрица с компонентами вектора $\displaystyle x$ на диагонали;

$\displaystyle\dim\,x$ — размерность объекта $\displaystyle x$;

$\displaystyle\text{dom }f$ — область определения функции $\displaystyle f$;

$\displaystyle F[x]$ — кольцо многочленов от конечного числа переменных с коэффициентами из поля $\displaystyle F$;

$\displaystyle\mbox{int}\,X$, $\displaystyle X^{o}$ — внутренность множества $\displaystyle X$;

$\displaystyle nnz\left(A\right)$ — число ненулевых элементов в матрице $\displaystyle A$;

$\displaystyle O(n)$ — неотрицательная функция от $\displaystyle n$, которую можно ограничить сверху $\displaystyle Cn$, где $\displaystyle C$ – числовая константа;

$\displaystyle\text{rank }A$ — ранг матрицы $\displaystyle A$;

$\displaystyle\text{Tr}(A)$ — след квадратной матрицы $\displaystyle A$, т.е. сумма диагональных элементов $\displaystyle A$;

$\displaystyle\lambda_{\max}\left(A\right)$ — максимальное собственное значение матрицы $\displaystyle A$.

Глава 1 Основы выпуклого анализа

В данной главе рассматриваются в основном задачи выпуклой оптимизации (минимизации выпуклой функции на выпуклом множестве). Описан принцип множителей Лагранжа как следствие теоремы об <<отделимости>> граничной точки выпуклого множества от самого множества (опорной) гиперплоскостью. При этом конечномерность пространств не предполагается, см., например, обоснование с помощью принципа множителей Лагранжа леммы Неймана–Пирсона в разделе 11 (основной леммы в проверке статистических гипотез). Обсуждаются различные моменты, которые активно используются при разработке эффективных численных методов решения задач выпуклой оптимизации (и их удобных переформулировок), о чём пойдёт речь в том числе и в последующих главах. Особенно отметим: теорему фон Неймана–Сиона–Какутани в разделе 9.10 ($\displaystyle\min\max=\max\min$), теорему (формулу) Демьянова–Данскина–Рубинова о дифференцировании под знаком максимума (минимума) в разделе 6, теорию двойственности в разделе 9 и теоремы об альтернативах в разделе 12. Отличительной особенностью материала данной главы от содержания многих других русскоязычных учебных пособий по выпуклой оптимизации является наличие заключительных разделов, которые содержат весьма продвинутый материал. Если коническое программирование уже достаточно прочно вошло в различные западные курсы по выпуклой оптимизации, то робастную оптимизацию, насколько нам известно, в основном излагают только в виде отдельных спецкурсов. В этом пособии мы, следуя А. С. Немировскому, стараемся продемонстрировать, что именно такие приложения позволяют по-настоящему прочувствовать все возможности арсенала современной выпуклой оптимизации.

Для более глубокого погружения в затронутые в данной главе вопросы можно рекомендовать замечательные книги по выпуклой оптимизации В. М. Тихомирова, А. С. Немировского У Владимира Михайловича Тихомирова и у Аркадия Семёновича Немировского довольно много разных книг на тему выпуклой оптимизации, см., например, . У ВладимираМихайловича акцент делается на общих вопросах выпуклого анализа, у Аркадия Семёновича — на вычислительных. В совокупности это в хорошей степени покрывает материал, отвечающий глубокому изучению данного курса. и, конечно, книгу Стивена Бойда и Ливена Ванденберга , которую можно рекомендовать всем желающим разобраться в том, что такое <<выпуклая оптимизация>>. Вот уже почти 20 лет эта книга служит непревзойдённым по доступности изложения источником базовых фактов о выпуклой оптимизации. Также можно порекомендовать книги Ю. Е. Нестерова , Б. Н. Пшеничного , Б. Т. Поляка .

В этом параграфе собраны некоторые определения и факты , которые необходимы для доказательства теорем, представленных далее.

Векторное пространство $\displaystyle X$ называется вещественным нормированным пространством, если каждому элементу $\displaystyle x\,\in\,X$ сопоставлено вещественное число $\displaystyle\|x\|_{X}$, называемое нормой $\displaystyle x$, которое удовлетворяет условиям:

невырожденность: для любого $\displaystyle x\in X$ имеем $\displaystyle\|x\|_{X}\geqslant 0$ и $\displaystyle\|x\|_{X}=0$ тогда и только тогда, когда $\displaystyle x=0$;

неравенство треугольника: для любых $\displaystyle x,\,y\in X$ имеем $\displaystyle\|x+y\|_{X}\leqslant\linebreak\leqslant\|x\|_{X}+\|y\|_{X}$.

Евклидова норма вектора $\displaystyle x=(x_{1},\,x_{2},\,...,\,x_{n})$ (её также называют квадратичной) определяется как

Неравенство треугольника для евклидовой нормы называется неравенством Коши–Буняковского, оно же в нерусскоязычной литературе называется неравенством Коши–Шварца (Cauchy–Schwarz inequality). Действительно, возьмём два ненулевых неколлинеарных вектора $\displaystyle x$, $\displaystyle y$ в векторном пространстве $\displaystyle X$ с положительно определённым скалярным произведением $\displaystyle x^{T}y$. Неравенство треугольника для пространства $\displaystyle X$ записывается так:

Возводим обе части (1) в квадрат и раскрываем скобки, тогда получим эквивалентное утверждение

не имеет корней, следовательно, его дискриминант $\displaystyle 4(x^{T}y)^{2}-4(y^{T}y)(x^{T}x)$ отрицателен, что доказывает (2).

Евклидова норма является частным случаем векторной нормы Гёльдера, задаваемой выражением

Докажите, что $\displaystyle\max$-норма действительно является нормой.

Упомянутые Вообще говоря, не только упомянутые нормы, но и абсолютно все на конечномерном пространстве. векторные нормы эквивалентны Две нормы $\displaystyle\|\cdot\|_{k_{1}}$ и $\displaystyle\|\cdot\|_{k_{2}}$ в пространстве $\displaystyle X$ называются эквивалентными, если существуют такие положительные числа $\displaystyle C_{1}$ и $\displaystyle C_{2}$, что для любого $\displaystyle x\,\in\,X$ выполнены неравенства $\displaystyle C_{1}\|x\|_{k_{1}}\leq\linebreak\leq\|x\|_{k_{2}}\leq C_{2}\|x\|_{k_{1}}$. на конечномерном пространстве.

Норма на пространстве $\displaystyle X$ задаёт метрику (расстояние между элементами $\displaystyle x$ и $\displaystyle y$) по формуле $\displaystyle\|x-y\|_{X}$ при $\displaystyle x,\,y\,\in\,X$.

Расстоянием от точки $\displaystyle a\,\in\,X$ до множества $\displaystyle B\subset X$ называется величина $\displaystyle\inf\limits_{x\,\in\,B}\|x-a\|_{X}$.

Пусть $\displaystyle Q\subset X$. Точка $\displaystyle x\,\in\,Q$ называется внутренней точкой $\displaystyle Q$, если она входит в $\displaystyle Q$ вместе с некоторой окрестностью с центром в $\displaystyle x$. Множество внутренних точек множества $\displaystyle Q$ называется внутренностью $\displaystyle Q$ и обозначается $\displaystyle\mbox{int}\,Q$ или $\displaystyle Q^{o}$.

Множество $\displaystyle Q$ называется открытым, если $\displaystyle\mbox{int}\,Q=Q$.

Точка $\displaystyle x^{*}\,\in\,X$ называется граничной точкой множества $\displaystyle Q$, если в любой окрестности точки $\displaystyle x^{*}$ содержатся точки как из множества $\displaystyle Q$, так и из его дополнения. Множество называется замкнутым, если ему принадлежат все граничные точки. Известно, что дополнение к замкнутому множеству является открытым. И наоборот, дополнение к открытому множеству является замкнутым.

Выпуклые множества и выпуклые функции

Выпуклый анализ --- раздел математики, в котором изучают выпуклые множества, выпуклые функции и выпуклые экстремальные задачи. Исторические корни понятия выпуклости уходят в античные времена. Определение выпуклой кривой присутствует, например, в сочинениях Архимеда (III век до н.э.). В дальнейшем активное изучение выпуклых фигур началось в XIX веке, в трудах О. Коши (один из первых результатов --- теорема Коши о жёсткости выпуклых многогранников, 1813 год), Я. Штейнера и Г. Минковского возникла отдельная ветвь геометрии --- выпуклая геометрия. Окончательно новой областью математики выпуклая геометрия стала после выхода книги Минковского Minkowski H. Geometrie der Zahlen. Leipzig: Teubner Verlag, 1896, 1910. Последующие переиздания: New York: Chelsea, 1953; New York: Johnson, 1968.. Так были заложены геометрические основания выпуклого анализа.

В двадцатые и тридцатые годы ХХ века бурное развитие теории выпуклых множеств продолжилось. Итоги этого периода были подведены в вышедшей в 1934 году монографии немецких математиков Боннесена и Фенхеля <<Теория выпуклых тел>>. Многие значимые идеи выпуклой геометрии стали основой для важных положений функционального анализа (теоремы Хана–Банаха, Крейна–Мильмана).

Понятие выпуклости стало привлекать особое внимание исследователей в 40-е годы XX века, когда начал происходить настоящий <<выпуклый бум>>, по выражению В. М. Тихомирова [76, стр. 3], поскольку выяснилось, какую огромную роль играет выпуклость в экономических задачах, следствием решения которых стало рождение нового направления в теории экстремума — линейного программирования Подробнее о развитии линейного программирования см. п. 9.6 на с. 9.6..

Результаты первооткрывателя нетривиальных задач и теории линейного программирования Л. В. Канторовича были переоткрыты на Западе, там было осознано значение выпуклых экстремальных задач при решении актуальных проблем экономики и военно-промышленного комплекса, и многие исследователи приняли участие в развитии новой дисциплины на стыке математического анализа и геометрии. В 1951 г. выходит издание курса лекций Фенхеля по теории выпуклых функций и множеств (Fenchel W. Convex Cones, Sets and Functions. Princeton University Press, 1951). Название окончательно оформившейся новой дисциплины — выпуклый анализ — предложил профессор Принстонского университета А. У. Таккер, что описано в предисловии к подводившей итоги 20-летнего периода развития теории и вышедшей в США в 1970 г. монографии американского математика Р. Рокафеллара <<Выпуклый анализ>> . Рокафеллар был пионером в применении выпуклого анализа к оптимизации.

Множество $\displaystyle Q$ называется выпуклым, если для любых двух точек, принадлежащих этому множеству, отрезок, соединяющий эти две точки, целиком принадлежит этому множеству, т.е.

Докажите, пользуясь определением выпуклого множества, что единичный шар с центром в нуле $\displaystyle B_{\|\cdot\|}(0,\,1)$ является выпуклым.

Представим отрезок $\displaystyle[x,\,y]$ как множество точек вида $\displaystyle\alpha x+(1-\alpha)y$, $\displaystyle\alpha\,\in\,[0,\,1]$. По определению выпуклого множества при $\displaystyle x,\,y\,\in\,B_{\|\cdot\|}(0,\,1)$ все точки вида $\displaystyle\alpha x+(1-\alpha)y$, $\displaystyle\alpha\,\in\,[0,\,1]$ тоже должны принадлежать этому шару, т.е. должно выполняться неравенство $\displaystyle\|\alpha x+(1-\alpha)y\|\leq 1$. В силу неравенства треугольника для нормы и мультипликативности нормы

Поскольку $\displaystyle x$, $\displaystyle y$ принадлежат единичному шару,

Следовательно, $\displaystyle\|\alpha x+(1-\alpha)y\|\leq 1$.

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

Пересечение любой совокупности выпуклых множеств выпукло.

Геометрически неравенство Йенсена означает, что отрезок, соединяющий точки $\displaystyle(x,\,f(x))$ и $\displaystyle(y,\,f(y))$, лежит не ниже графика функции $\displaystyle f(x)$.

которое называется надграфиком $\displaystyle f$.

Иногда говорят, что функция выпукла, если её надграфик является выпуклым множеством. Оба эти определения эквивалентны.

Функция $\displaystyle f$ называется строго выпуклой, если

Функция $\displaystyle f$ называется вогнутой, если $\displaystyle-f$ — выпуклая функция, и функция $\displaystyle f$ называется строго вогнутой функцией, если $\displaystyle-f$ — строго выпуклая функция.

Анализ выпуклых функций является хорошо проработанной областью исследований. Одним из важных результатов является, например, следующий: функция $\displaystyle f$ является выпуклой тогда и только тогда, когда для всех $\displaystyle x\,\in\,\mbox{dom}\,f$ и для всех $\displaystyle v$ функция $\displaystyle g(t)=f(x+tv)$ является выпуклой на своей области определения $\displaystyle\{t\,|\,x+tv\,\in\,\mbox{dom}\,f\}$. Это полезное свойство позволяет сводить проверку на выпуклость функции многих переменных к проверке на выпуклость функции одной переменной.

Будем обозначать здесь и далее положительную определённость матрицы $\displaystyle A$ таким образом: $\displaystyle A\succ 0$. Соответственно, если матрица неотрицательно определена, обозначение следующее: $\displaystyle A\succeq 0$. И наоборот, отрицательно определённая матрица: $\displaystyle A\prec 0$.

Пусть функция $\displaystyle f$ дважды дифференцируема, т.е. её матрица вторых производных (которую называют гессиан, или матрица Гессе) $\displaystyle\nabla^{2}\,f$ существует в каждой точке области определения $\displaystyle\mbox{dom}\,f$. Тогда функция $\displaystyle f$ выпукла тогда и только тогда, когда $\displaystyle\mbox{dom}\,f$ — выпуклое множество и гессиан функции $\displaystyle f$ — неотрицательно определённая матрица:

Для функции одной переменной это условие означает, что её первая производная является неубывающей функцией на интервале $\displaystyle\mbox{dom}\,f$:

Аналогично, функция $\displaystyle f$ является вогнутой тогда и только тогда, когда $\displaystyle\mbox{dom}\,f$ — выпуклое множество и $\displaystyle\nabla^{2}\,f\,\preceq\,0$ для всех $\displaystyle x\,\in\,\mbox{dom}\,f$.

Данную функцию можно представить как максимум из всех возможных сумм $\displaystyle k$ элементов вектора $\displaystyle x$:

где $\displaystyle z=(e^{x_{1}},\,\ldots,\,e^{x_{n}})$, и здесь, и далее $\displaystyle\text{diag}(x)$ — диагональная матрица с компонентами вектора $\displaystyle x$ на главной диагонали.

Для того чтобы доказать неотрицательную определённость гессиана $\displaystyle f$, нужно воспользоваться определением неотрицательно определённой матрицы и доказать следующее свойство: для всех $\displaystyle v$ выполняется неравенство $\displaystyle v^{T}\nabla^{2}f(x)v\,\geqslant\,0$. После подстановки $\displaystyle\nabla^{2}f(x)$ из (4) получаем

Последнее неравенство следует из неравенства Коши–Буняковского:

в котором нужно взять $\displaystyle a_{i}=\sqrt{z_{i}}$, $\displaystyle b_{i}=v_{i}\sqrt{z_{i}}$.

Максимальное собственное значение симметричной матрицы как функция, определённая в пространстве симметричных матриц, является выпуклой функцией:

Ещё один неочевидный пример — функция $\displaystyle f\left(X\right)=\log\det X^{-1}$, определённая на множестве симметричных положительно определённых матриц, является выпуклой. Здесь и далее $\displaystyle\log$ обозначает логарифм числа по любому основанию. При этом $\displaystyle f\left(X\right)=\log\det X$ при $\displaystyle X\succ 0$ — вогнутая функция.

Традиционно в теории оптимизации используются условия Липшица для производных определённого порядка.

По условию $\displaystyle f^{\prime}$ ограничена. Следовательно, существует константа $\displaystyle L_{0}>0$, такая, что $\displaystyle|f^{\prime}(c)|\leq L_{0}$. Следовательно,

По сути, для $\displaystyle L_{0}$-липшицевой функции $\displaystyle L_{0}$ является показателем скорости изменения функции. Кроме того, для непрерывной по Липшицу функции всегда существует двойной конус с вершиной, которую можно перемещать по графику функции в любом направлении, но при этом для такой функции её график всегда лежит вне конуса.

Не все дифференцируемые функции являются непрерывными по Липшицу. Рассмотрим, например, дифференцируемую функцию $\displaystyle f(x)=x^{2}$:

поэтому $\displaystyle f$ не является $\displaystyle L_{0}$-липшицевой.

Дифференцируемость не является и необходимым условием липшицевости функции. Например, функция $\displaystyle f(x)=|x|$ недифференцируема, но непрерывна по Липшицу.

Докажите, что функция $\displaystyle f(x)=|x|$ непрерывна по Липшицу с $\displaystyle L_{0}=1$.

Достаточно рассмотреть обратное неравенство треугольника

Конусы и отношения порядка в евклидовых пространствах

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

Непустое множество $\displaystyle K$ называется конусом, если для любого $\displaystyle x\,\in\,K$ и $\displaystyle\lambda\,\geqslant\,0$ выполняется включение $\displaystyle\lambda x\,\in\,K$. Иными словами, множество в линейном пространстве является конусом (с вершиной в точке $\displaystyle 0$), если с каждой своей точкой оно содержит и весь луч, исходящий из начала координат и проходящий через эту точку.

Множество $\displaystyle K$ называется выпуклым конусом, если $\displaystyle K$ — конус и $\displaystyle K$ — выпуклое множество.

Луч $\displaystyle\{x_{0}+\theta v\,|\,\theta\geqslant 0\}$, где $\displaystyle v\neq 0$, является выпуклым конусом, если $\displaystyle x_{0}=0$.

у $\displaystyle K$ непустая внутренность;

$\displaystyle K$ — остроконечный, т.е. не содержит прямых:

Вместо $\displaystyle y\succeq_{K}x$ можно написать: $\displaystyle x\preceq_{K}y$. Аналогично определяется строгое обобщённое неравенство:

и вместо $\displaystyle y\succ_{K}x$ можно написать: $\displaystyle x\prec_{K}y$.

Отношение $\displaystyle\succeq_{K}$ является отношением частичного порядка со следующими свойствами:

рефлексивность: $\displaystyle\forall\,x\quad x\succeq_{K}x$;

антисимметричность: $\displaystyle\forall\,x\succeq_{K}y,\,y\succeq_{K}x\,\Rightarrow\,x=y$;

транзитивность: $\displaystyle\forall\,x\succeq_{K}y,\,y\succeq_{K}z\,\Rightarrow\,x\succeq_{K}z$;

однородность: если $\displaystyle x\succeq_{K}y$ и $\displaystyle\lambda$ — любое неотрицательное вещественное число, то $\displaystyle\lambda x\succeq_{K}\lambda y$;

аддитивность: если $\displaystyle x\succeq_{K}y$ и $\displaystyle w\succeq_{K}z$, то $\displaystyle x+w\succeq_{K}y+z$.

то же самое можно записать и так: $\displaystyle x\geqslant y$.

Часто встречается в подобных неравенствах конус Лоренца В англоязычной литературе его иногда называют ’’ice-cream cone’’ — <<конус-мороженое>>.:

Это конус симметричных матриц, все собственные значения которых неотрицательны.

Пусть $\displaystyle K\subset V$ — произвольный конус в вещественном векторном пространстве $\displaystyle V$. Двойственным (или сопряжённым) к $\displaystyle K$ конусом называется множество

Отметим, что двойственный к $\displaystyle K$ конус определён в двойственном к $\displaystyle V$ векторном пространстве. Нетрудно видеть, что имеет место включение $\displaystyle K\subset(K^{*})^{*}$.

Если $\displaystyle\mbox{int}\,K\neq\varnothing$, то $\displaystyle K^{*}$ является остроконечным конусом.

Если $\displaystyle K$ — замкнутый выпуклый остроконечный конус, то $\displaystyle\textup{\mbox{int}}\,K^{*}\neq\varnothing$.

Если $\displaystyle K$ — замкнутый конус, то сопряжённый к конусу $\displaystyle K^{*}$ совпадает с исходным:

Таким образом, если конус $\displaystyle K$ — регулярный, то двойственный конус $\displaystyle K^{*}$ также будет регулярным. Более того, в этом случае мы имеем соотношение $\displaystyle(K^{*})^{*}=K$.

Для приведённых выше семейств конусов двойственный конус совпадает с прямым, если отождествить пространства $\displaystyle V$ и $\displaystyle V^{*}$ путём отождествления канонического базиса в $\displaystyle V$ с его двойственным базисом в $\displaystyle V^{*}$. Такие конусы называются самодвойственными.

Как получать выпуклые функции?

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

Очевидно, что сумма двух выпуклых функций выпукла. Также очевидно, что если умножить выпуклую функцию $\displaystyle f$ на некоторое неотрицательное число $\displaystyle\alpha$, то полученная функция $\displaystyle\alpha f$ также выпукла. Комбинируя эти свойства, получим следующую лемму.

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

2 Аффинные преобразования аргумента

Сразу сформулируем данное свойство выпуклых функций в виде леммы.

3 Композиция, максимум и точная верхняя грань функций

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

Если $\displaystyle f_{1}$ и $\displaystyle f_{2}$ — выпуклые функции, то функция $\displaystyle f(x)=\linebreak=\max\,\{f_{1}(x),\,f_{2}(x)\}$ с областью определения $\displaystyle\mbox{dom}\,f=\mbox{dom}\,f_{1}\,\cap\,\mbox{dom}\,f_{2}$ тоже выпукла. Данное свойство легко доказать, воспользовавшись неравенством Йенсена. Понятно, что аналогичное свойство можно доказать для функции $\displaystyle f(x)=\max\{f_{1}(x),\,\ldots,\,f_{m}(x)\}$, которая является выпуклой, если функции $\displaystyle f_{1}$, $\displaystyle f_{2}$, $\displaystyle\ldots$, $\displaystyle f_{m}$ выпуклы.

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

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

Пусть $\displaystyle A$ — некоторое множество и $\displaystyle f(x,\,y)$ — выпуклая по $\displaystyle x$ функция для любого $\displaystyle y\,\in\,A$, тогда функция

является выпуклой по $\displaystyle x$ с областью определения

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

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

4 Минимизация

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

Пусть $\displaystyle G\left({x,\,y}\right)$ — выпуклая по $\displaystyle(x,\,y)$ функция, $\displaystyle Q$ — выпуклое непустое множество. Если задача $\displaystyle\inf\limits_{y\,\in\,Q}G(x,\,y)$ разрешима для всех $\displaystyle x$, то функция О формализованной записи экстремальных задач см. п. 9.

выпукла по $\displaystyle x$. При этом область определения функции $\displaystyle f$ есть проекция $\displaystyle\textup{dom }G$ на её $\displaystyle x$-координаты:

Доказать эту лемму можно, воспользовавшись неравенством Йенсена для $\displaystyle x_{1}$, $\displaystyle x_{2}\,\in\,\mbox{dom }f$.

Функция $\displaystyle\|x-y\|$ выпукла по $\displaystyle(x,\,y)$ как любая функция вычисления нормы вектора, следовательно, если множество $\displaystyle Q$ выпукло, то функция $\displaystyle\inf\limits_{y\,\in\,Q}\|x-y\|$ выпукла по $\displaystyle x$.

Если в лемме 1.5 предположить $\displaystyle\mu$-сильную выпуклость $\displaystyle G(x,y)$ в 2-норме по совокупности переменных $\displaystyle(x,y)$, то верно ли, что функция $\displaystyle f$ будет $\displaystyle\mu$-сильно выпуклая в 2-норме? См. утверждение 1 из в качестве отправной точки. Отметим также (см. утверждение 3 ), что если $\displaystyle G(x,y)$ имеет константу Липшица градиента в 2-норме $\displaystyle L$, то константа Липшица градиента функции $\displaystyle f$ в 2-норме будет не больше $\displaystyle L$.

Негладкие задачи

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

называется субдифференциалом функции $\displaystyle f$ в точке $\displaystyle x_{0}$.

Если функция $\displaystyle f$ выпукла и дифференцируема, то её градиент в точке $\displaystyle x_{0}$ совпадает с субградиентом и он соответственно в этом случае единственен (доказательство см., например, в ).

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

тогда $\displaystyle|x|\geqslant gx$, следовательно, субградиентом функции $\displaystyle f(x)=|x|$ в точке $\displaystyle 0$ может быть любое число из отрезка $\displaystyle[-1,\,1]$, и $\displaystyle\partial f(0)=[-1,\,1]$.

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

Необходимым и достаточным условием глобального минимума выпуклой функции в точке $\displaystyle x^{*}$ является

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

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

Знание субградиента помогает вычислять производную по направлению.

Производная выпуклой функции $\displaystyle f$ в точке $\displaystyle x_{0}$ по любому направлению $\displaystyle s$ всегда существует и определяется равенством

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

Если функции $\displaystyle f_{1}(x)$, $\displaystyle f_{2}(x)$ выпуклы, то для всех $\displaystyle x\,\in\,\textup{dom }f_{1}\cap\textup{dom }f_{2}$ справедлива формула

Пусть функции $\displaystyle f_{1}$, $\displaystyle f_{2}$ выпуклые и $\displaystyle f_{1}(x_{0})=f_{2}(x_{0})$ (причём в точке $\displaystyle x_{0}$ обе функции непрерывны). Тогда

Очевидно, что две последние теоремы распространяются по индукции на любое конечное число функций.

Обозначение $\displaystyle\partial\varphi(Ax)$ означает субдифференциал $\displaystyle\varphi$ по отношению к аргументу в точке $\displaystyle Ax$.

Формула Демьянова–Данскина

В приложениях, приводящих к оптимизационным задачам на минимакс, часто возникает необходимость дифференцирования функций под знаком максимума. Для этих целей применяют теорему о дифференцировании (по направлению) под знаком максимума, которую часто называют теоремой или формулой Демьянова--Данскина В англоязычной литературе эту теорему часто называют просто теорема Данскина (Danskin’s theorem). В России также можно встретить название этой формулы (теоремы), как формулы Демьянова–Данскина–Рубинова., поскольку оба автора независимо пришли к аналогичному утверждению в конце 60-х годов XX века . Сформулируем одну из форм этого утверждения.

выпукла, и в случае, если существует единственный $\displaystyle y\left(x\right)$, такой что $\displaystyle G\left({x,\,y\left(x\right)}\right)=\max\limits_{y}\,G\left({x,\,y}\right)$, градиент функции $\displaystyle f(x)$ можно вычислить следующим образом:

Если $\displaystyle\partial G/\partial x$ непрерывна по $\displaystyle y$ для всех $\displaystyle x$, то субдифференциал Определение и свойства субдифференциала см. в п. 5.

где $\displaystyle\conv$ обозначает операцию взятия выпуклой оболочки от множества.

Не вдаваясь в детали, поясним основную идею доказательства этой теоремы в случае, когда $\displaystyle y(x)$ определяется (единственным образом) из системы ($\displaystyle m$ уравнений):

Эта идея делает интуитивно понятным основное утверждение теоремы Демьянова–Данскина. Поскольку

то $\displaystyle\nabla f(x)=G^{\prime}_{x}(x,y(x))=\nabla_{x}G(x,y(x))$. Здесь $\displaystyle y^{\prime}(x)$ — матрица Якоби ($\displaystyle(i,j)$ элемент матрицы $\displaystyle y^{\prime}(x)$ равен $\displaystyle\partial y_{i}(x)/\partial x_{j}$). Отсюда также становится понятно, что аналогичное утверждение (естественное, при некоторых предположениях) можно сформулировать для $\displaystyle f(x)=\min\limits_{y}G(x,\,y)$ и даже для $\displaystyle f(x)=\min\limits_{y}\max\limits_{z}G(x,y,z)$, см. раздел 26.2.

В 1971 году Дмитрий Бертсекас в своей диссертации доказал более общий результат, не требующий дифференцируемости $\displaystyle G(\cdot,\,y)$, см. .

Утверждения, аналогичные теореме Демьянова–Данскина, были известны и ещё раньше. Так, в середине 60-х годов XX века А. Я. Дубовицкий и А. А. Милютин при получении принципа максимума для задач оптимального управления с фазовыми ограничениями доказали и фактически уже использовали теорему о дифференцировании по направлению под знаком $\displaystyle\sup$ , см. также теорему 1.5 данного пособия.

В более общем виде теорему Демьянова–Данскина можно сформулировать следующим образом (см. также ).

Существует версия теоремы Демьянова–Данскина и без условия компактности $\displaystyle Y$ (см. ).

Существует несколько так называемых теорем об очистке, доказанных В. Л. Левиным (в том числе об очистке субдифференциалов). Приведём основную из этих теорем.

$\displaystyle M=\inf_{x\,\in\,X}\max_{t\,\in\,T}\,G(t,\,x)\,>\,-\infty$.

Тогда найдутся натуральное число $\displaystyle r$, такое, что $\displaystyle r\leq\emph{dim}(X)+1$, и точки $\displaystyle\tau_{1},\,\ldots,\,\tau_{r}\,\in\,T$, такие, что $\displaystyle M=\inf_{x\,\in\,X}\max_{1\leq i\leq r}\,G(\tau_{i},\,x)$.

Теорема 1.8 означает, что исходную задачу минимизации максимума отображения можно заменить на задачу с меньшим числом ограничений. Этим объясняется такое название теоремы — <<очистка>>, отбрасывание некоторых ограничений.

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

где $\displaystyle\partial_{x}G(t_{i},\,\hat{x})$ обозначает субдифференциал функции $\displaystyle G(\cdot,\,x)$ в точке $\displaystyle\hat{x}$.

Для доказательства данной теоремы достаточно применить теорему Ферма (теорема 1.3), обычную теорему об очистке (теорема 1.8) и теорему Дубовицкого–Милютина (теорема 1.5) о дифференцировании максимума из двух выпуклых функций (см. ).

С теоремами об очистке связано одно из доказательств теоремы Хелли, см. п. 12.2.

Дополнение по Шуру

Рассмотрим симметричную матрицу размера $\displaystyle n\times n$ следующего вида:

где $\displaystyle A$ – симметричная матрица размера $\displaystyle k\times k$. Если $\displaystyle\mbox{det }A\neq 0$, то матрица

называется дополнением по Шуру матрицы $\displaystyle A$ в $\displaystyle X$. Матрицы такого вида возникают в различных важных теоремах и формулах, в частности, при решении систем линейных алгебраических уравнений методом исключения блоков переменных.

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

где матрица $\displaystyle A$ положительно определена, т.е. $\displaystyle{\forall x\neq 0}$ выполняется $\displaystyle{{x^{T}Ax}>0}$.

Решением задачи минимизации $\displaystyle\min\limits_{y}G(x,\,y)$ является $\displaystyle y=-A^{-1}Bx$. Тогда

Для того чтобы (7) являлась выпуклой функцией, необходимо и достаточно, чтобы матрица (6) была неотрицательно определённой, так как квадратичную форму (7) можно представить как

Но функция (8) является выпуклой по лемме 1.5. Так как (8) тоже является квадратичной формой, для её выпуклости необходимо и достаточно, чтобы матрица $\displaystyle S={C-B^{T}A^{-1}B}$ была неотрицательно определённой. Следовательно, верны следующие леммы.

Если $\displaystyle A\succ 0$, то $\displaystyle X\succeq 0$ тогда и только тогда, когда $\displaystyle S\succeq 0$.

$\displaystyle X\succ 0$ тогда и только тогда, когда $\displaystyle S\succ 0$ и $\displaystyle A\succ 0$.

Теорема о неявной функции

Теорема о неявной функции, известная из математического анализа, часто применяется при исследовании итеративных оптимизационных методов, не разрешённых явно относительно текущего приближения к решению $\displaystyle x_{k+1}$ на $\displaystyle k$-й итерации. В таких методах новое приближение $\displaystyle x_{k+1}$ может быть решением некоторой вспомогательной задачи минимизации, как, например, в методах регуляризации (подробнее см. ). Также теорема о неявной функции применяется при доказательстве принципа множителей Лагранжа.

Пусть $\displaystyle g(x^{*},\,y^{*})=0$, $\displaystyle g(x,\,y)$ непрерывна по $\displaystyle\{x,\,y\}$ в окрестности $\displaystyle x^{*}$, $\displaystyle y^{*}$ и матрица $\displaystyle g^{\prime}_{y}\left(x^{*},\,y^{*}\right)$ невырождена. Тогда существует единственная непрерывная в окрестности $\displaystyle x^{*}$ функция $\displaystyle y(x)$ такая, что $\displaystyle y^{*}=y(x^{*})$, $\displaystyle g(x,\,y(x))=0$. Если дополнительно существует $\displaystyle g^{\prime}_{x}(x^{*},\,y^{*})$, то $\displaystyle y(x)$ дифференцируема в $\displaystyle x^{*}$ и

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

Пусть $\displaystyle X,\,Y,\,Z$ — банаховы пространства, $\displaystyle U$ — окрестность точки $\displaystyle(x^{*},\,y^{*})\,\in\,X\times Y$ и $\displaystyle g$ — отображение $\displaystyle U$ в $\displaystyle Z$, обладающее следующими свойствами:

$\displaystyle g$ непрерывно в точке $\displaystyle(x^{*},\,y^{*})$;

Частная производная $\displaystyle g^{\prime}_{y}(x,\,y)$ существует в $\displaystyle U$ и непрерывна в точке $\displaystyle(x^{*},\,y^{*})$, а оператор $\displaystyle g_{y}^{\prime}(x^{*},\,y^{*})$ имеет ограниченный обратный.

Тогда существуют такие $\displaystyle\varepsilon>0$, $\displaystyle\delta>0$ и такое отображение

определённое при $\displaystyle\|x-x^{*}\|<\delta$ и непрерывное в точке $\displaystyle x^{*}$, что каждая пара $\displaystyle(x,\,y)$, для которой $\displaystyle\|x-x^{*}\|<\delta$ и $\displaystyle y=f(x)$, удовлетворяет уравнению

и обратно, каждая пара $\displaystyle(x,\,y)$, удовлетворяющая уравнению (10) и условиям $\displaystyle\|x-x^{*}\|<\delta$, $\displaystyle\|y-y^{*}\|\leq\varepsilon$, удовлетворяет и (9).

Доказательство теоремы основано на принципе сжимающих отображений, его можно найти в [50, с. 508]. Там же приведено доказательство и нижеследующей теоремы об условиях, при которых функция, определяемая уравнением вида $\displaystyle g(x,\,y)=0$, дифференцируема.

Пусть выполнены условия теоремы 1.11, и пусть, кроме того, в $\displaystyle U$ существует частная производная $\displaystyle g^{\prime}_{x}$, непрерывная в точке $\displaystyle(x^{*},y^{*})$. Тогда отображение $\displaystyle f$ дифференцируемо в точке $\displaystyle x^{*}$ и

Теорема Люстерника, в свою очередь, играет важную роль в задачах оптимального управления. С помощью теоремы Люстерника правило множителей Лагранжа нахождения условного экстремума (см. п. 9) может быть доказано для экстремальных задач в банаховых пространствах.

Экстремальные задачи и двойственность

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

Точно поставленная (формализованная) экстремальная задача обязательно включает в себя следующие элементы :

ограничения, которые в общем виде можно представить как подмножество $\displaystyle D\,\subset\,X$.

Формализованную экстремальную задачу на минимум записывают в следующей форме:

соответственно формализованную экстремальную задачу на максимум записывают так В российской традиции формулировку задачи (11) принято записывать и так: $f(x)\,\rightarrow\,\min_{x\,\in\,D}.$ :

Точки $\displaystyle x\,\in\,D$ называют допустимыми для задач (11), (12), само множество $\displaystyle D$ называют допустимым множеством. Если $\displaystyle D=X$, то задачи (11) – (12) называют задачами без ограничений.

Допустимая точка $\displaystyle x^{*}$ называется решением задачи (11) или глобальным (абсолютным) минимумом в задаче (11), если для любого $\displaystyle x\,\in\,D$ имеет место неравенство $\displaystyle f(x)\,\geqslant\,f(x^{*})$. Допустимая точка $\displaystyle x^{*}$ называется решением задачи (12) или глобальным (абсолютным) максимумом в задаче (12), если для любого $\displaystyle x\,\in\,D$ имеет место неравенство $\displaystyle f(x)\,\leqslant\,f(x^{*})$. Если в задаче требуется найти и точки максимума, и точки минимума, то в записи (11) ((12)) вместо $\displaystyle\min\,(\max)$ пишется extr (такая задача будет называтьcя задачей на экстремум функционала $\displaystyle f$).

Ясно, что если $\displaystyle x^{*}$ — решение задачи (11) на минимум ((12) на максимум), то $\displaystyle x^{*}$ также является решением аналогичной задачи на максимум (минимум) с функционалом $\displaystyle-f(x)$ вместо $\displaystyle f(x)$.

Введём также понятие локального экстремума (т.е. локального минимума и максимума).

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

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

В этом параграфе изложение во многом следует и . Здесь рассматривается правило множителей Лагранжа для гладких задач с ограничениями, задаваемыми равенствами. Принцип Лагранжа (метод решения задач, основанный на идее Лагранжа) описан самим автором в эпиграфе, поставленном нами к данному параграфу. В дальнейшем оказалось, что идея Лагранжа поразительно плодотворна — необходимые условия экстремума в самых разных экстремальных задачах (с ограничениями типа равенств, неравенств и включений) имеют форму правила множителей Лагранжа. По словам Р. Рокафеллара , <<теория множителей Лагранжа позволяет преобразовывать экстремальные задачи с ограничениями в задачи, имеющие меньше ограничений, но больше переменных>>. До представленного ниже формализованного описания правила множителей Лагранжа кратко поясним, что принцип Лагранжа заключается в идее составления функции (теперь она называется функцией Лагранжа), которая является суммой минимизируемого (максимизируемого) функционала и функций-ограничений, задающих равенства, с неопределёнными множителями. Тогда необходимые условия экстремума для исходной задачи с ограничениями эквивалентны таким условиям для безусловной задачи минимизации (максимизации) функции Лагранжа. Кроме того, для выпуклых задач решение исходной задачи доставляет глобальный минимум функции Лагранжа, т.е. необходимые условия экстремума минимума функции Лагранжа становятся и достаточными условиями.

Рассмотрим задачу с ограничениями типа равенств вида

где $\displaystyle f$, $\displaystyle g_{i},\,i=1,\,\ldots,\,m$, — достаточно гладкие функции.

Если $\displaystyle\nabla g_{i}(x^{*})$, $\displaystyle i\!\!\!=\linebreak=1,\,\ldots,\,m$ линейно независимы и если $\displaystyle x^{*}$ — точка минимума в задаче (13), т.е. $\displaystyle x^{*}\in Q=\{x|g_{i}(x)=0,\,i=1,\,\ldots,\,m\}$ и $\displaystyle\forall x\in Q\linebreak f(x^{*})\,\leqslant\,f(x)$, то найдутся такие $\displaystyle\lambda_{1}^{*},\,\ldots\,\lambda_{m}^{*}$, что

Числа $\displaystyle\lambda_{1}^{*},\,\ldots\,\lambda_{m}^{*}$ в (14) называются множителями Лагранжа.

Тогда правило множителей Лагранжа (14) переформулируется как

где $\displaystyle L_{x}^{\prime}$, $\displaystyle L_{\lambda}^{\prime}$ — производные (градиенты) по соответствующим переменным. В (16) переменные $\displaystyle x$ называются прямыми, а $\displaystyle\lambda$ — двойственными.

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

Поскольку $\displaystyle g(v^{*},\,y^{*})=0$, то в условиях выполнения теоремы о неявной функции (см. п. 8):

Если объединить (18) и (19), то получатся следующие равенства:

которые эквивалентны (16). Таким образом, обосновано правило множителей Лагранжа, и (19) даёт явную формулу для множителей Лагранжа.

Аналогичные рассуждения можно провести, считая, что переменные принадлежат общему гильбертову пространству, см. раздел 26.2 (или даже банахову пространству, см. раздел 8).

2 Гладкие задачи с ограничениями типа равенств и неравенств

В этом параграфе изложение частично следует .

Рассмотрим задачу с ограничениями типа равенств и неравенств вида

не является пустой. Здесь и далее будем обозначать $\displaystyle x^{*}$ — оптимальное решение задачи (20), а оптимальное значение $\displaystyle f(x^{*})=f^{*}$. Такие же обозначения общеприняты и для задач математического программирования общего вида. Как уже упоминалось, функцию $\displaystyle f$ называют целевой.

Ограничение-неравенство $\displaystyle h_{i}(\cdot)\,\leqslant\,0$ называется активным в точке $\displaystyle x^{\prime}$, если в этой точке оно обращается в равенство: $\displaystyle h_{i}(x^{\prime})=0$. Ограничения-равенства по определению всегда активны в допустимой точке.

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

Впервые задача с неравенствами (20) была рассмотрена в диссертации В. Каруша (1939 г., Чикаго), но результаты остались неопубликованными. В 1948 г. задача (20) и метод её решения с помощью функции Лагранжа были переоткрыты Ф. Джоном. Подробно история этих открытий описана в научно-популярной статье .

Существует много разных способов обоснования принципа множителей Лагранжа. Отметим здесь, в частности, работы сотрудников МФТИ , .

Двойственная функция Лагранжа для задачи (20) определяется как

Если лагранжиан (22) не ограничен снизу, двойственная функция принимает значение $\displaystyle-\infty$. Поскольку двойственная функция представляет собой поточечные нижние грани аффинных функций от $\displaystyle\lambda$ и $\displaystyle\nu$, она является вогнутой, даже если задача (20) не является выпуклой задачей.

Любое значение двойственной функции $\displaystyle{\varphi(\lambda,\nu)}$ всегда не больше оптимального значения $\displaystyle f^{*}$:

Здесь и далее векторные неравенства со знаками $\displaystyle\geqslant$ и $\displaystyle\leqslant$ являются покомпонентными.

Действительно, пусть $\displaystyle x^{\prime}$ — допустимая точка для задачи (20), т.е. $\displaystyle g_{i}(x^{\prime})=0$, $\displaystyle h_{i}(x^{\prime})\,\leqslant\,0$. Пусть $\displaystyle\nu\,\geqslant\,0$. Тогда

поскольку каждое слагаемое в первой сумме равно $\displaystyle 0$, а каждое слагаемое во второй сумме неположительно. Отсюда

для любого допустимого $\displaystyle x^{\prime}$, то это верно и при $\displaystyle x^{\prime}=x^{*}$:

Итак, для каждой пары $\displaystyle(\lambda,\,\nu)$ c $\displaystyle\nu\,\geqslant\,0$ двойственная функция Лагранжа даёт нижнюю оценку оптимального значения $\displaystyle f^{*}$ задачи (20). Возникает вопрос: а можно ли найти наилучшую нижнюю оценку среди всех нижних оценок, которые можно получить с помощью двойственной функции Лагранжа? Ответом на этот вопрос служит решение задачи

которая является задачей выпуклого программирования См. далее параграф 9.4., поскольку целевая функция $\displaystyle\varphi(\lambda,\,\nu)$ вогнута, а ограничения задачи выпуклы.

Задача (23) называется двойственной к задаче (20). Последнюю задачу поэтому иногда называют прямой.

Пару $\displaystyle(\lambda^{*},\,\nu^{*})$, являющуюся решением задачи (23), называют оптимальными множителями Лагранжа.

3 Чувствительность в оптимизации

Множители Лагранжа часто имеют вполне конкретную интерпретацию в различных интересных практических задачах. Например, в экономических приложениях множители Лагранжа часто интерпретируются как цены.

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

Для примера рассмотрим простую задачу с одним аффинным ограничением :

Пусть $\displaystyle x^{*}$ — как обычно, решение задачи (24) и соответственно $\displaystyle\lambda^{*}$ — оптимальный множитель Лагранжа.

Если правая часть ограничения $\displaystyle a^{T}x=b$ изменится на $\displaystyle\Delta b$ (рис. 5):

то оптимальное значение $\displaystyle x^{*}$ изменится на какое-то $\displaystyle\Delta x$. При этом $\displaystyle b+\Delta b=\linebreak=a^{T}(x^{*}+\Delta x)=a^{T}x^{*}+a^{T}\Delta x=b+a^{T}\Delta x$, т.е.

Используя (14), получаем, что $\displaystyle\nabla f(x^{*})=-\lambda^{*}a$. Оценим соответствующее изменение оптимального значения целевой функции:

Учитывая (25), получим $\displaystyle\Delta f=-\lambda^{*}\Delta b+o\left(\|\Delta x\|\right)$, поэтому с точностью до первого порядка по $\displaystyle\|\Delta x\|$

т.е. величина множителя Лагранжа соответствует скорости уменьшения $\displaystyle\Delta f$ при увеличении $\displaystyle b$ на $\displaystyle\Delta b$. Иными словами, $\displaystyle\lambda^{*}$ можно проинтерпретировать как цену ограничения.

К соотношению, аналогичному (26), можно прийти и таким путём . Лагранжиан для задачи (24)

Рассматривая лагранжиан как функцию от параметра $\displaystyle b$ (соответственно, искомое решение $\displaystyle x^{*}(b)$, а множитель Лагранжа — $\displaystyle\lambda^{*}(b)$), получаем

Поскольку $\displaystyle a^{T}x^{*}(b)\equiv b$, из (27) получаем

С другой стороны, если оставить в правой части равенства (27) только первое и третье слагаемые, можно прийти к такому равенству:

В силу (14) из последнего равенства получаем, что $\displaystyle\frac{dL}{db}=-\lambda^{*}(b)$, т.е.

что означает, что множитель Лагранжа можно интерпретировать как показатель чувствительности оптимума по отношению к ограничению.

Если в задаче (24) имеются несколько ограничений вида $\displaystyle(a^{i})^{T}x=b_{i}$, $\displaystyle i=1,\,\ldots,\,m$, то с помощью аналогичных преобразований можно прийти к соотношению

В случае существования всех нужных зависимостей $\displaystyle x^{*}(b)$, $\displaystyle\lambda^{*}(b)$ каждый из множителей Лагранжа интерпретируется следующим образом:

Нетрудно заметить, что к абсолютно тем же результатам (26), (28) можно прийти и в более общем случае ограничений вида $\displaystyle g_{i}(x)=b$ в задаче (24).

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

4 Задачи выпуклого программирования

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

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

Двойственная функция Лагранжа для задачи (30) определяется как

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

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

Следует отметить, что формулировка задачи только с ограничениями-неравенствами, без ограничений-равенств, не умаляет общности постановки задачи. Действительно, каждое ограничение-равенство вида $\displaystyle Ax-b=0$ можно заменить двумя ограничениями-неравенствами $\displaystyle Ax-b\,\leqslant\,0$ и $\displaystyle Ax-b\,\geqslant\,0$.

На рис. 6–7 представлена геометрическая интерпретация данного факта. В общем случае множество

и вектор весов $\displaystyle(\nu,1)$ определяет опорную для $\displaystyle H$ плоскость (см. определение 1.16).

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

Непустые выпуклые множества $\displaystyle A$ и $\displaystyle B$ называются (собственно) отделимыми, если существует аффинная гиперплоскость

такая, что множества $\displaystyle A$, $\displaystyle B$ лежат в противоположных по отношению к $\displaystyle H$ замкнутых полупространствах и, по крайней мере, одно из множеств $\displaystyle A$, $\displaystyle B$ не содержится в $\displaystyle H$. В этом случае гиперплоскость $\displaystyle H$ отделяет множества $\displaystyle A$, $\displaystyle B$.

Аналитически определение 1.13 записывается так:

Непустые выпуклые множества $\displaystyle A$ и $\displaystyle B$ называются строго отделимыми, если существуют две различные параллельные гиперплоскости

Можно доказать и более сильную версию теоремы 1.14: непустые выпуклые множества отделимы тогда и только тогда, когда их относительные внутренности не пересекаются. Здесь относительная внутренность множества $\displaystyle A$ — это его внутренность как подмножества аффинной оболочки множества $\displaystyle A$. Доказательство можно найти в [187, теорема 3.16].

Тогда если $\displaystyle x^{*}$ — решение задачи (30), то существует ненулевой вектор множителей Лагранжа $\displaystyle\nu=(\nu_{0},\,\nu_{1},\,\ldots,\,\nu_{p})$, такой, что для функции Лагранжа

Если $\displaystyle\nu_{0}\neq 0$, то условия 1) – 3) предыдущего утверждения достаточны для того, чтобы допустимая точка $\displaystyle x^{*}$ была решением задачи (30).

Докажем первое утверждение данной теоремы (более подробное доказательство см. в ). Не ограничивая общности, будем считать, что $\displaystyle f(x^{*})=0$.

Докажем, что $\displaystyle B$ является непустым выпуклым множеством. Если в качестве $\displaystyle x$ взять $\displaystyle x^{*}$, то любой вектор $\displaystyle b$ со всеми неотрицательными компонентами будет принадлежать множеству $\displaystyle B$, т.е. $\displaystyle B$ непусто. Для доказательства выпуклости $\displaystyle B$ возьмём два вектора $\displaystyle b\,\in\,B$ и $\displaystyle b^{\prime}\,\in\,B$. Пусть $\displaystyle x$ и $\displaystyle x^{\prime}$ — такие элементы из $\displaystyle Q$, что $\displaystyle f(x)\,\leqslant\,b_{0}$, $\displaystyle h_{i}(x)\,\leqslant\,b_{i}$, $\displaystyle f(x^{\prime})\,\leqslant\,b^{\prime}_{0}$, $\displaystyle h_{i}(x^{\prime})\,\leqslant\,b^{\prime}_{i}$ соответственно, $\displaystyle i=1,\,\ldots,\,p$. Для $\displaystyle\alpha\,\in\,[0,\,1]$ $\displaystyle x_{\alpha}=\alpha x+(1-\alpha)x^{\prime}\,\in\,Q$ в силу выпуклости $\displaystyle Q$. Ввиду выпуклости функций $\displaystyle f$, $\displaystyle h_{i}$, $\displaystyle i=1,\,\ldots,\,p$,

т.е. точка $\displaystyle\alpha b+(1-\alpha)b^{\prime}\,\in\,B$.

что противоречит тому, что $\displaystyle x^{*}$ — решение задачи (30). Следовательно, наше предположение неверно и $\displaystyle C\cap B=\varnothing$.

Так как $\displaystyle 0\,\in\,B$, то из последнего неравенства следует, что

Поскольку $\displaystyle c_{0}<0$, то $\displaystyle\nu_{0}\,\geqslant\,0$ и, следовательно, $\displaystyle\sup_{c\,\in\,C}\nu_{0}c_{0}=0$. Тогда (32) можно переписать так:

3. Докажем, что множители Лагранжа $\displaystyle\nu_{i}$, $\displaystyle i=0,\,1,\,\ldots,\,p$ удовлетворяют условиям неотрицательности. Вектор

в котором единица стоит на $\displaystyle i$-м месте, принадлежит множеству $\displaystyle B$, как и любой вектор с неотрицательными компонентами. Подставив $\displaystyle\hat{b}^{i}$ в (33), получим, что $\displaystyle\nu_{i}\,\geqslant\,0$, что и требовалось.

4. Докажем, что множители $\displaystyle\nu_{i}$, $\displaystyle i=1,\,\ldots,\,p$ удовлетворяют условиям дополняющей нежёсткости. Для $\displaystyle h_{i}(x^{*})=0$ равенство $\displaystyle\nu_{i}h_{i}(x^{*})=0$ тривиально. Пусть $\displaystyle h_{i}(x^{*})\neq 0$ для некоторого $\displaystyle i$, тогда $\displaystyle h_{i}(x^{*})<0$. Возьмём в определении множества $\displaystyle B$ в качестве $\displaystyle x$ точку $\displaystyle x^{*}$. Тогда вектор

в котором число $\displaystyle h_{i}(x^{*})$ стоит на $\displaystyle i$-м месте, принадлежит множеству $\displaystyle B$. Следовательно, можно подставить $\displaystyle b_{h_{i}}$ в (33). Получаем, что $\displaystyle\nu_{i}h_{i}(x^{*})\,\geqslant\,0$. Тогда $\displaystyle\nu_{i}$ должно быть неположительным (поскольку $\displaystyle h_{i}(x^{*})<0$). Но в п. 3 доказано, что все $\displaystyle\nu_{i}$ неотрицательны. Таким образом, $\displaystyle\nu_{i}=0$ и $\displaystyle\nu_{i}h_{i}(x^{*})=0$, $\displaystyle i=1,\,\ldots,\,p$.

5. Докажем принцип минимума для функции Лагранжа Обратите внимание, что для задачи математического программирования в общем виде (20) это свойство формулируется немного иначе и называется нижней оценкой оптимального значения с помощью двойственной функции Лагранжа, см. лемму 1.11.. Пусть $\displaystyle x\,\in\,Q$. Тогда вектор

принадлежит $\displaystyle B$. Следовательно, мы можем подставить $\displaystyle b_{fh}$ в (33):

Поскольку $\displaystyle f(x^{*})=0$ и выполняются условия дополняющей нежёсткости, то для любого $\displaystyle x\,\in\,Q$

5 Сильная и слабая двойственность

Обозначим оптимальное значение для двойственной задачи (23) через $\displaystyle\varphi^{*}$. Тогда можно записать очень важное свойство оптимального значения целевой функции:

(см. лемму 1.11 о нижней оценке оптимального значения).

Неравенство (34) выполняется, даже если исходная задача невыпуклая Кроме того, неравенство выполняется, даже если $\displaystyle\varphi^{*}=\infty$ и $\displaystyle f^{*}=\infty$., и называется свойством слабой двойственности (weak duality).

Разность $\displaystyle f^{*}-\varphi^{*}$ называется зазором двойственности или зазором между решениями прямой и двойственной задач.

Ясно, что зазор двойственности всегда неотрицателен. Если имеет место равенство

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

где $\displaystyle A$ — симметричная матрица размера $\displaystyle n\times n$ и $\displaystyle A$ не является неотрицательно определённой. Вследствие последнего утверждения задача (36) не является выпуклой.

Составим функцию Лагранжа для этой задачи:

здесь $\displaystyle I$ — единичная матрица.

Двойственная задача $\displaystyle\max\limits_{\nu\geq 0}\,\varphi(\nu)$ является выпуклой и одномерной. Зазор двойственности в этой случае нулевой:

Решением задачи (36) является нормированный собственный вектор матрицы $\displaystyle A$, который соответствует её минимальному собственному значению. Иногда задачу (36) называют задачей построения доверительной области (trust region problem). Такого рода задачи могут возникать при необходимости нахождения оптимальных аппроксимаций второго порядка различных функций на единичном шаре.

Имеет место и более общий факт наличия сильной двойственности для общей задачи квадратичного программирования, см. далее п. 10.

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

где $\displaystyle W$ — симметричная матрица размера $\displaystyle n\times n$. Ограничения задачи означают, что компоненты вектора $\displaystyle x$ могут принимать только значения $\displaystyle 1$ или $\displaystyle-1$. Задачи оптимизации, в которых некоторые или все переменные должны быть целыми числами, называют задачами целочисленного программирования.

Допустимое множество задачи (37) конечно, поскольку содержит всего $\displaystyle 2^{n}$ точек, но зависимость от $\displaystyle n$ экспоненциальная, поэтому с помощью простого перебора точек из допустимого множества задачу (37) можно решить только для совсем небольших $\displaystyle n$, не более нескольких десятков. В общем случае задача (37) NP-трудна.

поскольку квадратичная форма (38) достигает минимума в точке $\displaystyle x=0$ при условии, что её матрица $\displaystyle W+\text{diag}(\lambda)$ неотрицательно определена и не ограничена в остальных случаях.

Функция (39) даёт нижнюю оценку оптимального значения задачи (37). Например, при $\displaystyle\lambda=-\lambda_{\min}(W)\cdot(1,\,\ldots,\,1)$ нижняя оценка для $\displaystyle f^{*}$ следующая:

Задачу (37) можно интерпретировать как задачу разбиения множества из $\displaystyle n$ элементов $\displaystyle S=\{1,\,2,\,\ldots,\,n\}$ на две части:

Тогда элемент матрицы $\displaystyle w_{ij}$ можно интерпретировать как стоимость нахождения элементов с номерами $\displaystyle i$ и $\displaystyle j$ из $\displaystyle S$ в одной части, а $\displaystyle-w_{ij}$ — как стоимость нахождения элементов с номерами $\displaystyle i$ и $\displaystyle j$ из $\displaystyle S$ в разных классах соответственно. При этом задача (37) соответствует цели построения разбиения с минимальной общей стоимостью.

Мы вернёмся к описанной задаче в п. 14.7, где посмотрим на неё с позиции возможной (выпуклой) <<релаксации>> для нахождения приближённого решения.

Часто полезно заранее знать, для каких задач выполняется свойство сильной двойственности (т.е. имеется нулевой разрыв двойственности). Одним из таких условий является условие Слейтера.

Рассмотрим задачу выпуклого программирования следующего вида:

в которой функции $\displaystyle f$, $\displaystyle h_{1}$, $\displaystyle\ldots$, $\displaystyle h_{p}$ являются выпуклыми.

Условие Слейтера (его ещё иногда называют условием регулярности) требует, чтобы для задачи (40) существовала такая допустимая точка $\displaystyle x^{\prime}$, что неравенства в (40) являются строгими:

Такую точку $\displaystyle x^{\prime}$ также иногда называют строго допустимой.

Теорема Слейтера утверждает, что свойство сильной двойственности для задачи выпуклого программирования (40) выполняется, если выполняются условия (41).

Условия Слейтера можно ослабить, если некоторые из функций-ограничений $\displaystyle h_{i}$ являются аффинными (определение аффинных функций см. в п. 2). Пусть первые $\displaystyle k$ функций-ограничений $\displaystyle h_{i}(x)$, $\displaystyle i=1,\,\ldots,\,k$ аффинные. Тогда для существования нулевого зазора двойственности достаточно, чтобы существовала точка $\displaystyle x^{\prime}$, такая, что

6 Задача линейного программирования

Рассмотрим оптимизационную задачу с линейной целевой функцией и линейными функциями-ограничениями

Задача (43), называемая задачей линейного программирования (ЛП), стала, наверное, одной из самых известных в ХХ веке задач оптимизации. В начале 80-х годов XX века считалось, что решение задачи линейного программирования находится на первом месте в мире среди всех математических задач Но в эти задачи не входила работа с базами данных (сортировка, поиск данных). по числу затраченного компьютерного времени.

Приведём текстовое описание задачи ЛП: необходимо найти максимум или минимум линейной функции множества переменных на выпуклом многограннике (задаваемом конечной системой линейных равенств и неравенств). Задачи ЛП, конечно, являются подклассом задач выпуклого программирования. Как отмечено в текстовом описании, задачи на нахождение максимума линейной функции при линейных ограничениях также относятся к задачам ЛП. Геометрическую иллюстрацию графического метода решения задачи ЛП см. на рис. 10.

С созданием теории линейного программирования начался период активного применения теории и методов оптимизации в экономике и экономических исследованиях. Во-первых, было обнаружено, что целый ряд практических задач организации производства можно формализовать как задачи ЛП Сам Канторович приводит такой список: ¡¡вопросы наилучшего распределения работы станков и механизмов, максимального уменьшения отходов, наилучшего использования сырья и местных материалов, топлива, транспорта и пр.¿¿ (цит. по [46, с. 43]).. Во-вторых, к уже упомянутым экономическим задачам и задачам управления системами, которые позже отнесут к дисциплине <<исследование операций>>, возник большой интерес у военных специалистов. Считается, что сейчас уже классическая задача ЛП об оптимальной диете, описанная и решённая будущим Нобелевским лауреатом Джорджем Стиглером , возникла в американской армии в 30--40-е годы XX века. Задача о диете ставилась так: выбрать суточный набор продуктов питания минимальной стоимости, который будут обеспечивать необходимую норму питательных веществ. Первые версии задачи Стиглер решал эвристическим методом (77 переменных --- продуктов и 9 ограничений) Позже, после появления симплекс-метода Данцига, результаты были пересчитаны и полностью подтвердились.. Оказалось, что для первой версии задачи оптимальный рацион состоит из хлеба, молока, капусты, шпината и фасоли.

В-третьих, были разработаны и реализованы вычислительные методы, которые сделали реальным решение таких задач на ЭВМ, даже относительно больших размеров (как и по числу переменных, так и по числу ограничений). Что интересно, начальный этап развития ЛП на Западе (а это было почти на десятилетие позже, чем в СССР) происходил практически одновременно с развитием компьютеров, и там это сразу означало, что впервые в истории управленцы получили мощный и практический метод поиска оптимального направления действий из огромного числа возможных направлений. Так, линейное программирование открыло дорогу к практическому выполнению расчётов, направленных на оптимизацию использования ресурсов во многих секторах экономики и военно-промышленном комплексе.

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

Приоритет в создании теории и моделей задач ЛП принадлежит советскому математику Леониду Витальевичу Канторовичу (1912–1986). Первая печатная работа <<Математические методы организации и планирования производства>> с постановками таких задач и методом их решения была опубликована Канторовичем в 1939 году . В качестве метода решения задач ЛП в работе был представлен метод разрешающих множителей — прообраз симплекс-метода Данцига (см. ниже).

Эта основополагающая работа Канторовича по линейному программированию стала известна и доступна коллегам из западных стран только через два десятилетия (!), в 1960 г., когда в журнале <> опубликовали английский перевод . Инициатива этого перевода и публикации принадлежала американскому экономисту и математику голландского происхождения Т. Купмансу.

В 1940 г. Л. В. Канторович опубликовал математическую версию брошюры 1939 г. — статью <<Об одном эффективном методе peшeния некоторых классов экстремальных проблем>>, в которой оптимизация впервые была рассмотрена с позиции функционального анализа . В данной работе был сформулирован критерий оптимальноcти в задаче максимизации функционала на компактном множестве.

За свой вклад в теорию ЛП и экономику Канторович (вместе с независимо получившим те же результаты, но позже, Т. Купмансом) был удостоен Нобелевской премии по экономике (с формулировкой <<за вклад в теорию оптимального распределения ресурсов>>) в 1975 году.

Активное развитие теория ЛП (а позже и выпуклая оптимизация) получила в Соединённых Штатах Америки в середине и конце 40-х годов XX века. Помимо Канторовича и Купманса, значительный вклад в стремительное развитие линейного программирования внесли математики Джон фон Нейман и Джордж Бернард Данциг, а также известный экономист Василий Леонтьев.

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

Василий Леонтьев (1905–1999) в 1930-е гг. начал работу над экономико-математической моделью <<затраты–выпуск>> (модель многоотраслевой экономики). В модели взаимодействие между различными отраслями экономики учитывается таким образом: объём продукции каждой отрасли является линейной комбинацией объёмов продукции остальных отраслей (что отражает необходимые затраты на обеспечение выпуска) с прибавленным объёмом конечного потребления по этой отрасли. В формальной постановке модель описывается с помощью системы линейных алгебраических уравнений. В 1973 году Василий Леонтьев был удостоен Нобелевской премии по экономике <<за развитие метода «затраты – выпуск>> и за его применение к важным экономическим проблемам>>.

Д. Данциг (1914–2005) в 1947 г. разработал первый вычислительный алгоритм для решения задач ЛП — симплекс-метод. Эта работа выполнялась для американской армии. Метод последовательно перебирает смежные вершины графа допустимого множества, так, чтобы в каждой последующей вершине значение целевой функции или улучшалось, или оставалось неизменным. Результатом работы метода будет либо множество оптимальных решений — одна из вершин допустимого полиэдра или его сторона, либо определение несовместимости множества ограничений, либо заключение о неограниченности целевой функции. Благодаря простоте реализации и хорошей практической скорости работы, несмотря на полувековые попытки заменить его, симплекс-метод до сих пор остаётся одним из наиболее популярных методов решения задач ЛП на практике. Он реализован во многих оптимизационных вычислительных пакетах.

В 1950-е годы продолжилось развитие теоретических основ линейного программирования, его применение для промышленных задач и создание первых программных кодов для решения задач ЛП . В 1960-е годы стало возможным решать задачи линейного программирования большой размерности. Симплекс-метод хорошо работал на практике: эксперименты подтверждали, что число требуемых итераций почти линейно зависит от числа ограничений. Но в начале 1970-х годов авторитет симплекс-метода как универсального средства решения задач ЛП сильно упал. Появилась теория вычислительной сложности, и на специальных примерах было показано, что симплекс-метод (при самом широко используемом правиле выбора направляющего столбца и направляющей строки) требует экспоненциально большого (от размерности пространства) числа итераций Понятия экспоненциальной и полиномиальной разрешимости классов задач возникают в теории сложности алгоритмов. Если алгоритм решает любую задачу из рассматриваемого класса задач за время, ограниченное экспонентой от некоторого многочлена (полинома) от размерности задачи, то говорят, что алгоритм имеет экспоненциальную сложность. Полиномиальный по времени алгоритм — это алгоритм решения любой задачи из рассматриваемого класса, в котором число арифметических шагов (время работы) ограничено некоторым многочленом от размерности задачи или, иными словами, полиномиально ограничено. Сам класс задач в этом случае является полиномиально разрешимым.. Первыми такие примеры представили американские математики В. Кли и Д.Д. Минти в 1972 г. (см. пример 1.19). Позже примеры задач ЛП, на которых симплекс-метод работает экспоненциально долго Это были модифицированные варианты примера 1.19., были предложены и для других правил выбора направляющей строки и направляющего столбца (см., например, ).

Тем не менее в упомянутых примерах речь идёт о худшем случае работы алгоритма, а в целом на практике симплекс-метод обычно работает очень быстро, и многочисленные эксперименты и исследования метода подтверждали полиномиальное время работы на практике. В 70-е и 80-е годы XX века эта разница между теоретическими и практическими результатами не давала покоя многим исследователям. Было несколько попыток объяснить загадку этих наблюдений путём вероятностного анализа работы симплекс-метода на случайных входных данных, которые моделировали задачи из реальных приложений (см., например, ). Были получены результаты, что в среднем симплекс-метод полиномиален, поскольку требует $\displaystyle O(m^{3})$ операций (при общем количестве итераций $\displaystyle 2m$, $\displaystyle m$ — число строк в исходной матрице $\displaystyle A$ задачи). Но наиболее успешная попытка дать объяснение факту быстрой работы симплекс-метода на практике была сделана в эпохальной работе начала XXI века Спилмана и Тенга : необходимо проводить так называемый сглаженный анализ алгоритмов (smoothed analysis), который является промежуточным звеном между анализом худшего случая и анализом в среднем. Аргументация такого промежуточного подхода в следующем: при анализе работы алгоритма в худшем случае задачи, на которых алгоритм работает медленно, обычно подбираются искусственно. Но они не являются типичными и почти никогда не возникают на практике, при расчётах с реальными данными. Что касается анализа работы алгоритма в среднем случае, который был призван решить упомянутую проблему анализа худшего случая, то и у этого подхода тоже есть свои недостатки. В частности, при генерации входных данных эти данные должны соответствовать какому-то распределению, которое, в свою очередь, моделирует исходные данные реальных задач. Но распределения данных реальных задач сильно отличаются друг от друга. Кроме того, не во всех случаях в принципе для задачи можно определить распределение исходных данных. В результате входные данные задач, которые встречаются на практике, могут почти не иметь ничего общего со входами, сгенерированными для анализа работы алгоритма в среднем.

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

Таким образом, сглаженный анализ является вероятностным анализом алгоритма: проверяется работа алгоритма при незначительных случайных возмущениях (конкретнее — гауссовых возмущениях) конкретных входных данных, при этом ищется зависимость производительности алгоритма от размера входа и от среднеквадратичного отклонения возмущений.

Более формально, идея Спилмана и Тенга в следующем. Рассматривается задача ЛП вида

Пусть матрица $\displaystyle A$ представляется в виде

где каждый элемент матрицы $\displaystyle G$ — нормально распределённая независимая случайная величина с нулевым математическим ожиданием и дисперсией $\displaystyle\sigma^{2}$. Если в случае анализа алгоритма в среднем $\displaystyle\sigma^{2}\rightarrow\infty$, то для сглаженной сложности $\displaystyle\sigma^{2}\rightarrow 0$. Если мы ищем время решения задачи (44) как функцию $\displaystyle T(A)$ от заданной матрицы $\displaystyle A$ размерности $\displaystyle m\times n$, то для любого $\displaystyle\bar{A}$ значение $\displaystyle T(A)$ является случайной величиной, и её математическое ожидание есть полином от $\displaystyle n$, $\displaystyle m$, $\displaystyle\log\frac{1}{\varepsilon}$, $\displaystyle\frac{1}{\sigma}$ в категориях сложности по Блюм–Шубу–Смейлу (см. п. 35.3).

Спилман и Тенг показали, что симплекс-метод имеет полиномиальную сглаженную сложность В том же 2006 году оценка симплекс-метода Спилмана и Тенга была улучшена Р. Вершининым . Он показал, что ожидаемое время работы симплекс-метода на незначительно изменённых входных данных является полиномом от логарифма количества ограничений $\displaystyle n$.. Эти результаты означают, что хотя и существуют задачи, на которых симплекс-метод будет работать экспоненциально долго, но если исходные данные таких задач (коэффициенты целевой функции и ограничений) подвергнуть незначительному изменению, то с достаточно высокой вероятностью симплекс-метод на возмущённой задаче уже будет работать за полиномиальное время.

В конце 1970-х годов обнаружили, что алгоритмы, в общем случае решающие задачи ЛП за полиномиальное время, всё-таки существуют (см. подробнее главу 2, п. 17.3). Все такие полиномиальные алгоритмы — методы внутренней точки (самый первый метод внутренней точки — метод И. И. Дикина , первый метод с полиномиальной сложностью — метод Кармаркара , см. также п. 24.8) и метод эллипсоидов — отличались от симплекс-метода геометрическим подходом. Эти алгоритмы либо генерировали последовательность точек во внутренности допустимого множества, либо помещали допустимое множество в эллипсоид. В течение 50 лет оставался открытым вопрос, существует ли полиномиальный алгоритм, который работает подобно симплекс-методу, перебирая только вершины (угловые точки) допустимого множества задачи. Ответ на этот вопрос дали Келнер и Спилман в 2006 г. : они представили рандомизированный симплекс-метод с полиномиальным временем работы. Как и другие известные полиномиальные алгоритмы для решения задач ЛП, время работы предложенного Келнером и Спилманом алгоритма полиномиально зависит от числа битов, необходимых для представления входной информации задачи. Данный алгоритм показывает полиномиальную скорость работы и на <<плохих>> для симплекс-метода задачах.

Закончит работу алгоритм в оптимальной точке $\displaystyle(0,\,0,\,\ldots,\,5^{n})$. Пример получен в результате небольшой деформации $\displaystyle n$-мерного гиперкуба Сейчас допустимое множество системы линейных неравенств из (45), предложенной Кли и Минти, называют кубом, или политопом Кли–Минти.$\displaystyle\ \,0\leqslant x_{i}\leqslant 1$, $\displaystyle i=1,\,\ldots,\,n$, заставляющей симплекс-метод перебирать все вершины куба.

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

О главной нерешённой проблеме в теории линейного программирования, сформулированной Стивеном Смейлом, см. в п. 35.3.

Существуют два частных случая задачи ЛП (43), которые так часто встречаются в приложениях, что имеют специальные названия. Один из них — задача ЛП в стандартной форме:

т.е. задача ЛП, в которой ограничениями-неравенствами являются только условия неотрицательности всех компонент вектора $\displaystyle x$. Для приведения (46) к каноническому виду (20) необходимо учитывать, что $\displaystyle h_{i}(x)=-x_{i}$, $\displaystyle i=1,\,\ldots,\,p$.

Вторым часто встречающимся случаем задачи ЛП является задача без ограничений-равенств вида

Перейдём к аналитическому рассмотрению задачи (46). Функция Лагранжа для этой задачи выглядит следующим образом:

Задача на минимум в этом выражении легко решается аналитически:

Таким образом, нижняя оценка оптимального значения $\displaystyle f^{*}$ является нетривиальной только в случае, когда $\displaystyle\nu_{i}\,\geqslant\,0$, $\displaystyle i=1,\,\ldots,\,p$ и $\displaystyle\left(c+A^{T}\lambda-\nu\right)=0$. Двойственная к задаче линейного программирования записывается так:

Пусть $\displaystyle x^{*}$ — допустимое решение задачи (46), $\displaystyle\lambda^{*}$ — допустимое решение задачи (48). Тогда $\displaystyle c^{T}x^{*}\geq-b^{T}\lambda^{*}$.

Двойственная задача (48) имеет оптимальное решение тогда и только тогда, когда оптимальное решение имеет задача (46). Пусть $\displaystyle x^{*}$ — конечное оптимальное решение задачи (46), $\displaystyle\lambda^{*}$ — конечное оптимальное решение задачи (48). Тогда $\displaystyle c^{T}x^{*}=-b^{T}\lambda^{*}$.

Доказательства последних двух теорем см., например, в .

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

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

7 Оценка на множители Лагранжа

Пусть для задачи (30) выполняются условия регулярности Слейтера:

И пусть число $\displaystyle\gamma$ таково, что $\displaystyle\gamma=\min\limits_{i=1,\,\ldots,\,p}\left\{{-h_{i}\left(x^{\prime}\right)}\right\}$.

Из последнего неравенства получаем оценку на оптимальный множитель:

8 Геометрическая интерпретация

Определим множество значений целевой функции и ограничений задачи:

Тогда оптимум задачи (20) $\displaystyle f^{*}=f(x^{*})$ можно выразить следующим образом: