Objectif

Confirmez si la compréhension de KKT est correcte ou non. Cherchez plus d'explications et de confirmations sur KKT.

Contexte

Essayer de comprendre les conditions KKT, en particulier la condition complémentaire, qui apparaît toujours à l'improviste dans les articles SVM. Je n'ai pas besoin d'une liste de formules abstraites mais j'ai besoin d'une explication concrète, intuitive et graphique.

Question

Si P, qui minimise la fonction de coût f (X), est à l'intérieur de la contrainte (g (P)> = 0), c'est la solution. Il semble que KKT ne soit pas pertinent dans ce cas.

Il semble que KKT indique que si P n'est pas à l'intérieur de la contrainte, alors la solution X devrait satisfaire ci-dessous dans l'image. S'agit-il de KKT ou est-ce que je manque d'autres aspects importants?

Autres clarifications

1. F (x) doit-il être convexe pour que KKT s'applique?
2. G (x) doit-il être linéaire pour que KKT s'applique?
3. Faut-il que λ soit nécessaire dans λ * g (X) = 0? Pourquoi g (X) = 0 ou g (Xi) = 0 ne suffit pas?

Les références

• Lagrange Multipler KKT condition
• Est-ce que chaque point de gouttière dans SVM a un multiplicateur positif?
• http://fnorio.com/0136Lagrange_method_of_undknown_multipliers/Lagrange_method_of_undeterm_multipliers.html

---

Mise à jour 1

Merci pour les réponses mais j'ai encore du mal à comprendre. Concentrez-vous sur la nécessité uniquement ici:

La condition (2) dans la réponse de Matthew Gunn sur le point non optimal (dans le cercle vert) et KKT ne sera-t-elle pas satisfaite là-bas? Et le point serait identifié en regardant Hessian comme dans la réponse de Mark L. Stone?

Je suppose qu'une autre situation concerne les points de selle, mais la même chose s'applique?

user23658

L'idée de base des conditions KKT en tant que conditions nécessaires pour un optimum est que si elles ne tiennent pas à un point faisable , alors il existe une direction δ qui améliorera l'objectif f sans augmenter (et donc éventuellement violer) les contraintes. (Si les conditions KKT ne tiennent pas à x, alors x ne peut pas être un optimum, donc les conditions KKT sont nécessaires pour qu'un point soit optimal.)$\mathbf{x}$$\boldsymbol{\delta}$$f$$\mathbf{x}$$\mathbf{x}$

Imaginez que vous ayez le problème d'optimisation:

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

Où et $\mathbf{x} \in \mathbb{R}^n$$k$ contraintes.

Conditions KKT et lemme de Farkas

Laisser un vecteur colonne indiquant le gradient de f évalué à$\nabla f(\mathbf{x})$$f$$\mathbf{x}$ .

Appliqué à cette situation, le lemme de Farkas déclare que pour tout point exactement un$\mathbf{x} \in \mathbb{R}^n$ des affirmations suivantes est vraie:

1. Il existe tel que ∑ k j = 1 λ j ∇ g j ( x ) = - ∇ f ( x ) et λ ≥ $\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}$
2. Il existe tel que ∀ j δ ′ g j ( x ) ≤ 0 et δ ′ ∇ f ( x ) < $\boldsymbol{\delta} \in \mathbb{R}^n$$\forall_j \boldsymbol{\delta}' g_j(\mathbf{x}) \leq 0$$\boldsymbol{\delta}'\nabla f(\mathbf{x}) < 0$

Qu'est-ce que ça veut dire? Cela signifie que pour tout point réalisable , soit:$\mathbf{x}$

• La condition (1) est vérifiée et les conditions KKT sont remplies.
• La condition (2) est vérifiée et il existe une direction réalisable qui améliore la fonction objectif f sans augmenter les contraintes g j . (par exemple, vous pouvez améliorer f en passant de x à x + ϵ δ )$\boldsymbol{\delta}$$f$$g_j$$f$$\mathbf{x}$$\mathbf{x} + \epsilon \boldsymbol{\delta}$

La condition (1) indique qu'il existe des multiplicateurs non négatifs tels que les conditions KKT sont satisfaites au point x . (Géométriquement, on dit que le - ∇ f se situe dans le cône convexe défini par les gradients des contraintes.)$\boldsymbol{\lambda}$$\mathbf{x}$$- \nabla f$

La condition (2) indique qu'au point , il existe une direction δ pour se déplacer (localement) telle que:$\mathbf{x}$$\boldsymbol{\delta}$

• Le déplacement dans la direction réduit la fonction objectif (car le produit scalaire de ∇ f ( x ) et $\boldsymbol{\delta}$$\nabla f(\mathbf{x})$$\boldsymbol{\delta}$ est inférieur à zéro).
• Le déplacement dans la direction n'augmente pas la valeur des contraintes (car le produit scalaire de ∇ g j ( $\boldsymbol{\delta}$ et δ est inférieur ou égal à zéro pour toutes les contraintes j ).$\nabla g_j(\mathbf{x})$$\boldsymbol{\delta}$$j$

