KKT w pigułce graficznie

Cel

Potwierdź, czy rozumienie KKT jest prawidłowe, czy nie. Szukaj dalszych wyjaśnień i potwierdzeń w KKT.

tło

Próbowanie zrozumienia warunków KKT, szczególnie tych uzupełniających, które zawsze pojawiają się niespodziewanie w artykułach SVM. Nie potrzebuję listy abstrakcyjnych wzorów, ale potrzebuję konkretnego, intuicyjnego i graficznego wyjaśnienia.

Pytanie

Jeśli P, który minimalizuje funkcję kosztu f (X), znajduje się wewnątrz ograniczenia (g (P)> = 0), jest to rozwiązanie. Wygląda na to, że KKT nie ma znaczenia w tym przypadku.

Wygląda na to, że KKT mówi, że jeśli P nie znajduje się w wiązaniu, wówczas rozwiązanie X powinno spełniać poniższe zdjęcie. Czy chodzi o KKT, czy brakuje mi innych ważnych aspektów?

Inne wyjaśnienia

Czy f (x) powinno być wypukłe, aby zastosować KKT?
Czy g (x) powinno być liniowe, aby zastosować KKT?
Czy λ powinno być konieczne w λ * g (X) = 0? Dlaczego g (X) = 0 lub g (Xi) = 0 to za mało?

Bibliografia

Aktualizacja 1

Dziękuję za odpowiedzi, ale wciąż nie mogę zrozumieć. Skoncentruj się na konieczności tylko tutaj:

Czy warunek (2) w odpowiedzi Matthew Gunna na temat nieoptymalnego punktu (w zielonym kółku) i KKT nie będzie tam spełniony? A kwestię tę można zidentyfikować, patrząc na Hesjan jako na odpowiedź Marka L. Stone'a?

Przypuszczam, że inną sytuacją są punkty siodłowe, ale to samo dotyczy?

użytkownik23658

svm optimization lagrange-multipliers pon
źródło

To pytanie może zwrócić większą uwagę na stronie matematyki; Warunki KKT niekoniecznie są „statystyczne”. Statystycy pożyczają te i inne wyniki analizy numerycznej w celu rozwiązania interesujących problemów statystycznych, ale jest to raczej pytanie matematyczne.

user23658

(1) Jeśli ograniczenia nie wiążą się, problem optymalizacji z ograniczeniami ma takie samo rozwiązanie jak problem optymalizacji bez ograniczeń. (2) Ani nie musi być wypukły, ani nie musi być liniowy, aby warunki KKT były optymalnie konieczne. (3) Potrzebujesz specjalnych warunków (np. Problem wypukły, gdy utrzymuje się Slater), aby warunki KKT były wystarczające do uzyskania optymalnego.

f

$f$

g

$g$

Matthew Gunn

Podstawową ideą uzupełniającego warunku luzu (tj. gdzie jest ograniczeniem) jest to, że jeśli ograniczenie jest luźne (tj. ) przy optymalnym , wówczas kara za zaostrzenie ograniczenia wynosi 0. A jeśli istnieje dodatnia kara za zaostrzenie ograniczenia, wówczas ograniczenie musi być wiążące (tj. ). Jeśli ruch odbywa się płynnie, opłata za przejazd mostem dla innego samochodu wynosi zero. A jeśli opłata za przejazd mostem , wówczas most musi znajdować się na granicy pojemności.

λ g (x) = 0

$\lambda g(\mathbf{x}) = 0$

g (x) \leq 0

$g(\mathbf{x}) \leq 0$

g (x) < 0

$g(\mathbf{x}) < 0$

x

$\mathbf{x}$

λ

$\lambda$

λ

$\lambda$

g (x) = 0

$g(\mathbf{x}) = 0$

λ

$\lambda$

λ > 0

$\lambda > 0$

Matthew Gunn

Podstawowe twierdzenie KKT mówi, że jeśli warunki KKT nie są spełnione w punkcie , to punkt nie jest optymalny. Warunki KKT są niezbędne dla optymalnego, ale niewystarczającego. (Na przykład, jeśli funkcja ma punkty siodłowe, lokalne minima itp. ... warunki KKT mogą być spełnione, ale punkt nie jest optymalny!) W przypadku niektórych klas problemów (np. Problem wypukły, w którym występuje stan Slatera), KKT warunki stają się wystarczającymi warunkami.

