Существование рационально --- Метод множителей Лагранжа

Метод множителей Лагранжа предназначен для решения задач условной оптимизации (максимум-минимизация).

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

Известно, что между целью и параметрами задачи существует связь. y=x^2 , то мы можем легко узнать, что когда x=0 , оптимальная цель $y=min \ x^2=0$ .Но если мы добавим ограничение в этот процесс оптимизации: $x-1 \geq 0$ , это,Если это ограничение должно выполняться, найдите минимальное значение исходной функции. Тогда эту проблему нужно решать по-другому. На данный момент мы ввелиМетод множителей Лагранжа(Метод множителя Лагранжа), также называемый в некоторых местахМетод множителей Лагранжа.

Рассмотрим простейший пример

Наиболее простым в данном случае является метод множителей Лагранжа при ограничении одним равенством, необходимо обратить внимание на процесс вычисления, и приведу полный пример на всеобщее обозрение:

Мы устанавливаем множитель Лагранжа равным $\lambda$ , то существует следующая функция Лагранжа:

следующий за $x,y,\lambda$ Три переменные частично дифференцируются:

\nabla_{x,y,\lambda}L(x,y,\lambda)=\left( \frac{\partial L}{\partial x},\frac{\partial L}{\partial y},\frac{\partial L}{\partial \lambda} \right)

=(2xy+2 \lambda x,x^2+2 \lambda y,x^2+y^2-3)

Пусть частные дифференциалы равны 0, тогда:

\nabla_{x,y,\lambda}L(x,y,\lambda)=0 \; \iff \begin{cases} 2xy+2\lambda x =0, \quad (i) \\ x^2+2 \lambda y=0, \quad (ii) \\ x^2+y^2-3=0, \quad (iii) \end{cases}

решать:

(\pm \sqrt 2,1,-1);(\pm \sqrt 2,-1;1);(0, \pm \sqrt 3,0)

заменять f(x,y) окончательное решение f(x,y) Несколько возможных значений 2,-2,0 , то это набор максимального и минимального значений, видно, что $\max_{x,y} \; f(x,y) =2$ , приведенная выше картинка полностью объяснила мою серию расчетов.

Посмотрите еще раз на ограничения неравенства и условия KKT.

Ситуация будет немного сложнее.Для ограничений неравенства, пока выполняются определенные условия, метод множителя Лагранжа все еще может использоваться для решения, здесь условиеККТ условия(условия Каруша-Куна-Таккера). Условия KKT названы в честь людей, поэтому не обращайте внимания на значение их имен. Я видел много блогов на форумах, которые используют метод множителя Лагранжа для ограничений равенства и условный метод KKT для ограничений неравенства, который не является строгим. Условие ККТ — это просто условие, а не метод. Методы, используемые как для задач оптимизации с ограничениями равенства, так и для задач неравенства, представляют собой множители Лагранжа.

Давайте рассмотрим такую задачу с ограничениями неравенства:

Соответствующая ему функция Лагранжа выглядит следующим образом:

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

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

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

Мы смотрим на первое изображение, чтобы представить первый случай, центр синего круга находится внутри красного круга. Таким образом, ограничения не играют роли в ограничениях, и оптимальное решение после ограничения остается исходным оптимальным решением. Для второго графика мы видим, что синий центр находится за пределами красной области. Конечно, это также включает случай только на красной рамке. Почему эти два случая сгруппированы вместе? Давайте посмотрим дальше: мы должны удовлетворить ограничения, то есть мы должны найти оптимальное решение в красном диапазоне. Даже если это оптимальное решение не является оптимальным для исходной функции. Поскольку исходная функция является выпуклой функцией, она представляет собой гладкий одиночный экстремум. Тогда теоретически, в любом направлении от экстремального значения, чем ближе мы к экстремальному значению, тем лучше значение. Итак, мы знаем, что это оптимальное значение будет находиться на границах ограничений. это g(x)=0 когда. В это время оно снова становится ограничением равенства.

Приведенные выше два случая означают, что либо допустимое решение попадает на границу ограничения, либо g(x)=0 , либо допустимое решение попадает в область ограничений, и в этом случае ограничение не работает, пусть $\lambda = 0$ Просто удалите ограничения, так что в любом случае вы получите:

В этом случае наше ограничение неравенства является тем же решением, что и ограничение равенства. В данном случае этоТо, что мы называем состоянием ККТВниз. Итак, резюмируем условия ККТ для этой задачи:

\begin{cases} \nabla_x L(x,\lambda) =0, \quad (I) \\ λg(x)=0, \quad (II) \\ g(x) \leq 0, \quad (III) \\ \lambda \geq0, \quad (IV) \\ \end{cases}

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

Требование, которому должна соответствовать приведенная выше формула, - это множитель Лагранжа. $\lambda\geq0$ , эту задачу можно привести наглядный пример, предположим, вы идете подниматься на гору, цель вершина горы, но есть препятствие, преграждающее путь к вершине горы, поэтому вы можете подняться только вдоль препятствия до положение как можно ближе к вершине горы, а затем смотрим на вершину горы Вздох, здесь вершина горы — допустимое решение целевой функции, а препятствие — граница функции ограничений. В это время направление уклона должно указывать на вершину горы в том же направлении, что и уклон препятствия.Следующий рисунок описывает эту ситуацию:

Конечно, более общий вопрос:

s.t. \quad c_{i}(x)\leq0 \ ,\quad i=1,2,...,k

\quad \qquad h_{j}(x)=0 \ ,\quad j=1,2,...,l

У нас есть более полное условие ККТ:

$\begin{cases} \nabla_x L(x,\alpha_i,\beta_i) =0, \qquad \qquad \quad (1) \\ \alpha_i c_i(x) = 0, \quad i=1,2,...,k \quad(2) \\ h_j(x) = 0, \qquad j=1,2,...,l \quad (3) \\ c_i(x) \leq0, \quad i=1,2,...,k \qquad(4) \\ \alpha_i \geq0, \quad \quad \ i=1,2,...,k \qquad(5) \\ \end{cases}$

Допустимое решение при ограничениях неравенства может быть получено путем минимизации лагранжиана после выполнения условия ККТ. Условие KKT выглядит много, но на самом деле его очень легко понять:

Необходимые условия лагранжиана для получения допустимых решений;

Это интересное ограничение приведенного выше анализа, называемое релаксационным условием дополнительности;

начальные ограничения;

начальные ограничения;

Условия, которым должен удовлетворять множитель Лагранжа, ограниченный неравенством.

Основными условиями ККТ являются (3) и (5).Пока эти два условия выполняются, метод множителей Лагранжа может быть использован напрямую.Отсюда исходит опорный вектор в SVM.Следует отметить, что условие ККТ является то же, что проблема двойственности также имеет большую связь

Как появился метод множителей Лагранжа?

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

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

У нас есть следующая функция Лагранжа для этого многомерного ограничения:

L(x,\alpha,\beta)=f(x)+ \sum_{i=1}^k \alpha_{i} c_{i}(x)+\sum_{j=1}^l\beta_{j}h_{j}(x)

Предположим, что задано,еслинарушает ограничения исходной задачи, т.е.сделать $c_{i}(w)>0$ или естьсделать $h_{j}(w) \neq0$ , то есть

\max_{\alpha,\beta:\alpha_{i} \geq0} \left[ f(x)+\sum_{i=1}^k \alpha_{i}c_{i}(x)+ \sum_{j=1}^l\beta_{j}h_{j}(x) \right]=\infty

потому что есливводить ограничения $c_{i}>0$ , ты можешь сделать $\alpha_{i} \rightarrow+ \infty$ , есливводить ограничения $h_{j}(x) \neq0$ , тогда пусть $\beta_{j}$ сделать $\beta_{j}h_{j}(x) \rightarrow +\infty$ , а остальные $\alpha_{i},\beta_{j}$ Оба принимаются за 0. Таким образом, те, которые не удовлетворяют ограничениям, принимаются как $\infty$ , и наоборот, удовлетворяя ограничениям, положим $\alpha,\beta$ Установите на 0, чтобы функция Лагранжа была такой же, как исходное решение функции.

Приведенное выше утверждение подробно иллюстрирует идею метода множителей Лагранжа.

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

так:

Существование имеет смысл. В чем смысл? Ответ: самый эффективный из известных методов решения подобных проблем.

Условие KKT в двойном ручном толчке было перемещено в«Двойственность Лагранжа»., друзья, которые заинтересованы, могут прийти и посмотреть.

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

[1] «Статистические методы обучения», Ли Ханг, март 2012 г., 1-е издание.

[2].Метод множителей Лагранжа и условие ККТ метода условной оптимизации

[3].[Интуитивное и подробное объяснение] Умножение Лагранжа и условия ККТ

[4].Метод множителей Лагранжа и условия ККТ

[5] «Машинное обучение», Чжоу Чжихуа, первое издание, январь 2016 г.