Множители Лагранжа, условия ККТ и двойственность — интуитивно объяснены

Интуитивное объяснение множителей Лагранжа, условий ККТ и двойственности

Ваш ключ к пониманию SVM, регуляризации, PCA и многих других концепций машинного обучения

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

Независимая оптимизация

В независимой оптимизации нам дана многопеременная функция f(u), и мы хотим найти значение вектора u*, где значение функции f(u*) является оптимальным (максимальным или минимальным).

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

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

• Mой опыт работы с DevOps и DataOps
• Введение в логистическую регрессию в PySpark
• 5 визуализаций с помощью Python для отображения одновременных изменений в геопространственных данных

Осуществление независимой оптимизации заданной многопеременной функции f(u) возможно путем решения ∇ᵤf(u) = 0. Если f(u) является функцией от n переменных (u₁, u₂,…,uₙ), то это система из n уравнений:

Когда эти уравнения решены, возвращается оптимальное решение u*=(u*₁,u*₂,…,u*ₙ), которое является местом нахождения оптимального значения (например, минимума).

Чтобы увидеть, откуда это происходит, вспомните следующее:

• Нормальный вектор к касательной плоскости в любой точке u имеет вид (∂f(u)/∂u₁, ∂f(u)/∂u₂, …, ∂f(u)/∂uₙ, f(u))
• Касательная плоскость в любом минимуме или максимуме является горизонтальной (визуально очевидно)
• Следовательно, каждый раз, когда ∇ᵤf(u) = 0, существует горизонтальная касательная плоскость в этой точке и, следовательно, это должно быть минимумом, который мы ищем.

Еще один способ объяснить это, который будет полезен в ближайшем будущем, заключается в том, чтобы заметить, что градиент указывает в направлении наибольшего возрастания (И в противоположном направлении наибольшего убывания). Таким образом, когда ∇ᵤf(u) = 0, либо невозможно (не существует направления, в котором бы можно) увеличить функцию из этой точки (то есть, находясь в максимуме), либо уменьшить функцию из этой точки (то есть, находясь в минимуме).

Краткое резюме безоговорочной оптимизации

Дано: f(u)Требуется: u, при котором f(u) минимальноПодход: Решите ∇ᵤf(u) = 0, так как это имеет место в минимуме

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

В этом типе оптимизации нам задается равенственное ограничение вида g(u)=0 или g(u)≤0 (иначе мы можем привести его к этой форме, переставив термины или умножив на отрицательное число), и мы хотим оптимизировать только те точки, которые удовлетворяют условию.

Обычно предполагается, что равенственные ограничения g(u)=0 являются аффинными (обобщение линейных) и неравенственные ограничения g(u)≤0 связаны с выпуклыми функциями, чтобы весь оптимизационный проблема была выпуклой (в противном случае только само то, что f(u) выпуклая, может быть недостаточно, чтобы гарантировать одно оптимальное значение).

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

В этом случае нам задается многомерная функция f(u) и ограничение g(u)=0, и мы хотим найти точку u*, где g(u*)=0 и f(u*) минимальна (то есть, наименьшая точка, при условии ограничения).

Например, в показанном примере целевая функция имеет вид f(u₁,u₂) = u₁+ u₂ (3D плоскость), а ограничением является u²₁+ u²₂=1 (2D окружность). Цель состоит в том, чтобы найти точку (u₁, u₂), соответствующую самой низкой точке на плоскости, где u²₁+ u²₂=1 (то есть, (u₁, u₂), где наименьшая точка на окружности, проецируемой на плоскость, находится).

Один из подходов к решению этого типа задач ограниченной оптимизации – использование метода множителей Лагранжа. Простыми словами, теорема множителей Лагранжа гласит, что любое решение u* оптимизационной задачи вида:

Минимизировать f(u) при условии g(u)=0

должно удовлетворять уравнению ∇ᵤL(u*,λ)=0 для некоторого λ∈R (и тривиально, g(u*)=0), где L – функция Лагранжа, которая задается формулой L(u,λ)=f(u)+λg(u). Это предполагает, что ∇ᵤg(u*)≠0.

Из этого следует, что мы можем решать задачи условной оптимизации с ограничениями равенства следующим образом (при условии, что ∇ᵤg(u*) ≠ 0):