x

$\mathbf{x}$

x

$\mathbf{x}$

Matthew Gunn

Odpowiedzi:

$\mathbf{x}$ $\boldsymbol{\delta}$ $f$ $\mathbf{x}$ $\mathbf{x}$

Wyobraź sobie, że masz problem z optymalizacją:

\begin{array}{llr} minimize (over x) & f (x) \\ subject to & \forall_{j \in {1 \dots k}} g_{j} (x) \leq 0 \end{array}

$\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{x}$)} & f(\mathbf{x}) \\ \mbox{subject to} & \forall_{j \in \{1\ldots k\}}\; g_j(\mathbf{x}) \leq 0 \end{array} \end{equation}$

Gdzie i istnieje ograniczeń. $\mathbf{x} \in \mathbb{R}^n$ $k$

Warunki KKT i Farkas Lemma

Niech będzie wektorem kolumnowym oznaczającym gradient obliczony w . $\nabla f(\mathbf{x})$ $f$ $\mathbf{x}$

W tej sytuacji Farkas Lemma stwierdza, że dla dowolnego punktu dokładnie jedna z następujących instrukcji: $\mathbf{x} \in \mathbb{R}^n$

Istnieje taki, że i $\boldsymbol{\lambda} \in \mathbb{R}^k$ $\sum_{j=1}^k \lambda_j \nabla g_j(\mathbf{x}) = -\nabla f(\mathbf{x})$ $\boldsymbol{\lambda} \geq \mathbf{0}$
Istnieje taki, że i $\boldsymbol{\delta} \in \mathbb{R}^n$ $\forall_j \boldsymbol{\delta}' g_j(\mathbf{x}) \leq 0$ $\boldsymbol{\delta}'\nabla f(\mathbf{x}) < 0$

Co to znaczy? Oznacza to, że dla każdego możliwego punktu : $\mathbf{x}$

Warunek (1) zostaje zachowany, a warunki KKT są spełnione.
Warunek (2) obowiązuje i istnieje możliwy kierunek który poprawia funkcję celu bez zwiększania ograniczeń . (np. możesz poprawić , przechodząc z do ) $\boldsymbol{\delta}$ $f$ $g_j$ $f$ $\mathbf{x}$ $\mathbf{x} + \epsilon \boldsymbol{\delta}$

Warunek (1) stwierdza, że istnieją nieujemne mnożniki dzięki czemu warunki KKT są spełnione w punkcie . (Geometrycznie mówi się, że leży w wypukłym stożku określonym przez gradienty wiązań). $\boldsymbol{\lambda}$ $\mathbf{x}$ $- \nabla f$

Warunek (2) stwierdza, że w punkcie istnieje kierunek aby przenieść (lokalnie), tak aby: $\mathbf{x}$ $\boldsymbol{\delta}$

Poruszanie się w kierunku zmniejsza funkcję celu (ponieważ iloczyn iloczynu i jest mniejszy od zera). $\boldsymbol{\delta}$ $\nabla f(\mathbf{x})$ $\boldsymbol{\delta}$
Poruszanie się w kierunku nie zwiększa wartości ograniczeń (ponieważ iloczyn iloczynu i jest mniejszy lub równy zero dla wszystkich ograniczenia ). $\boldsymbol{\delta}$ $\nabla g_j(\mathbf{x})$ $\boldsymbol{\delta}$ $j$

(Geometrycznie możliwy kierunek definiuje oddzielającą hiperpłaszczyznę między wektorem a wypukłym stożkiem zdefiniowanym przez wektory .) $\boldsymbol{\delta}$ $-\nabla f(\mathbf{x})$ $\nabla g_j(\mathbf{x})$

(Uwaga: aby zamapować to na Farkas Lemma , zdefiniuj macierz ) $A = \begin{bmatrix} \nabla g_1, \nabla g_2, \ldots, \nabla g_k \end{bmatrix}$

