KKT in aller Kürze grafisch

Zielsetzung

Bestätigen Sie, ob das Verständnis von KKT korrekt ist oder nicht. Weitere Erklärungen und Bestätigungen finden Sie auf KKT.

Hintergrund

Der Versuch, die KKT-Bedingungen zu verstehen, insbesondere die komplementären, die in SVM-Artikeln immer aus heiterem Himmel auftauchen. Ich brauche keine Liste abstrakter Formeln, sondern eine konkrete, intuitive und grafische Erklärung.

Frage

Wenn P, das die Kostenfunktion f (X) minimiert, innerhalb der Beschränkung liegt (g (P)> = 0), ist dies die Lösung. Es scheint, dass KKT in diesem Fall nicht relevant ist.

Es scheint, dass KKT sagt, wenn P nicht innerhalb der Beschränkung ist, dann sollte die Lösung X unten im Bild genügen. Geht es bei KKT nur um oder vermisse ich andere wichtige Aspekte?

Andere Klarstellungen

Sollte f (x) konvex sein, damit KKT angewendet wird?
Sollte g (x) linear sein, damit KKT angewendet wird?
Sollte λ in λ * g (X) = 0 notwendig sein? Warum reicht g (X) = 0 oder g (Xi) = 0 nicht aus?

Verweise

Update 1

Vielen Dank für die Antworten, aber immer noch schwer zu verstehen. Konzentrieren Sie sich nur hier auf die Notwendigkeit:

Ist die Bedingung (2) in Matthew Gunns Antwort über den nicht optimalen Punkt (im grünen Kreis) und KKT dort nicht erfüllt? Und der Punkt würde identifiziert werden, wenn man Hessisch wie in der Antwort von Mark L. Stone ansieht?

Ich nehme an, eine andere Situation sind Sattelpunkte, aber das Gleiche gilt?

user23658

svm optimization lagrange-multipliers mon
quelle

Diese Frage könnte mehr Aufmerksamkeit auf der Mathematikseite erregen. KKT-Bedingungen sind nicht unbedingt "statistisch". Die Statistiker leihen diese und andere Ergebnisse aus der numerischen Analyse aus, um interessante statistische Probleme zu lösen. Dies ist jedoch eher eine mathematische Frage.

user23658

(1) Wenn Bedingungen nicht gebunden sind, hat das Optimierungsproblem mit den Bedingungen die gleiche Lösung wie das Optimierungsproblem ohne die Bedingungen. (2) Weder muss

konvex noch

linear sein, damit die KKT-Bedingungen optimal sind. (3) Sie benötigen spezielle Bedingungen (z. B. ein konvexes Problem, bei dem die Slater-Bedingung gilt), damit die KKT-Bedingungen für ein Optimum ausreichen.

f

$f$

g

$g$

Matthew Gunn

Die Grundidee der komplementären Schlupfbedingung (dh

wobei

eine Bedingung ist) ist, dass dann, wenn die Bedingung schlupf ist (dh

optimal ist die Strafe

für das Verschärfen der Einschränkung ist 0. Und wenn es eine positive Strafe

für das Verschärfen der Einschränkung gibt, muss die Einschränkung verbindlich sein (dh

λ 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$ ). Wenn der Verkehr reibungslos verläuft, ist die Brückengebühr

für ein anderes Auto Null. Und wenn die Brückenzahl

, muss sich die Brücke an der Kapazitätsgrenze befinden.

λ

$\lambda$

λ > 0

$\lambda > 0$

Matthew Gunn

Das grundlegende KKT-Theorem besagt, dass der Punkt

nicht optimal ist , wenn die KKT-Bedingungen an einem Punkt

nicht erfüllt sind . Die KKT-Bedingungen sind für ein Optimum notwendig, aber nicht ausreichend. (Wenn die Funktion beispielsweise Sattelpunkte, lokale Minima usw. hat, sind die KKT-Bedingungen möglicherweise erfüllt, aber der Punkt ist nicht optimal!) Für bestimmte Problemklassen (z. B. konvexes Problem, bei dem die Bedingung von Slater gilt) die KKT Bedingungen werden zu ausreichenden Bedingungen.

x

$\mathbf{x}$

x

$\mathbf{x}$

Matthew Gunn

Antworten:

Die Grundidee der KKT-Bedingungen als notwendige Bedingungen für ein Optimum ist, dass, wenn sie nicht an einem realisierbaren Punkt festhalten , eine Richtung , die das Ziel verbessert, ohne zuzunehmen (und damit möglicherweise Verstöße) gegen die Auflagen. (Wenn die KKT Bedingungen halten nicht an dann können nicht optimal sein, damit KKT Bedingungen notwendig sind , für einen Punkt , ein Optimum zu sein.) $\mathbf{x}$ $\boldsymbol{\delta}$ $f$ $\mathbf{x}$ $\mathbf{x}$

Stellen Sie sich vor, Sie haben das Optimierungsproblem:

\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}$