1. Запишите лагранжианскую функцию L(u,λ) = f(u) + λg(u).
2. Решите n+1 уравнений, полученных из ∇ᵤL(u,λ) = 0 (n уравнений) с g(u) = 0, чтобы найти n+1 неизвестных u*₁,u*₂,…,u*ₙ,λ.
3. Решение представляет собой u*=(u*₁,u*₂,…,u*ₙ).

λ называется множителем Лагранжа. Нам нужно найти его, потому что он является частью системы, которая даёт решение u*.

Вы можете решить пример, соответствующий рисунку выше, здесь. В этом примере задача не выпуклая и решение может дать любой минимум или максимум. Обратите внимание, что шаги (1) и (2) выше эквивалентны выполнению неограниченной оптимизации для L(u,λ) = f(u) + λg(u). То есть, устанавливая:

∇ L(u,λ) =(∂L(u)/∂u₁, ∂L(u)/∂u₂, …, ∂L(u)/∂uₙ, ∂L(u)/∂λ) = 0

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

Обоснование

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

Мы знаем, что ∇ f(u) указывает в противоположном направлении наибольшего убывания (в направлении наибольшего возрастания). Однако в нашем случае мы можем двигаться только в допустимой области (точки, удовлетворяющие ограничению); поэтому, чтобы минимизировать функцию при условии ограничения, мы должны двигаться в направлении наибольшего убывания вдоль кривой ограничения (чтобы никогда не выходить из допустимой области и достичь минимума).

Предположим, что направление касательной в точке u на кривой ограничения задается вектором r(u), тогда вспоминая формулу для проекции вектора (векторная проекция), мы хотим двигаться в противоположном направлении проекции (∇ f(u) проекция на r(u)):

Аналогично случаю без ограничений, должно стать очевидным, что, когда это равно 0, мы не можем двигаться в любом направлении вдоль ограничения, чтобы дальше увеличить f(u) (если на максимуме) или уменьшить его (если на минимуме).

Ясно, что для того, чтобы это было равно нулю, нам нужно r(u) ≠ 0 (чтобы знаменатель не был равен нулю) и ∇ f(u) ⋅ r(u) = 0. Для второго утверждения мы знаем, что нормальный вектор на кривой ограничения ∇ g(u) перпендикулярен касательной r(u). Таким образом, все, что нам нужно, это то, чтобы ∇ f(u) было параллельно ∇ g(u).

Таким образом, при оптимальной точке u* должны соблюдаться следующие условия:

1. Нормаль к ограничению ненулевой: ∇ g(u*) ≠ 0 (чтобы r(u*) ≠ 0)
2. Ограничение удовлетворено: g(u*) = 0 (тривиальное условие)
3. ∇ f(u*) ∥ ∇ g(u*): существует некоторое действительное β, такое что ∇ f(u*) = β∇ g(u*)

Обратите внимание, что переставляя слагаемые и переименовывая -β, (3) эквивалентно утверждению “существует такое реальное λ, что ∇ f(u)+λ∇ g(u)=0”. Другими словами, ∇ᵤL(u,λ) = 0, и таким образом, мы интуитивно получаем теорему о множителях Лагранжа для одного ограничения (прокрутите вверх, если это нужно).

Обратите внимание, что первое условие называется квалификацией ограничения. Если ограничение не удовлетворяет этому условию в точке, где (2) и (3) удовлетворены, то нет гарантий, что эта точка оптимальна, так как проекция там не определена.

Множество равенственных ограничений

Когда присутствуют несколько ограничений g₁(u), g₂(u),…,gₖ(u), метод плавно обобщается следующим образом:

1. Запишите Лагранжиан L(u,λ₁,λ₂,…,λₖ) = f(u) + λ₁g₁(u) + λ₂g₂(u) +…+λₖgₖ(u)
2. Решите n+k уравнений, установив ∇ᵤL(u,λ₁,λ₂,…,λₖ) = 0 (n уравнений) с g₁(u)=0, g₂(u)=0, …, gₖ(u)=0, чтобы найти n+k неизвестных u*₁,u*₂,…,u*ₙ, λ₁,λ₂,…,λₖ
3. Решение – это u*=(u*₁,u*₂,…,u*ₙ)

Предположение∇ g(u*)≠0 обобщается на то, что ∇ g₁(u), ∇ g₂(u),…,∇ gₖ(u) должны быть линейно независимыми. Это называется LICQ (линейная независимость ограничений).

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

Вещи не становятся гораздо сложнее, когда мы имеем дело с ограничением неравенства вида g(u)≤0. В этом случае мы хотим оптимальную точку f(u), которая удовлетворяет g(u)≤0.

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