Ten argument wskazuje na konieczność (ale nie wystarczalność) warunków KKT w optymalny sposób. Jeśli warunki KKT nie są spełnione (i spełnione są kwalifikacje ograniczeń), możliwe jest ulepszenie celu bez naruszania ograniczeń.

Rola kwalifikacji ograniczających

Co może pójść źle? Możesz uzyskać zdegenerowane sytuacje, w których gradienty wiązań nie opisują dokładnie możliwych kierunków ruchu.

Istnieje wiele różnych kwalifikacji ograniczeń do wyboru, które pozwolą na działanie powyższego argumentu.

Minimalna, maksymalna interpretacja (imho najbardziej intuicyjna)

Utwórz Lagrangian

L (x, λ) = f (x) + \sum_{j = 1}^{k} λ_{j} g_{j} (x)

$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^k \lambda_jg_j(\mathbf{x})$

Zamiast minimalizować podlegające ograniczeniom , wyobraź sobie, że próbujesz zminimalizować podczas gdy jakiś przeciwnik próbuje go zmaksymalizować. Mnożniki można interpretować jako kary (wybrane przez niektórych przeciwników) za naruszenie ograniczeń. $f$ $g_j$ $\mathcal{L}$ $\lambda_i$

Rozwiązanie pierwotnego problemu optymalizacji odpowiada:

min_{x} max_{λ} L (x, λ)

$\min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

To jest:

Najpierw wybierasz aby zminimalizować Lagrangian , wiedząc, że ... $\mathbf{x}$ $\mathcal{L}$
Następnie aby zmaksymalizować Lagrangian (obserwując twój pick ). $\boldsymbol{\lambda}$ $\mathbf{x}$

Na przykład, jeśli naruszysz ograniczenie , mogę cię ukarać, ustawiając na nieskończoność! $g_2$ $\lambda_2$

Słaba dualność

W przypadku dowolnej funkcji zauważ, że: $f(x, y)$

\forall_{\hat{x}, \hat{y}} min_{x} f (x, \hat{y}) \leq f (\hat{x}, \hat{y}) \leq max_{y} f (\hat{x}, y)

$\forall_{\hat{x},\hat{y}} \quad \min_x f(x, \hat{y}) \leq f(\hat{x}, \hat{y}) \leq \max_y f(\hat{x}, y)$

Ponieważ odnosi się to do każdego i to również, że: $\hat{x}$ $\hat{y}$

max_{y} min_{x} f (x, y) \leq min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) \leq \min_x \max_y f(x, y)$

W ustawieniach Langriana ten wynik jest taki, że jest znany jako słaba dualność. $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) \leq \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Podwójny problem daje ci dolną granicę rozwiązania $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Silna dualność

W pewnych szczególnych warunkach (np. Problem wypukły, gdy utrzymuje się stan Slatera), masz silną dualność (tj. Właściwość punktu siodłowego).

max_{λ} min_{x} L (x, λ) = min_{x} max_{λ} L (x, λ)

$\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Ten piękny wynik oznacza, że możesz odwrócić kolejność problemu.

Najpierw wybieram kary aby zmaksymalizować Lagrangian. $\boldsymbol{\lambda}$
Następnie wybierz aby zminimalizować Lagrangian . $\mathbf{x}$ $\mathcal{L}$

zestaw w tym procesie są cenami za naruszenie ograniczeń, a ceny są ustawione tak, że nigdy nie będzie naruszać ograniczeń. $\lambda$

Matthew Gunn
źródło