Wo und es gibt Einschränkungen. $\mathbf{x} \in \mathbb{R}^n$ $k$

KKT-Bedingungen und Farkas Lemma

Sei ein Spaltenvektor, der den Gradienten von , der bei ausgewertet wird . $\nabla f(\mathbf{x})$ $f$ $\mathbf{x}$

Auf diese Situation bezogen gibt Farkas Lemma an , dass für jeden Punkt genau eine der folgenden Aussagen gilt: $\mathbf{x} \in \mathbb{R}^n$

Es gibt so dass und $\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}$
Es gibt so dass und $\boldsymbol{\delta} \in \mathbb{R}^n$ $\forall_j \boldsymbol{\delta}' g_j(\mathbf{x}) \leq 0$ $\boldsymbol{\delta}'\nabla f(\mathbf{x}) < 0$

Was bedeutet das? Dies bedeutet, dass für jeden machbaren Punkt entweder: $\mathbf{x}$

Bedingung (1) gilt und die KKT-Bedingungen sind erfüllt.
Bedingung (2) gilt und es existiert eine mögliche Richtung , die die Zielfunktion verbessert, ohne die Bedingungen . (zB können Sie verbessern, indem Sie von nach ) $\boldsymbol{\delta}$ $f$ $g_j$ $f$ $\mathbf{x}$ $\mathbf{x} + \epsilon \boldsymbol{\delta}$

Bedingung (1) besagt, dass es nicht negative Multiplikatoren so dass die KKT-Bedingungen am Punkt erfüllt sind . (Geometrisch heißt es, dass das im konvexen Kegel liegt, der durch die Steigungen der Nebenbedingungen definiert wird.) $\boldsymbol{\lambda}$ $\mathbf{x}$ $- \nabla f$

Bedingung (2) besagt, dass am Punkt eine Richtung , um sich (lokal) so zu bewegen, dass: $\mathbf{x}$ $\boldsymbol{\delta}$

Das Bewegen in Richtung verringert die Zielfunktion (weil das Skalarprodukt von und kleiner als Null ist). $\boldsymbol{\delta}$ $\nabla f(\mathbf{x})$ $\boldsymbol{\delta}$
Das Bewegen in die Richtung erhöht den Wert der Bedingungen nicht (da das Skalarprodukt von und für alle kleiner oder gleich Null ist Einschränkungen ). $\boldsymbol{\delta}$ $\nabla g_j(\mathbf{x})$ $\boldsymbol{\delta}$ $j$

(Geometrisch definiert die mögliche Richtung eine Trennungshyperebene zwischen dem Vektor und dem durch die Vektoren definierten konvexen Kegel .) $\boldsymbol{\delta}$ $-\nabla f(\mathbf{x})$ $\nabla g_j(\mathbf{x})$

(Hinweis: Um dies auf Farkas Lemma abzubilden , definieren Sie Matrix ) $A = \begin{bmatrix} \nabla g_1, \nabla g_2, \ldots, \nabla g_k \end{bmatrix}$

