KKT em poucas palavras graficamente

Objetivo

Confirme se o entendimento da KKT está correto ou não. Procure mais explicações e confirmações na KKT.

fundo

Tentando entender as condições KKT, especialmente a complementar, que sempre aparece do nada nos artigos SVM. Não preciso de uma lista de fórmulas abstratas, mas de uma explicação concreta, intuitiva e gráfica.

Questão

Se P, que minimiza a função de custo f (X), estiver dentro da restrição (g (P)> = 0), é a solução. Parece que a KKT não é relevante neste caso.

Parece que a KKT diz que se P não estiver dentro da restrição, a solução X deve satisfazer abaixo na figura. É o KKT ou sinto falta de outros aspectos importantes?

Outros esclarecimentos

F (x) deve ser convexo para a KKT aplicar?
G (x) deve ser linear para a KKT aplicar?
Λ deve ser necessário em λ * g (X) = 0? Por que g (X) = 0 ou g (Xi) = 0 não é suficiente?

Referências

Atualização 1

Obrigado pelas respostas, mas ainda lutamos para entender. Concentre-se apenas na necessidade aqui:

A condição (2) na resposta de Matthew Gunn sobre o ponto não ótimo (no círculo verde) e o KKT não será satisfeita lá? E o ponto seria identificado olhando Hessian como na resposta de Mark L. Stone?

Suponho que outra situação seja pontos de sela, mas o mesmo se aplica?

user23658

svm optimization lagrange-multipliers seg
fonte

Essa pergunta pode atrair mais atenção no site de matemática; As condições KKT não são necessariamente "estatísticas". Os estatísticos emprestam esses e outros resultados da análise numérica para resolver problemas estatísticos interessantes, mas isso é mais uma questão de matemática.

precisa saber é o seguinte

(1) Se as restrições não se vinculam, o problema de otimização com as restrições tem a mesma solução que o problema de otimização sem as restrições. (2) Nem

precisa ser convexo nem

precisam ser lineares para que as condições KKT sejam necessárias no melhor dos casos. (3) Você precisa de condições especiais (por exemplo, problema convexo onde a condição Slater se mantém) para que as condições KKT sejam consideradas condições suficientes para um ótimo.

f

$f$

g

$g$

Matthew Gunn

A idéia básica da condição de folga complementar (ou seja,

que

é uma restrição) é que, se a restrição for folga (ou seja,

) no

ideal , então a penalidade

para apertar a restrição é 0. E se houver uma penalidade positiva

para apertar a restrição, a restrição deve ser vinculativa (ou seja,

λ 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$ ) Se o tráfego estiver fluindo sem problemas, o pedágio da ponte

para outro carro é zero. E se o pedágio da ponte

, a ponte deve estar no limite de capacidade.

λ

$\lambda$

λ > 0

$\lambda > 0$

Matthew Gunn

O teorema básico da KKT diz que, se as condições da KKT não forem satisfeitas no ponto

, o ponto

não será o ideal. As condições KKT são necessárias para um ótimo, mas não suficiente. (Por exemplo, se a função tiver pontos de sela, mínimos locais etc ... as condições KKT podem ser satisfeitas, mas o ponto não é o ideal!) Para certas classes de problemas (por exemplo, problema convexo onde a condição de Slater se mantém), o KKT condições se tornam condições suficientes .

x

$\mathbf{x}$

x

$\mathbf{x}$

Matthew Gunn

Respostas:

A idéia básica das condições KKT como condições necessárias para um ótimo é que, se elas não se mantiverem em um ponto viável , existe uma direção que melhorará o objetivo sem aumentar (e, portanto, possivelmente violar) as restrições. (Se as condições KKT não se mantiverem em , não pode ser o ideal, portanto, as condições KKT são necessárias para que um ponto seja o ideal.) $\mathbf{x}$ $\boldsymbol{\delta}$ $f$ $\mathbf{x}$ $\mathbf{x}$

Imagine que você tem o problema de otimização:

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

Onde e existem restrições. $\mathbf{x} \in \mathbb{R}^n$ $k$

Condições KKT e Farkas Lemma

Seja um vetor de coluna que denota o gradiente de avaliado em . $\nabla f(\mathbf{x})$ $f$ $\mathbf{x}$

Aplicado a essa situação, Farkas Lemma afirma que, para qualquer ponto exatamente uma das seguintes afirmações é válida: $\mathbf{x} \in \mathbb{R}^n$

Existe tal que e $\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}$
Existe tal que e $\boldsymbol{\delta} \in \mathbb{R}^n$ $\forall_j \boldsymbol{\delta}' g_j(\mathbf{x}) \leq 0$ $\boldsymbol{\delta}'\nabla f(\mathbf{x}) < 0$

O que isto significa? Isso significa que, para qualquer ponto viável ,: $\mathbf{x}$

A condição (1) é mantida e as condições da KKT são atendidas.
A condição (2) é mantida e existe uma direção viável que melhora a função objetiva sem aumentar as restrições . (por exemplo, você pode melhorar movendo de para ) $\boldsymbol{\delta}$ $f$ $g_j$ $f$ $\mathbf{x}$ $\mathbf{x} + \epsilon \boldsymbol{\delta}$

A condição (1) afirma que existem multiplicadores não negativos modo que as condições KKT são satisfeitas no ponto . (Geometricamente, diz que o está no cone convexo definido pelos gradientes das restrições.) $\boldsymbol{\lambda}$ $\mathbf{x}$ $- \nabla f$