(Géométriquement, la direction réalisable définit un hyperplan de séparation entre le vecteur - ∇ f ( x$\boldsymbol{\delta}$$-\nabla f(\mathbf{x})$ et le cône convexe défini par les vecteurs $\nabla g_j(\mathbf{x})$ .)

(Remarque: pour cartographier cela dans le lemme de Farkas , définir la matrice )$A = \begin{bmatrix} \nabla g_1, \nabla g_2, \ldots, \nabla g_k \end{bmatrix}$

Cet argument vous donne la nécessité (mais pas la suffisance) des conditions KKT à un optimum. Si les conditions KKT ne sont pas remplies (et que les qualifications de contrainte sont satisfaites), il est possible d'améliorer l'objectif sans violer les contraintes.

Le rôle des qualifications de contraintes

Qu'est-ce qui peut mal tourner? Vous pouvez obtenir des situations dégénérées où les gradients des contraintes ne décrivent pas avec précision les directions possibles pour se déplacer.

Il existe une multitude de qualifications de contraintes différentes à choisir qui permettront à l'argument ci-dessus de fonctionner.

L'interprétation min, max (à mon humble avis la plus intuitive)

Former le lagrangien

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

Au lieu de minimiser soumis aux contraintes g j , imaginez que vous essayez de minimiser L pendant qu'un adversaire essaie de le maximiser. Vous pouvez interpréter les multiplicateurs λ i comme des pénalités (choisies par certains adversaires) pour avoir violé les contraintes. $f$$g_j$$\mathcal{L}$$\lambda_i$

La solution au problème d'optimisation d'origine équivaut à:

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

C'est:

1. Vous choisissez d'abord pour minimiser le L lagrangien , sachant que ...$\mathbf{x}$$\mathcal{L}$
2. Je vais ensuite choisir pour maximiser le lagrangien (après avoir observé votre choix x ).$\boldsymbol{\lambda}$$\mathbf{x}$

Par exemple, si vous violez la contrainte , je peux vous pénaliser en mettant λ $g_2$$\lambda_2$ à l'infini!

Faible dualité

Pour toute fonction observez que:$f(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)$$

$\hat{x}$$\hat{y}$

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

$\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) \leq \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$ is known as weak duality.

The dual problem $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$ gives you a lower bound on the solution

Strong duality

Under certain special conditions (eg. convex problem where Slater condition holds), you have strong duality (i.e. the saddle point property).

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

This beautiful result implies you can reverse the order of the problem.

1. I first pick penalties $\boldsymbol{\lambda}$ to maximize the Lagrangian.

2. You then pick $\mathbf{x}$ to minimize the Lagrangian $\mathcal{L}$.

The $\lambda$ set in this process are prices for violating the constraints, and the prices are set such that you will never violate the constraints.

f(x) being convex is necessary for KKT to be sufficient for x to be local minimum. If f(x) or -g(x) are not convex, x satisfying KKT could be either local minimum, saddlepoint, or local maximum.

g(x) being linear, together with f(x) being continuously differentiable is sufficient for KKT conditions to be necessary for local minimum. g(x) being linear means that the Linearity constraint qualification for KKT to be nessary for local minimum is satisfied. However, there are other less restrictive constraint qualifications which are sufficient for KKT conditions to be necessary for local minimum. See the Regularity conditions (or constraint qualifications) section of https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .

If a local minimum has no "active" constraints (so in the case of only an inequality constraint, that constraint is not satisfied with equality), Lagrange multipliers associated with such constraints must be zero, in which case, KKT reduces to the condition that the gradient of the objective = 0. In such case, there is zero "cost" to the optimal objective value of an epsilon tightening of the constraint.

Further info:

Objective function and constraints are convex and continuously differentiable implies KKT is sufficient for global minimum.

If objective function and constraints are continuously differentiable and constraints satisfy a constraint qualification, KKT is necessary for a local minimum.

If objective function and constraints are continuously differentiable, convex, and constraints satisfy a constraint qualification, KKT is necessary and sufficient for a global minimum.

The above discussion actually pertains only to 1st order KKT conditions. There are also 2nd order KKT conditions, which can be stated as: A point satisfying 1st order KKT conditions and for which objective function and constraints are twice continuously differentiable is (sufficient for) a local minimum if the the Hessian of the Lagrangian projected into the nullspace of the Jacobian of active constraints is positive semidefinite. (I'll let you look up the terminology used in the preceding sentence.) Letting $Z$ be a basis for the nullspace of the Jacobian of active constraints, 2nd order KKT condition is that $Z^T H Z$ is positive semi-definite, where $H$ is the Hessian of the Lagrangian. Active constraints consist of all equality constraints plus all inequality constraints which are satisfied with equality at the point under consideration. If no constraints are active at the 1st order KKT point under consideration, the identity matrix is a nullspace basis $Z$, and all Lagrange multipliers must be zero, therefore, the 2nd order necessary condition for a local minimum reduces to the familiar condition from unconstrained optimization that the Hessian of the objective function is positive semi-definite. If all constraints are linear, the Hessian of the Lagrangian = Hessian of objective function because the 2nd derivative of a linear function = 0.