Dieses Argument gibt Ihnen die Notwendigkeit (aber nicht die Hinlänglichkeit) der KKT-Bedingungen im Optimum. Wenn die KKT-Bedingungen nicht erfüllt sind (und die Einschränkungsqualifikationen erfüllt sind), kann das Ziel verbessert werden, ohne die Einschränkungen zu verletzen.

Die Rolle von Constraint-Qualifikationen

Was kann schon schief gehen? Es kann zu entarteten Situationen kommen, in denen die Steigungen der Abhängigkeiten die möglichen Bewegungsrichtungen nicht genau beschreiben.

Sie können aus einer Vielzahl verschiedener Einschränkungsqualifikationen auswählen, damit das obige Argument funktioniert.

Die minimale, maximale Interpretation (imho die intuitivste)

Bilden Sie den Lagrange

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})$

Stellen Sie sich vor, Sie versuchen zu minimieren, während ein Gegner versucht, es zu maximieren, anstatt unter den Bedingungen zu minimieren . Sie können Multiplikatoren als (von einem Gegner gewählte) Strafen für Verstöße gegen die Beschränkungen interpretieren . $f$ $g_j$ $\mathcal{L}$ $\lambda_i$

Die Lösung für das ursprüngliche Optimierungsproblem ist äquivalent zu:

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

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

Das ist:

Sie wählen zuerst um das Lagrange zu minimieren , da Sie wissen, dass ... $\mathbf{x}$ $\mathcal{L}$
Ich werde dann auswählen , um den Lagrange zu maximieren (nachdem ich Ihren pick ). $\boldsymbol{\lambda}$ $\mathbf{x}$

Wenn Sie beispielsweise die Bedingung verletzen , kann ich Sie bestrafen, indem ich auf unendlich ! $g_2$ $\lambda_2$

Schwache Dualität

Für jede Funktion beachten, dass: $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)$

Da dies für jedes und gilt, gilt auch : $\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)$

In der Langrian-Einstellung führt dies dazu, dass ist als schwache Dualität bekannt. $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) \leq \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Das doppelte Problem gibt Ihnen eine Untergrenze für die Lösung $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Starke Dualität

Unter bestimmten besonderen Bedingungen (z. B. konvexes Problem, wenn die Slater-Bedingung zutrifft) haben Sie eine starke Dualität (dh die Sattelpunkt-Eigenschaft).

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})$

Dieses schöne Ergebnis impliziert, dass Sie die Reihenfolge des Problems umkehren können.

Ich wähle zuerst die Strafen , um die Lagrange zu maximieren. $\boldsymbol{\lambda}$
Dann wählen Sie um den Lagrange zu minimieren . $\mathbf{x}$ $\mathcal{L}$

Die in diesem Prozess festgelegten Werte sind Preise für die Verletzung der Beschränkungen, und die Preise sind so festgelegt, dass Sie niemals gegen die Beschränkungen verstoßen. $\lambda$

Matthew Gunn
quelle