Вместо решения двух условий множителей Лагранжа (2, 3) мы решаем набор из четырех условий, называемых условиями KKT, которые обобщают случай множителей Лагранжа. Мы можем вывести их следующим образом:

Заметим, что с произвольной гиперповерхностью f(u) и ограничением g(u)≤0 существуют ровно две возможности, предполагая выпуклую гладкую функцию с одним оптимумом:

1. Оптимальная точка uᴾ находится внутри допустимой области.

• В этом случае решением оптимизационной проблемы u* должна быть uᴾ, и должно выполняться условие g(u*)<0 (левое изображение).
• Невозможно найти более оптимальную точку в допустимой области, потому что uᴾ является наиболее оптимальной точкой (например, минимальной) во всей области (области определения) функции f(u).

2. Оптимальная точка uᴾ находится за пределами допустимой области.

• В этом случае функция f(u) должна строго убывать в допустимой области, если эта точка является максимумом (иначе может возникнуть еще одна оптимальная точка)
• Функция f(u) должна строго возрастать в допустимой области, если эта точка является минимумом (иначе может возникнуть еще одна оптимальная точка)
• Таким образом, оптимальная точка u* должна находиться на границе допустимой области, так как внутри она улучшаться не будет (должно выполняться условие g(u*) = 0)

В первом случае очевидно, что решение оптимизационной проблемы эквивалентно решению неконтролируемой версии этой проблемы.

∇ᵤf(u) = 0

Мы говорим, что ограничение является “неактивным”, потому что оно не влияет на оптимизационную проблему.

Во втором случае очевидно, что решение оптимизационной проблемы эквивалентно решению версии с ограничением равенства (метод множителей Лагранжа).

Единственное условие для этого случая состоит в том, что λ должно быть ≥ 0 для минимизации и ≤ 0 для максимизации. Для минимизации это означает, что ∇ᵤf(u) и ∇ᵤg(u) указывают в противоположном направлении (т.е. β в∇ᵤ f(u) = β∇ ᵤg(u) ≤0), что должно быть верно, поскольку ∇ᵤg(u) указывает на положительную сторону ограничения g(u)≥0 (основное свойство); тем временем, ∇ᵤ f(u) указывает на отрицательную сторону ограничения, потому что именно там функция f(u) возрастает. Подобный аргумент легко можно обобщить на случай максимизации.

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

1. Записать функцию Лагранжа L(u,λ)=f(u)+λg(u)
2. Установить ∇ᵤL(u,λ) = 0 (n уравнений) и g(u)≤0
3. Решить для решения (u*₁,u*₂,…,u*ₙ,λ), где применяются один из вышеуказанных случаев:

• λ=0 и g(u*)<0 (первый случай, так как λ=0 означает, что ∇ᵤL(u,λ) = ∇ᵤf(u) = 0, поэтому шаги 1 и 2 эквивалентны решению ∇ᵤf(u) = 0)
• g(u*)=0 и λ≥0 (второй случай, так как g(u)=0 означает, что применение метода Лагранжа правильно, и в этом мы убедились)

Можно сформулировать эти два пункта следующим образом: должны выполняться условия g(u*)≤0 и λ≥0, а также должно выполняться условие λg(u*)=0 (одно из λ или g(u*) должно быть равно нулю). Из этого следует, что для оптимальной точки u* по задаче оптимизации вида:

Минимизировать f(u) при условии g(u)≤0

Мы ожидаем, что для оптимальной точки u* должны выполняться следующие четыре условия:

1. Стационарность: ∇ᵤL(u*,λ) = 0
2. Примитивность: g(u*)≤0
3. Дуальная примитивность: λ≥0
4. Взаимное ослабление: λg(u*)=0

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

• Если точка удовлетворяет этим условиям (например, находится путем их совместного решения), то это достаточно, чтобы доказать, что точка является оптимальной (не нужно искать дальше для выпуклых задач).
• Тем не менее, эти условия не являются необходимыми для того, чтобы точка была оптимальной. Возможно, что решение условий не дает результата, когда на самом деле существует оптимальная точка, не удовлетворяющая им. Например, рассмотрим функцию f(x) = x и ограничение x² ≤ 0 (оба примера KKT из этого и другого примера решены в данном документе)