A condição (2) afirma que no ponto , existe uma direção para se mover (localmente) de modo que: $\mathbf{x}$ $\boldsymbol{\delta}$

Mover na direção reduz a função objetivo (porque o produto escalar de e é menor que zero). $\boldsymbol{\delta}$ $\nabla f(\mathbf{x})$ $\boldsymbol{\delta}$
Mover na direção não aumenta o valor das restrições (porque o produto escalar de e é menor ou igual a zero para todas as restrições ). $\boldsymbol{\delta}$ $\nabla g_j(\mathbf{x})$ $\boldsymbol{\delta}$ $j$

(Geometricamente, a direção viável define um hiperplano de separação entre o vetor e o cone convexo definido pelos vetores .) $\boldsymbol{\delta}$ $-\nabla f(\mathbf{x})$ $\nabla g_j(\mathbf{x})$

(Nota: para mapear esse em Farkas Lema , definir matriz ) $A = \begin{bmatrix} \nabla g_1, \nabla g_2, \ldots, \nabla g_k \end{bmatrix}$

Este argumento fornece a necessidade (mas não a suficiência) das condições KKT em um nível ótimo. Se as condições da KKT não forem atendidas (e as qualificações de restrição forem atendidas), é possível melhorar o objetivo sem violar as restrições.

O papel das qualificações de restrição

O que pode dar errado? Você pode obter situações degeneradas em que os gradientes das restrições não descrevem com precisão as direções possíveis para a mudança.

Há uma infinidade de qualificações de restrição diferentes para escolher, que permitirão que o argumento acima funcione.

A interpretação min, max (imho a mais intuitiva)

Formar o Lagrangiano

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

$f$ $g_j$ $\mathcal{L}$ $\lambda_i$

A solução para o problema de otimização original é equivalente a:

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

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

Isso é:

$\mathbf{x}$ $\mathcal{L}$
$\boldsymbol{\lambda}$ $\mathbf{x}$

$g_2$ $\lambda_2$

Dualidade fraca

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

Desde que detém para qualquer e é também afirma que: $\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)$

Na configuração de Langrian, este resultado que $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) \leq \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

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

Dualidade forte

Sob certas condições especiais (por exemplo, problema convexo onde a condição Slater se mantém), você tem uma dualidade forte (ou seja, a propriedade do ponto de sela).

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

Este belo resultado implica que você pode reverter a ordem do problema.

$\boldsymbol{\lambda}$
$\mathbf{x}$ $\mathcal{L}$

$\lambda$

Matthew Gunn
fonte

Aprecie as informações e os links para preencher as lacunas de entendimento. Permita-me confirmar. A condição (1) significa que KKT diz que para um ponto X ser uma solução, ele precisa satisfazer λ * g (X) = 0, λ> = 0, e o comprimento do gradiente de g (X) é λ vezes de a de f (X), caso contrário, encontraremos o gradiente da direção dos pontos de f (X) onde f (X ') menor pode ser encontrado?

mon

A condição slater é (apenas) uma qualificação de restrição que pode ser aplicada a problemas de otimização convexos, ou seja, torna a KKT necessária. A convexidade torna a KKT suficiente. Portanto, a condição Slater para um problema de otimização convexa, em que a função e as restrições objetivas são convexas e continuamente diferenciáveis, torna a KKT necessária e suficiente para o mínimo global. A condição slater é que existe pelo menos um ponto possível (isto é, satisfazer todas as restrições) que está no interior estrito de todas as restrições não lineares (qualquer coisa ocorre com restrições lineares, desde que possível).

Mark L. Stone

f (x) ser convexo é necessário para que KKT seja suficiente para x ser o mínimo local. Se f (x) ou -g (x) não forem convexos, x satisfazendo KKT pode ser mínimo local, ponto de sela ou máximo local.

g (x) sendo linear, juntamente com f (x) sendo continuamente diferenciáveis, é suficiente para que as condições KKT sejam necessárias para o mínimo local. g (x) ser linear significa que a qualificação de restrição de linearidade para KKT ser necessária para o mínimo local é satisfeita. No entanto, existem outras qualificações de restrição menos restritivas que são suficientes para que as condições da KKT sejam necessárias para o mínimo local. Consulte a seção Condições de regularidade (ou qualificações de restrição) em https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .

Se um mínimo local não tiver restrições "ativas" (portanto, no caso de apenas uma restrição de desigualdade, essa restrição não é satisfeita com a igualdade), os multiplicadores de Lagrange associados a essas restrições devem ser zero; nesse caso, a KKT reduz a condição de o gradiente do objetivo = 0. Nesse caso, existe um "custo" zero para o valor objetivo ideal de um aperto épsilon da restrição.

Mais informações :

A função e as restrições objetivas são convexas e continuamente diferenciáveis implicam que a KKT é suficiente para o mínimo global.

Se a função e as restrições objetivas são continuamente diferenciáveis e as restrições atendem a uma qualificação de restrição, o KKT é necessário para um mínimo local.

Se a função e as restrições objetivas são continuamente diferenciáveis, convexas e as restrições satisfazem uma qualificação de restrição, a KKT é necessária e suficiente para um mínimo global.

$Z$ $Z^T H Z$ $H$ $Z$

Mark L. Stone
fonte