Методы оптимизации

Введение

В безусловной оптимизации локальный минимум гладкой функции ищется из естественного требования: в точке минимума не должно существовать малого сдвига, уменьшающего значение функции. Если $f:\mathbb{R}^{n}\to\mathbb{R}$ дифференцируема и $x^*$ является локальным минимумом, то обязательно

$$\nabla f(x^*) = 0.$$

Эта формула выражает простую геометрическую идею: градиент задаёт направление наискорейшего роста, а значит, если градиент не равен нулю, то в направлении $-\nabla f(x^*)$ функция убывает и точка не может быть минимумом.

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

Именно из этой идеи и рождается метод множителей Лагранжа, а затем и условия Каруша-Куна-Таккера. Они формализуют вопрос: как выглядит аналог условия $\nabla f(x^*)=0$, если разрешено двигаться только вдоль ограничений?

Задача условной оптимизации

Будем рассматривать общую задачу математического программирования

$$\min_{x\in\mathbb{R}^{n}} f_0(x),\quad\text{ при } f_i(x)\le 0,\ i=\overline{1,m}\; \text{ и }\; h_j(x)=0,\ j=\overline{1,p}$$

Допустимое множество определяется как

$$S=\{x\in\mathbb{R}^{n}\mid f_i(x)\le 0,\ h_j(x)=0\}.$$

Если безусловный минимум функции $f_0$ уже лежит в $S$, то ограничения в некотором смысле не мешают, и задача выраждается в безусловную оптимизацию, а вот когда безусловный минимум вне допустимого множества оптимальная точка часто лежит на границе $S$ (так как если мы не уперлись в допустимое множество, мы можем сделать шаг в направлении антиградиента), то есть часть ограничений-неравенств становится активной и начинает вести себя как равенства.

Почему появляются множители Лагранжа

Начнём с простейшего случая одного ограничения-равенства

$$\min_{x\in\mathbb{R}^{n}} f(x) \quad \text{при } h(x)=0.$$

Пусть $x^*$ — локальный минимум, причём $\nabla h(x^*)\neq 0$. Рассмотрим малое допустимое смещение $\delta x$. Чтобы не выйти из множества $h(x)=0$, необходимо, чтобы в первом порядке сохранялось равенство

$$h(x^*+\delta x)\approx h(x^*)+\langle \nabla h(x^*),\delta x\rangle = 0.$$

Так как $h(x^*)=0$, для допустимого направления должно выполняться

$$\langle \nabla h(x^*),\delta x\rangle = 0.$$

Значит, допустимые малые сдвиги ортогональны градиенту ограничения. С другой стороны, если бы существовало допустимое направление $\delta x$, в котором

$$\langle \nabla f(x^*),\delta x\rangle < 0,$$

то вдоль этого направления функция уменьшалась бы, и $x^*$ не могла бы быть точкой минимума. Следовательно, в точке локального минимума градиент функции должен быть ортогонален всем допустимым направлениям.

Но множество всех допустимых направлений — это подпространство, ортогональное $\nabla h(x^*)$. Если вектор ортогонален всему этому подпространству, то он должен лежать в линейной оболочке нормали к ограничению. Значит, существует число $\nu^*$ такое, что

$$\nabla f(x^*)+\nu^* \nabla h(x^*) = 0.$$

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

Лагранжиан и задача с ограничениями-равенствами

Чтобы записывать это условие компактно, вводят лагранжиан

$$L(x,\nu)=f(x)+\nu h(x).$$

Тогда найденное выше условие принимает вид

$$\nabla_x L(x^*,\nu^*)=0.$$

При этом само ограничение тоже должно выполняться:

$$h(x^*)=0.$$

Но последнее можно записать как

$$\nabla_\nu L(x^*,\nu^*)=0.$$

Поэтому для задачи с равенствами естественная система необходимых условий выглядит так:

$$\nabla_x L(x^*,\nu^*)=0, \qquad \nabla_\nu L(x^*,\nu^*)=0.$$

Для нескольких ограничений-равенств

$$h_j(x)=0,\quad j=1,\dots,p$$

лагранжиан принимает вид

$$L(x,\nu)=f(x)+\sum_{j=1}^{p}\nu_j h_j(x)=f(x)+\nu^\top h(x),$$

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

$$\nabla_x L(x^*,\nu^*)=0, \qquad h(x^*)=0.$$

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

Переход к ограничениям-неравенствам

Теперь рассмотрим задачу

$$\min_{x\in\mathbb{R}^{n}} f(x) \quad \text{при } g(x)\le 0.$$

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

Если в оптимальной точке $x^*$ ограничение неактивно, то есть

$$g(x^*)<0,$$

то вокруг $x^*$ существует маленькая окрестность, целиком лежащая в допустимом множестве. Значит, ограничение локально не влияет на задачу, и мы снова получаем обычное условие

$$\nabla f(x^*)=0.$$

