Karush-Kuhn-Tucker Conditions

hj(x)=0(j=1,…,m),gi(x)≤0(i=1,…,ℓ),∇f(x)+∑j=1mλj∇hj(x)+∑i=1ℓμi∇gi(x)=0,μigi(x)=0(i=1,…,ℓ),μi≥0(i=1,…,ℓ)\begin{aligned} h_{j}(x) &=0 &(j&=1, \ldots, m), \\ g_{i}(x) & \leq 0 & &(i=1, \ldots, \ell), \\ \nabla f(x)+\sum_{j=1}^{m} \lambda_{j} \nabla h_{j}(x)+\sum_{i=1}^{\ell} \mu_{i} \nabla g_{i}(x) &=0, & & \\ \mu_{i} g_{i}(x) &=0 & &(i=1, \ldots, \ell), \\ \mu_{i} & \geq 0 & &(i=1, \ldots, \ell) \end{aligned}

Die ersten beiden Bedingungen geben an, dass xx zulässig ist.

Die dritte Bedingung sagt aus, dass sich der Gradient von ff als Linearkombination der Gradienten der Nebenbedingungen hjh_j und als konische Kombination (konische Hülle) der Nebenbedingungen gig_i schreiben lässt.

Hier ein Beispiel für die dritte Bedingung. Der negative Gradient liegt im Kegel (konische Hülle) der Nebenbedingungen, somit ist die dritte Bedingung mit bestimmten μi\mu_i erfüllt.

Bildschirmfoto 2022-07-13 um 09.03.35.png

Die vierte Bedingung heißt Komplementaritätsbedingung.

λ\lambda und μ\mu sind Lagrange-Multiplikatoren.

Keine Restriktionen → Notwendige Optimalitätsbedingung erster Ordnung unrestringierter Probleme

Da die λj\lambda_j kein Vorzeichen haben kann man für die Linearkombination auch schreiben:

∑j=1mλj∇hj(x)=−∑j=1mλj∇hj(x)\sum_{j=1}^{m} \lambda_{j} \nabla h_{j}(x) = -\sum_{j=1}^{m} \lambda_{j} \nabla h_{j}(x)

Mit der Lagrange-Funktion lässt sich die dritte Bedinung auch als

∇xL(x,λ,μ)=0\nabla_{x} \mathcal{L}(x, \lambda, \mu)=0

schreiben.

Wenn alle Funktionen zweimal stetig differenzierbar sind lässt sich die Hessematrix bestimmen als:

∇xx2L(x,λ,μ)=∇2f(x)+∑j=1mλj∇2hj(x)+∑i=1lμi∇2gi(x)\nabla_{x x}^{2} \mathcal{L}(x, \lambda, \mu)=\nabla^{2} f(x)+\sum_{j=1}^{m} \lambda_{j} \nabla^{2} h_{j}(x)+\sum_{i=1}^{l} \mu_{i} \nabla^{2} g_{i}(x)

KKT-Punkte bestimmen

  • NLP in die Form bringen mit f,gi,hif,g_i,h_i.
  • Gradienten aller Funktionen bestimmen
  • Alle Fälle der Indexmenge der Aktiven Ungleichungsbedingungen durchgehen und auf Lagrange-Funktion testen
    • Jeweils auf die anderen Bedingungen wie μ>0\mu >0 testen
    • falls alle Bedingungen gelten → xx bestimmen
  • Mit der Information, dass Ungleichung aktiv ist und dem xx kann yy berechnet werden
  • Punkt auf Zulässigkeit testen (andere Bedingungen)
  • LICQ überprüfen
  • Für zwei aktive Ungleichungen können diese kombiniert werden um ein xx und yy zu berechnen. → Andere Bedinungen testen

ML4ENG

apply for the given problem:

αi≥0yi(w⋅x−b)−1≤0αi[yi(w⋅x−b)−1]=0\begin{equation} \begin{gathered} \alpha_{i} \geq 0 \\ y_{i}(w \cdot x-b)-1 \leq 0 \\ \alpha_{i}\left[y_{i}(w \cdot x-b)-1\right]=0 \end{gathered} \end{equation}

Based on the last condition αi=0\alpha _i = 0 or yi(w⋅x−b)=1y_i(w \cdot x -b) = 1 for each training point.

When αi\alpha _i is not zero, we call the training point a support vector since it is right on the margin.

We can now use our previously derived function to calculate ww with our newly gained αi\alpha _i:

Depending on the sign of our result, the datapoint is either in class +1 or -1:

y=sgn⁡(w⋅x−b)=sgn⁡(∑i=1nαi∗yixi⋅x)\begin{equation} y=\operatorname{sgn}(\boldsymbol{w} \cdot \boldsymbol{x}-b)=\operatorname{sgn}\left(\sum_{i=1}^{n} \alpha_{i}^{*} y_{i} \boldsymbol{x}_{i} \cdot \boldsymbol{x}\right) \end{equation}