Doceń informacje i linki, aby wypełnić luki w zrozumieniu. Pozwól mi potwierdzić. Warunek (1) oznacza, że KKT mówi, że punkt X jest rozwiązaniem, musi spełniać λ * g (X) = 0, λ> = 0, a długość gradientu g (X) wynosi λ razy że f (X), w przeciwnym razie znajdziemy gradient punktu f (X), w którym można znaleźć mniejsze f (X ')?

pon.

Slater warunek jest (tylko) kwalifikacją ograniczenia, którą można zastosować do wypukłych problemów optymalizacyjnych, tzn. Czyni koniecznym KKT. Wypukłość sprawia, że KKT jest wystarczający. Tak więc spowolnienie warunku dla problemu optymalizacji wypukłej, w którym funkcja celu i ograniczenia są wypukłe i ciągle różnicowalne, sprawia, że KKT jest konieczne i wystarczające dla globalnego minimum. Późniejszy warunek polega na tym, że istnieje co najmniej jeden możliwy do wykonania punkt (tj. Spełnienie wszystkich ograniczeń), który znajduje się w ścisłym wnętrzu wszystkich ograniczeń nieliniowych (wszystko idzie z ograniczeniami liniowymi, o ile jest to wykonalne).

Mark L. Stone

f (x) wypukłość jest konieczna, aby KKT było wystarczające, aby x był lokalnym minimum. Jeśli f (x) lub -g (x) nie są wypukłe, x spełniające KKT może być albo lokalnym minimum, punktem pośrednim, albo lokalnym maksimum.

g (x) jest liniowy, a f (x) jest ciągle różnicowalny, wystarczy, aby warunki KKT były konieczne dla lokalnego minimum. g (x) jest liniowy, oznacza to, że spełniono kwalifikację ograniczenia liniowości, aby KKT był niezbędny dla lokalnego minimum. Istnieją jednak inne mniej restrykcyjne kwalifikacje ograniczeń, które są wystarczające, aby warunki KKT były konieczne dla lokalnego minimum. Zobacz sekcję Warunki regularności (lub kwalifikacje ograniczeń) w https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .

Jeśli lokalne minimum nie ma żadnych „aktywnych” ograniczeń (więc w przypadku tylko ograniczenia nierówności, ograniczenie to nie jest spełnione z równością), mnożniki Lagrange'a związane z takimi ograniczeniami muszą wynosić zero, w takim przypadku KKT sprowadza się do warunku, że gradient celu = 0. W takim przypadku zerowy „koszt” optymalnej wartości obiektywnej zaostrzenia ograniczenia epsilon.

Więcej informacji :

Funkcja celu i ograniczenia są wypukłe, a ciągłe różnicowanie oznacza, że KKT jest wystarczające dla globalnego minimum.

Jeśli funkcja celu i ograniczenia są ciągle rozróżnialne, a ograniczenia spełniają kryteria kwalifikacji, KKT jest konieczne dla lokalnego minimum.

Jeśli funkcja celu i ograniczenia są ciągle różnicowalne, wypukłe, a ograniczenia spełniają kryteria kwalifikacji, KKT jest konieczne i wystarczające dla globalnego minimum.

Powyższa dyskusja w rzeczywistości dotyczy tylko warunków KKT 1. rzędu. Istnieją również warunki KKT drugiego rzędu, które można określić jako: Punkt spełniający warunki KKT 1 rzędu i dla którego funkcja celu i ograniczenia są dwa razy ciągle różnicowalne, jest (wystarcza) dla lokalnego minimum, jeżeli Hesjan z Lagrangian rzutuje na zerowa przestrzeń jakobianów aktywnych wiązań jest dodatnia półfinałowa. (Pozwolę ci spojrzeć na terminologię użytą w poprzednim zdaniu.) Pozwalając, aby była podstawą zerowej przestrzeni jakobianów aktywnych wiązań, warunkiem KKT drugiego rzędu jest to, że jest dodatnie , gdzie $Z$ $Z^T H Z$ $H$ jest Hesjanem z Lagrangian. Aktywne ograniczenia obejmują wszystkie ograniczenia równości oraz wszystkie ograniczenia nierówności, które są spełnione z równością w rozpatrywanym punkcie. Jeśli żadne ograniczenia nie są aktywne w rozważanym punkcie KKT 1. rzędu, macierz tożsamości jest podstawą zerową , a wszystkie mnożniki Lagrange'a muszą wynosić zero, dlatego warunek konieczny drugiego rzędu dla lokalnego minimum zmniejsza się do znanego warunku z nieograniczonej optymalizacji że Hesjan funkcji celu jest dodatni półokreślony. Jeśli wszystkie ograniczenia są liniowe, Hesjan z Lagrangian = Hesjan funkcji celu, ponieważ druga pochodna funkcji liniowej = 0. $Z$

Mark L. Stone
źródło