Если же в оптимуме ограничение активно:

$$g(x^*)=0,$$

то двигаться можно только вдоль границы. Локально это уже почти та же геометрия, что и в задаче с равенством $g(x)=0$. Поэтому в этом случае должно существовать $\lambda^*\ge 0$ такое, что

$$\nabla f(x^*)+\lambda^*\nabla g(x^*)=0.$$

Знак $\lambda^*\ge 0$ не случаен. Если бы он был отрицательным, нормаль к ограничению указывала бы не в ту сторону: это соответствовало бы попытке компенсировать градиент функции в направлении, которое не блокируется допустимым множеством. Для задачи на минимум активное ограничение может только препятствовать спуску, а не помогать ему с внешней стороны, поэтому множитель должен быть неотрицательным.

Оба случая удобно объединяются условием

$$\lambda^* g(x^*)=0.$$

Это условие называется дополняющей нежёсткостью. Оно означает следующее:

• либо ограничение неактивно, то есть $g(x^*)<0$, и тогда обязательно $\lambda^*=0$;
• либо множитель положителен, и тогда ограничение обязано быть активным, то есть $g(x^*)=0$.

Именно эта логика позволяет перейти от метода Лагранжа для равенств к условиям KKT для неравенств.

Условия Каруша-Куна-Таккера

Для общей задачи

$$\min_{x\in\mathbb{R}^{n}} f_0(x)$$

при ограничениях

$$f_i(x)\le 0,\quad i=1,\dots,m, \qquad h_j(x)=0,\quad j=1,\dots,p$$

вводится лагранжиан

$$L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^{m}\lambda_i f_i(x)+\sum_{j=1}^{p}\nu_j h_j(x).$$

Если $x^*$ — локальный минимум и выполнены условия регулярности, то существуют множители $\lambda^*\in\mathbb{R}^{m}$ и $\nu^*\in\mathbb{R}^{p}$, для которых выполняются условия Каруша-Куна-Таккера:

$$\begin{array}{l} (1)\quad \nabla_x L(x^*,\lambda^*,\nu^*)=0,\\ (2)\quad f_i(x^*)\le 0,\\ (3)\quad h_j(x^*)=0,\\ (4)\quad \lambda_i^*\ge 0,\\ (5)\quad \lambda_i^* f_i(x^*)=0, \end{array}$$

Эту систему удобно читать по частям.

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

$$\nabla f_0(x^*) + \sum_{i=1}^{m}\lambda_i^* \nabla f_i(x^*) + \sum_{j=1}^{p}\nu_j^* \nabla h_j(x^*) = 0.$$

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

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

Дополняющая нежёсткость отбрасывает неактивные ограничения из стационарности: если $f_i(x^*)<0$, то автоматически $\lambda_i^*=0$, и соответствующее ограничение не влияет на баланс градиентов.

В результате KKT можно воспринимать как строгую запись интуиции: в оптимуме никакое допустимое направление не должно давать спуск.

Почему KKT естественны

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

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

Условия регулярности

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

Одно из самых простых условий — линейная квалификация ограничений: если все $f_i$ и $h_j$ аффинны, то дополнительных проблем не возникает, и стандартный вывод KKT работает.

Более общее и часто используемое условие — линейная независимость градиентов активных ограничений (LICQ). Оно требует, чтобы в точке $x^*$ векторы

$$\nabla f_i(x^*), \quad i\in I(x^*), \qquad \nabla h_j(x^*), \quad j=1,\dots,p,$$

были линейно независимы, где

$$I(x^*)=\{i\mid f_i(x^*)=0\}$$

— множество активных ограничений-неравенств.

Смысл LICQ в том, что активные ограничения не должны локально дублировать друг друга. Если они вырождены, то нормальное пространство определяется неоднозначно, множители могут не существовать или быть неединственными, и стандартная теория ломается.

Условие Слейтера и выпуклый случай

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

• $f_0$ выпукла;
• все $f_i$ выпуклы;
• все $h_j$ аффинны.

Тогда любая локальная точка минимума автоматически является глобальной. Но этого ещё недостаточно, чтобы KKT были полным критерием оптимальности. Для этого нужно условие Слейтера: существует такая точка $\bar{x}$, что

$$h_j(\bar{x})=0,\quad j=1,\dots,p,$$

и одновременно

$$f_i(\bar{x})<0,\quad i=1,\dots,m.$$

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

Условие Слейтера важно потому, что оно гарантирует нулевой зазор двойственности. А это означает, что у задачи есть достаточно сильная двойственная структура, чтобы KKT стали не только необходимыми, но и достаточными условиями оптимальности.

Доказательство достаточности KKT в выпуклом случае

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

Пусть функции удовлетворяют выпуклым предположениям, и пусть найдены $x^*$, $\lambda^*$, $\nu^*$, удовлетворяющие KKT. Докажем, что $x^*$ — глобальный минимум.

