Ограниченная оптимизация (Ограниченная оптимизация)

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

Ограниченная оптимизация

Неограниченная оптимизация

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

в, $x\in R^N$ , f(x) является выпуклой функцией, решить такую задачу очень просто, нужно только найти $\nabla_xf(x) =0$ изПросто нажмите.

ограничения равенства

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

\begin{align} &\min_x f(x) \\ &s.t \quad h_i(x) = 0 , \quad i=1,2,...,m \end{align} \tag{2}

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

Пунктирная линия на рисунке f(x,y) контуры , а ограничения h(x,y)=0 является ограничением. Мы знаем, что f(x,y) Проблема оптимизации должна быть в h(x,y) = 0 Решаем при условии , то есть пунктирная линия на рисунке должна пересекать или касаться зеленой линии Очевидно, мы можем видеть, что когда пунктирная линия касается зеленой линии, при условии ограничения h(x,y) =0 Вниз, f(x,y) получить минимальное значение.

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

\nabla_{x,y} f(x,y) + \alpha\nabla_{x,y}h(x,y) = 0 \\ \tag{3}

расширяться доРазмер имеет:

\nabla_{x} f(x) + \alpha\nabla_{x}h(x) = 0 \\ \tag{4}

Есть $h_{i}(x) = 0$ , оптимальное решение этой оптимизационной задачи получается немедленно.

Итак, мы можем сделать исходную функцию:

L(x,\alpha) = f(x) + \sum^m_{i=1} \alpha_i h_i(x) \tag{5}

То есть задача трансформируется в функцию L(x) Оптимальное решение , то есть:

\begin{align} \nabla_xL(x,\alpha) = 0 \\ \nabla_\alpha L(x,\alpha) = 0 \end{align} \tag{6}

получитьи $\alpha$ После этогозаменять f(x) Допустимое решение получается вМетод множителей Лагранжа(Lagrangian Multiplier Method),в $\alpha=\alpha_1^T,\alpha_2^T,...,\alpha_m^T$ называются множителями Лагранжа.

Ограничения неравенства

Затем, если вы добавите ограничения неравенства:

\begin{align} &\min_x f(x) \\ &s.t \quad g_i(x) \le 0 , \quad i=1,2,...,m \end{align} \tag{7}

Опять же, мы сводим проблему к двум измерениям:

Очевидно, допустимое решение может лежать в $g(x) \le 0$ Внутри или на границе, то есть следующие две ситуации:

видимый:

когда допустимое решениепадатьВ районе , в это время прямая минимизацияТы сможешь;
когда допустимое решениепадатьТо есть на границе это эквивалентно задаче оптимизации с ограничениями равенства.

Итак, мы можем получить:

немедленно $\beta =0$ , ограничение в данный момент не работает; $\beta \neq 0$ эквивалентно ограничению равенства.

Кроме того, в ограничениях-равенствах мы не накладывали ограничений на множители, а в ограничениях-неравенствах имеем:

Как видно из рисунка, для минимизации f(x) , область ограничений $g(x) \le 0$ Нормальный вектор должен быть таким же, как f(x) Отрицательный градиент находится в том же направлении, то есть:

\begin{align} -\nabla_x f(x) &= \beta \nabla_x g(x) \\ \beta &\ge 0 \end{align} \tag{9}

Следовательно, подобно задаче оптимизации с ограничениями равенства, задача оптимизации с ограничениями неравенства может быть решена методом множителей Лагранжа при выполнении определенных условий, и это условиеККТ условия(Karush-Kuhn-Tucker conditions).

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

\begin{align} \min_x &f(x) \\ s.t. \ &h_i(x) = 0, \qquad i=1,2,...,m\\ &g_j(x) \le 0, \qquad j=1,2,...,k\\ \end{align} \tag{10}

Напишите функцию Лагранжа:

L(x,\alpha,\beta) = f(x) + \sum^m_{i=1}\alpha_i h_i(x) + \sum^k_{j=1}\beta g_i(x) \tag{11}

На основании вышеприведенного анализа имеем следующееККТ условия:

\begin{align} \nabla_x L(x,\alpha,\beta) = 0 \\ \beta_j g_j(x) =0 \\ h_i(x) = 0 \\ g_j(x) \le 0 \\ \beta_j \ge0 \end{align} \tag{12}

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

двойная проблема

В теории оптимизации целевая функция имеет вид f(x) Задача оптимизации при ограничениях может быть преобразована в соответствующуюдвойная проблема(dual problem), в то время как исходный вопрос называлсяоригинальный вопрос(primal problem), а двойственная задача обладает следующими хорошими свойствами:

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

