Задача
Подтвердите правильность понимания KKT или нет. Ищите дальнейшие объяснения и подтверждения на KKT.
Фон
Попытка понять условия KKT, особенно дополнительные, которые всегда всплывают в статьях SVM. Мне не нужен список абстрактных формул, но мне нужно конкретное, интуитивное и графическое объяснение.
Вопрос
Если P, который минимизирует функцию стоимости f (X), находится внутри ограничения (g (P)> = 0), это решение. Кажется, ККТ не имеет отношения к этому делу.
Кажется, KKT говорит, что если P не находится внутри ограничения, то решение X должно удовлетворять ниже на рисунке. Это все о KKT или я пропускаю другие важные аспекты?
Другие уточнения
- Должно ли f (x) быть выпуклым для применения KKT?
- Должен ли g (x) быть линейным для применения KKT?
- Нужно ли λ в λ * g (X) = 0? Почему g (X) = 0 или g (Xi) = 0 недостаточно?
Ссылки
- Условие Лагранжа Множителя ККТ
- Каждый ли желоб в SVM имеет положительный множитель?
- http://fnorio.com/0136Lagrange_method_of_undetermined_multipliers/Lagrange_method_of_undetermined_multipliers.html
Обновление 1
Спасибо за ответы, но все еще трудно понять. Фокус на необходимости только здесь:
Не будет ли выполнено условие (2) в ответе Мэтью Ганна о неоптимальной точке (в зеленом круге) и KKT? И точка будет определена, если взглянуть на Гессиана как на ответ Марка Л. Стоуна?
Я полагаю, что другая ситуация седловых точек, но то же самое относится?
источник
Ответы:
Основная идея условий KKT как необходимых условий для оптимума заключается в том, что если они не выполняются в допустимой точке , то существует направление δ , которое улучшит цель f, не увеличивая (и, следовательно, возможно, нарушая) ограничения. (Если условия KKT не выполняются при x, то x не может быть оптимальным, поэтому условия KKT необходимы для того, чтобы точка была оптимальной.)x δ f x x
Представьте, что у вас есть проблема оптимизации:
Там , где и существует K ограничений.x∈Rn k
Условия KKT и лемма Фаркаша
Пусть - вектор-столбец, обозначающий градиент f, оцененный в точке x .∇f(x) f x
Применительно к данной ситуации, Фаркаш лемма утверждает , что для любой точки ровно одна из следующих утверждений:x∈Rn
Что это значит? Это означает, что для любой возможной точки , либо:x
Условие (1) утверждает, что существуют неотрицательные множители такие что условия KKT выполняются в точке x . (Геометрически это говорит о том, что - ∇ f лежит в выпуклом конусе, определяемом градиентами ограничений.)λ x −∇f
Условие (2) гласит, что в точке существует направление δ для перемещения (локально), такое что:x δ
(Геометрически, допустимое направлениеδ определяет разделяющую гиперплоскость между вектором и выпуклым конусом, определяемым векторами ∇ g j ( x ) .)−∇f(x) ∇gj(x)
(Примечание: чтобы отобразить это в лемму Фаркаша , определите матрицу )A=[∇g1,∇g2,…,∇gk]
Этот аргумент дает вам необходимость (но не достаточность) условий KKT в оптимальном режиме. Если условия KKT не выполнены (и удовлетворены ограничения), можно улучшить цель, не нарушая ограничений.
Роль ограничений квалификации
Что может пойти не так? Вы можете получить вырожденные ситуации, когда градиенты ограничений не точно описывают возможные направления движения.
Существует множество различных квалификационных ограничений , которые позволят использовать приведенный выше аргумент.
Мин, Макс интерпретация (IMHO наиболее интуитивно понятный)
Форма лагранжиана
Вместо минимизации учетом ограничений g j , представьте, что вы пытаетесь минимизировать L, в то время как какой-то противник пытается максимизировать его. Вы можете интерпретировать множители λ i как штрафы (выбранные некоторым оппонентом) за нарушение ограничений.f gj L λi
Решение исходной задачи оптимизации эквивалентно:
То есть:
Слабая двойственность
Сильная двойственность
При определенных особых условиях (например, выпуклая задача, где выполняется условие Слейтера), вы имеете сильную двойственность (то есть свойство седловой точки).
Этот прекрасный результат подразумевает, что вы можете изменить порядок задач.
источник
Выпуклость f (x) необходима для того, чтобы KKT было достаточным для того, чтобы x был локальным минимумом. Если f (x) или -g (x) не являются выпуклыми, то x, удовлетворяющий KKT, может быть локальным минимумом, седловой точкой или локальным максимумом.
При этом линейность g (x) вместе с непрерывно дифференцируемой функцией f (x) достаточна для того, чтобы условия KKT были необходимы для локального минимума. g (x) линейность означает, что условие ограничения линейности для KKT, являющегося обязательным для локального минимума, выполнено. Тем не менее, существуют другие менее ограничивающие ограничения, которые достаточны для того, чтобы условия KKT были необходимы для локального минимума. См. Раздел «Условия регулярности» (или квалификации ограничений) https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .
Если локальный минимум не имеет «активных» ограничений (поэтому в случае только ограничения неравенства это ограничение не удовлетворяется равенством), множители Лагранжа, связанные с такими ограничениями, должны быть равны нулю, и в этом случае KKT сводится к условию, что градиент объектива = 0. В этом случае нулевая «стоимость» равна оптимальному значению объективной эпсилон-точки ужесточения ограничения.
Дополнительная информация :
Целевая функция и ограничения являются выпуклыми и непрерывно дифференцируемыми, что означает, что KKT достаточно для глобального минимума.
Если целевая функция и ограничения непрерывно дифференцируемы и ограничения удовлетворяют квалификации ограничения, KKT необходим для локального минимума.
Если целевая функция и ограничения непрерывно дифференцируемы, выпуклы и ограничения удовлетворяют квалификации ограничения, KKT необходим и достаточен для глобального минимума.
источник