Возьмём произвольную допустимую точку $x$. Выпуклость $f_0$ даёт неравенство первого порядка

$$f_0(x)\ge f_0(x^*) + \langle \nabla f_0(x^*), x-x^* \rangle.$$

Из стационарности KKT имеем

$$\nabla f_0(x^*) = -\sum_{i=1}^{m}\lambda_i^* \nabla f_i(x^*) - \sum_{j=1}^{p}\nu_j^* \nabla h_j(x^*).$$

Подставим это в предыдущее неравенство:

$$f_0(x)\ge f_0(x^*) - \sum_{i=1}^{m}\lambda_i^* \langle \nabla f_i(x^*),x-x^*\rangle - \sum_{j=1}^{p}\nu_j^* \langle \nabla h_j(x^*),x-x^*\rangle.$$

Теперь используем выпуклость каждого $f_i$:

$$f_i(x)\ge f_i(x^*) + \langle \nabla f_i(x^*),x-x^*\rangle,$$

откуда

$$\langle \nabla f_i(x^*),x-x^*\rangle \le f_i(x)-f_i(x^*).$$

Для аффинных $h_j$ имеем точное равенство

$$h_j(x)=h_j(x^*)+\langle \nabla h_j(x^*),x-x^*\rangle.$$

Так как и $x$, и $x^*$ допустимы, то $h_j(x)=h_j(x^*)=0$, поэтому

$$\langle \nabla h_j(x^*),x-x^*\rangle = 0.$$

Следовательно,

$$f_0(x)\ge f_0(x^*) - \sum_{i=1}^{m}\lambda_i^*\bigl(f_i(x)-f_i(x^*)\bigr).$$

Раскроем сумму:

$$f_0(x)\ge f_0(x^*) - \sum_{i=1}^{m}\lambda_i^* f_i(x) + \sum_{i=1}^{m}\lambda_i^* f_i(x^*).$$

Теперь используем два свойства KKT.

Во-первых, по двойственной допустимости $\lambda_i^*\ge 0$, а по прямой допустимости $f_i(x)\le 0$. Значит,

$$-\lambda_i^* f_i(x)\ge 0.$$

Во-вторых, по дополняющей нежёсткости

$$\lambda_i^* f_i(x^*)=0.$$

Поэтому

$$f_0(x)\ge f_0(x^*).$$

Так как $x$ была произвольной допустимой точкой, $x^*$ действительно является глобальным минимумом.

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

Замечание о вторых порядках

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

$$\nabla_{xx}^{2}L(x^*,\lambda^*,\nu^*).$$

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

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

Пример: проекция на единичный симплекс

Рассмотрим задачу

$$\min_{x\in\mathbb{R}^{n}} \frac{1}{2}\|x-y\|_{2}^{2}$$

при ограничениях

$$x^\top \mathbf{1}=1, \qquad x\ge 0.$$

Это задача проекции точки $y$ на единичный симплекс. Она важна не только как упражнение на KKT: такая проекция регулярно возникает в задачах вероятностного моделирования, оптимизации на вероятностных векторах и методах зеркального спуска.

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

Запишем лагранжиан:

$$L(x,\lambda,\nu)=\frac{1}{2}\|x-y\|_{2}^{2} - \sum_{i=1}^{n}\lambda_i x_i + \nu(x^\top \mathbf{1}-1).$$

Здесь знак у $\lambda_i$ выбран так, чтобы ограничение $x_i\ge 0$ было переписано в стандартной форме $-x_i\le 0$.

Условия KKT дают:

$$\frac{\partial L}{\partial x_i}=x_i-y_i-\lambda_i+\nu = 0,$$ $$\lambda_i\ge 0,$$ $$\lambda_i x_i = 0,$$ $$x_i\ge 0, \qquad \sum_{i=1}^{n}x_i=1.$$

Теперь разберёмся, что из этого следует. Из стационарности

$$x_i = y_i + \lambda_i - \nu.$$

Если $x_i>0$, то по дополняющей нежёсткости $\lambda_i=0$, и тогда

$$x_i = y_i - \nu.$$

Если же $x_i=0$, то из стационарности получаем

$$\lambda_i = \nu - y_i \ge 0,$$

то есть

$$y_i-\nu \le 0.$$

Оба случая объединяются одной формулой:

$$x_i = \max(y_i-\nu,0).$$

Остаётся подобрать число $\nu$ так, чтобы выполнялось условие нормировки:

$$\sum_{i=1}^{n}\max(y_i-\nu,0)=1.$$

Это и есть окончательное описание проекции на симплекс. Смысл формулы очень красив: мы одновременно сдвигаем все координаты на одно и то же значение $\nu$, а затем отсекаем отрицательные. Геометрически это ровно то, что нужно, чтобы оказаться на гиперплоскости суммы, не выходя из неотрицательного ортанта.

Практически $\nu$ ищут после сортировки координат $y$, что даёт алгоритм сложности $O(n\log n)$.