Schätzen Sie die Informationen und Links, um die Lücken des Verständnisses zu schließen. Lassen Sie mich das bestätigen. Bedingung (1) bedeutet, dass KKT sagt, dass ein Punkt X eine Lösung sein soll, dass er λ * g (X) = 0, λ> = 0 erfüllen muss und die Länge des Gradienten von g (X) das λ-fache von beträgt das von f (X), sonst finden wir den Gradienten von f (X) zeigt Richtung, wo kleiner f (X ') gefunden werden kann?

mon

Slater-Bedingung ist (nur) eine Einschränkungsqualifikation, die auf konvexe Optimierungsprobleme angewendet werden kann, dh KKT erforderlich macht. Konvexität macht KKT ausreichend. Eine weitere Bedingung für ein konvexes Optimierungsproblem, bei dem die Zielfunktion und die Randbedingungen konvex und kontinuierlich differenzierbar sind, macht KKT für ein globales Minimum notwendig und ausreichend. Eine spätere Bedingung ist, dass es mindestens einen realisierbaren Punkt gibt (dh, der alle Bedingungen erfüllt), der im strengen Inneren aller nichtlinearen Bedingungen liegt (alles geht mit linearen Bedingungen, so lange es machbar ist).

Mark L. Stone

f (x) ist konvex, damit KKT ausreicht, damit x das lokale Minimum ist. Wenn f (x) oder -g (x) nicht konvex sind, kann x, das KKT erfüllt, entweder ein lokales Minimum, ein Sattelpunkt oder ein lokales Maximum sein.

g (x) ist linear, und f (x) ist kontinuierlich differenzierbar, so dass KKT-Bedingungen für das lokale Minimum erforderlich sind. g (x) ist linear bedeutet, dass die Linearitätsbeschränkungsqualifikation für KKT, die für das lokale Minimum erforderlich ist, erfüllt ist. Es gibt jedoch andere weniger restriktive Einschränkungen, die ausreichen, damit die KKT-Bedingungen für das lokale Minimum erforderlich sind. Weitere Informationen finden Sie im Abschnitt Regelmäßigkeitsbedingungen (oder Einschränkungen) unter https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .

Wenn ein lokales Minimum keine "aktiven" Bedingungen hat (im Falle einer Ungleichheitsbedingung ist diese Bedingung also nicht mit Gleichheit erfüllt), müssen Lagrange-Multiplikatoren, die solchen Bedingungen zugeordnet sind, Null sein. In diesem Fall reduziert sich KKT auf die Bedingung, dass der Gradient des Objektivs = 0. In einem solchen Fall gibt es keine "Kosten" für den optimalen Zielwert einer Verschärfung der Beschränkung durch Epsilon.

Weitere Infos :

Objektive Funktion und Randbedingungen sind konvex und kontinuierlich differenzierbar, was bedeutet, dass KKT für ein globales Minimum ausreicht.

Wenn die objektive Funktion und die Einschränkungen kontinuierlich differenzierbar sind und die Einschränkungen eine Einschränkungsqualifikation erfüllen, ist KKT für ein lokales Minimum erforderlich.

Wenn objektive Funktionen und Bedingungen kontinuierlich differenzierbar, konvex sind und Bedingungen eine Bedingungsqualifikation erfüllen, ist KKT für ein globales Minimum notwendig und ausreichend.

Die obige Diskussion betrifft tatsächlich nur KKT-Bedingungen erster Ordnung. Es gibt auch KKT-Bedingungen 2. Ordnung, die wie folgt angegeben werden können: Ein Punkt, der die KKT-Bedingungen 1. Ordnung erfüllt und für den die objektive Funktion und die Nebenbedingungen zweimal kontinuierlich differenzierbar sind, ist (ausreichend für) ein lokales Minimum, wenn das Hessische des Lagrangen in das Hessische projiziert wird Nullraum des Jacobi der aktiven Nebenbedingungen ist positiv semidefinit. (Ich lasse Sie die im vorhergehenden Satz verwendete Terminologie nachschlagen.) Wenn eine Basis für den Nullraum des Jacobi-Operators für aktive Nebenbedingungen ist, ist die KKT-Bedingung 2. Ordnung, dass positiv ist, wobei $Z$ $Z^T H Z$ $H$ ist der Hessische des Lagrange. Aktive Bedingungen bestehen aus allen Gleichheitsbedingungen sowie allen Ungleichheitsbedingungen, die zum betrachteten Zeitpunkt mit Gleichheit zufrieden sind. Wenn an dem betrachteten KKT-Punkt 1. Ordnung keine Einschränkungen aktiv sind, ist die Identitätsmatrix eine Nullraumbasis , und alle Lagrange-Multiplikatoren müssen Null sein. Daher reduziert sich die notwendige Bedingung 2. Ordnung für ein lokales Minimum auf die bekannte Bedingung aus einer uneingeschränkten Optimierung dass der Hessische der objektiven Funktion positiv semidefinit ist. Wenn alle Bedingungen linear sind, ist das Hessische des Lagrange = Hessisches der objektiven Funktion, da die 2. Ableitung einer linearen Funktion = 0 ist. $Z$

Mark L. Stone
quelle