оригинальный вопрос

Мы даем задачу оптимизации с ограничениями неравенства:

\begin{align} \min_x &f(x) \\ s.t. \ &h_i(x) = 0, \qquad i=1,2,...,m\\ &g_j(x) \le 0, \qquad j=1,2,...,k\\ \end{align}

Задайте функцию Лагранжа:

L(x,\alpha,\beta) = f(x) + \sum^m_{i=1}\alpha_i h_i(x) + \sum^k_{j=1}\beta_j g_j(x)

мы знаем h_i(x) =0 ,и $\beta_j \ge0 ,g_j(x)\le0$ который $\beta_j g_i(x) \le0$ ,Так есть:

f(x) = \max_{\alpha,\beta;\beta\ge0} L(x,\alpha,\beta) > L(x,\alpha,\beta) \tag{13}

Таким образом, наша задача оптимизации превращается в:

\min_x f(x) = \min_x \max_{\alpha,\beta;\beta\ge0} L(x,\alpha,\beta) \tag{14}

Это наш изначальный вопрос.

двойная проблема

Обозначим решение исходной задачи как $p^{\ast}$ , здесь определяетдвойная функция:

D(\alpha,\beta) = \min_xL(x,\alpha,\beta) \tag{15}

Затем мы определяем двойственную задачу:

\max_{\alpha,\beta;\beta\ge0} \min_x L(x,\alpha,\beta) \tag{16}

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

d^{*} =\max_{\alpha,\beta;\beta\ge0}D(\alpha,\beta) \tag{17}

Легко иметь:

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

В отличие от слабой двойственности существуетсильная двойственность(strong duality),который

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

Слейтер условие: существует x такой, что ограничение неравенства $g(x)\le0$ строго установлено, т.е..

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

(Исходная задача в SVM — это задача выпуклой оптимизации (квадратичное программирование также является задачей выпуклой оптимизации), а условие Слейтера в SVM относится к существованию гиперплоскости, разделяющей данные).
Но для обеспечения $d^{_*}$ является оптимальным решением, а также должно удовлетворять условию ККТ:

мы предполагаем, что $x^{\ast}$ и $\alpha^{\ast},\beta^{\ast}$ являются оптимальными решениями исходной задачи (не обязательно выпуклой) и двойственной задачи соответственно и удовлетворяют сильной двойственности, то удовлетворяет соответствующее экстремальное соотношение:

\begin{aligned} f(x^*) &= d^* = p^* =D(\alpha^*,\beta^*) \\ &=\min_x f(x)+ \sum_{i = 1}^m \alpha_i^*h_i(x) + \sum_{j=1}^n\beta_j^*g_j(x) \\ & \le f(x^*)+ \sum_{i = 1}^m \alpha_i^*h_i(x^*) + \sum_{j=1}^n\beta_j^*g_j(x^*) \\ &\le f(x^*) \end{aligned} \tag{20}

Учитывая первое неравенство, мы знаем h_i(x)=0 , вы можете получить:

\sum_{j=1}^n\beta_j^*g_j(x^*) \ge 0 \tag{21}

А также: $\sum_{j=1}^n\beta_j^\ast g_j(x^\ast) \le 0$ , так

\sum_{j=1}^n \beta_j^*g_j(x^*) = 0 \tag{22}

потому что $x^{\ast}$ да f(x) точка минимума , поэтому

Комбинируя вышеизложенное и начальные ограничения, мы имеем:

\begin{align} \nabla_x L(x,\alpha,\beta) = 0 \\ \beta_j g_j(x) =0 \\ h_i(x) = 0 \\ g_j(x) \le 0 \\ \beta_j \ge0 \end{align} \tag{24}

которыйККТ условия.

Использованная литература:

[1] ooon Blog Park: метод множителей Лагранжа и условие KKT метода условной оптимизации [EB/OL].woo woo woo.cn blog on.com/oh oh oh you/fear/5721… , 2016-07-30/2018-7-30.

[2] ooon Блог Garden: Двойственность Лагранжа [EB/OL].woo woo woo.cn blog on.com/oh oh oh you/fear/5723… , 2016-07-31/2018-7-30.

[3] feilong_csdn.CSDN: базовые знания о методе опорных векторов (SVM) (KKT, Slater, Dual) [EB/OL].blog.CSDN.net/Flying Dragon_Birthplace…, 2017-03-16/2018-7-30.