Как только мы применяем условие квалификации ограничений, такое как LICQ (как было сказано ранее), мы можем гарантировать, что условия KKT являются и достаточными, и необходимыми. Альтернативное условие квалификации ограничений, которое легче проверить, – это условие Слейтера, которое гарантирует, что KKT является необходимым и достаточным для выпуклых задач.

Условие Слейтера просто гласит, что множество допустимых значений должно иметь внутреннюю точку. То есть, для ограничения g(u)≤0 функция должна иметь точку(и) в области определения f(u), удовлетворяющую g(u)<0. Это базовое условие, которое почти всегда выполняется в реальных проблемах (но не в приведенном выше контрпримере), и это означает, что KKT редко пропустит нахождение оптимального решения.

Несколько ограничений

Когда присутствуют несколько равенств h₁(u), h₂(u),…,hₖ(u) вместе с несколькими неравенствами g₁(u), g₂(u),…,gₚ(u), метод гладко обобщается путем записи полного функционала Лагранжа и проверки условий KKT только для неравенств и их множителей (которых будем называть α):

0. Запишите функционал Лагранжа

1. Установите ∇ᵤL(u,λ₁,λ₂,…,λₖ, α₁, α₂, …, αₚ) = 0 (n уравнений)

2. Установите h₁(u)=0, h₂(u)=0, …, hₖ(u)=0 (k уравнений) и установите g₁(u)≤0, g₂(u)≤0, …, gₚ(u)≤0 (p неравенств)

3. Установите α₁≥0, α₂≥0, …, αₚ≥0 (p неравенств)

4. Установите α₁g₁(u) = α₂g₂(u) = αₚgₖ(u) = 0 (p уравнений)

Всего у вас есть n+k+p уравнений и 2p неравенств, которые вы решите вместе, чтобы найти n+k+p переменных (u*₁,u*₂,…,u*ₙ,λ₁,λ₂,…,λₖ,α₁, α₂, …, αₚ ), что приведет к решению u*=(u*₁,u*₂,…,u*ₙ), минимизирующему функцию и удовлетворяющему k+p ограничениям.

Принцип дуальности

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

Для любой задачи оптимизации вида:

Задача двойственной оптимизации имеет следующую форму:

и наоборот, если задача на максимум.

Пример

Например, задача ограниченной оптимизации, о которой мы ранее говорили:

Имеет соответствующую двойственную задачу:

Как подсказывает базовый исчислительный метод, чтобы продолжить минимизацию, мы делаем

что подразумевает

и тем самым задача оптимизации становится

и все, что остается, это дифференцировать это и приравнять к нулю, чтобы получить λ = 1/√2, что означает, что (x*, y*) = (−1/√2, −1/√2), что является той же самой решением, которое мы получили, решая первоначальную проблему с помощью KKT.

Поиск двойника

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

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

В этом случае первоначальная проблема эквивалентна

Это должно иметь смысл, потому что f(u)+P(u) устанавливает всё, что находится вне допустимой области, равным бесконечности, и оставляет допустимую область без изменений. Минимум этой суммы должен находиться в допустимой области, даже если ограничение принудительно выполняется, потому что бесконечность превышает все значения.

Обратите внимание, что мы можем утверждать, что:

Потому что с этим, если:

• g(u)<0 то P(u)=0, как определено ранее, так как λ=0 должно выполняться, чтобы максимизировать количество λg(u) (в противном случае оно отрицательное из-за g(u)<0)
• g(u)=0 то P(u)=0, как определено ранее, так как λg(u) будет равно нулю (λ может быть любым)
• g(u)>0 то P(u)=∞, как определено ранее, так как λ=∞ то, что максимизировало бы λg(u)

Таким образом, первоначальная проблема эквивалентна

Разница между этим и двойной задачей заключается в том, что в двойной задаче Max и Min меняются местами.

Таким образом, поскольку вообще MinMax(…) ≥ MaxMin(…), решение двойной является нижней границей для решения первоначальной проблемы. Это называется слабой двойственностью.

Более интересный случай – это когда MinMax(…) = MaxMin(…), где решение двойной также будет решением первоначальной проблемы (как в примере). Это называется сильной двойственностью. Вы можете довольно легко доказать, что равенство выполняется (и следовательно, есть сильная двойственность), когда ККТ является одновременно необходимым и достаточным. Другими словами, сильная двойственность будет существовать для выпуклых проблем, когда выполняется условие Слейтера!

Итак, что же?

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

Несколько ограничений?

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

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