Otimização/KKT

Neste capítulo o objetivo é desenvolver algumas ideias e provar o teorema de Karush–Kuhn–Tucker (também chamado simplesmente de teorema KKT) que será utilizado no capítulo seguinte para explorar os métodos duais. O teorema KKT é bem útil para resolver problemas do tipo

(P)\left\{{\begin{matrix}\min f(x)\\g_{i}(x)\leq 0;i=1,\ldots ,p\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.

Cones

Definição

Um conjunto $C\in \mathbb {R} ^{n}$ é um cone quando

d\in C\Rightarrow td\in C,\forall t\in \mathbb {R} _{+}

Exemplo de um cone no $\mathbb {R} ^{2}$ .

Em outras palavras, a propriedade que caracteriza um cone é que este tipo de conjunto contém todos os múltiplos não nulos de qualquer de seus elementos.

Definição

Dado um subconjunto $C\subset \mathbb {R} ^{n}$ , o cone polar de $C$ é o conjunto definido por

C^{*}=\{p\in \mathbb {R} ^{n}:p^{\top }x\leq 0,\ \forall x\in C\}

.

Observações:

$C^{*}$ é um cone: Se $d\in C^{*}$ tem-se que $d^{\top }x\leq 0,\ \forall x\in C$ . Logo, para qualquer $t\in \mathbb {R} _{+}$ , vale $(td)^{\top }x=td^{\top }x\leq 0,\ \forall x\in C$ . Disto segue que $td\in C^{*}$ , mostrando que $C^{*}$ é um cone.
Sempre se tem que $C\subseteq (C^{*})^{*}$ (Verifique).

Na segunda propriedade a igualdade pode não ocorrer (exemplo?). Para o objetivo deste texto, o ideal seria que a igualdade valesse. Mas será que isso ocorre para algum conjunto? A resposta é sim e, conforme o próximo lema, basta que $C$ seja um cone convexo fechado.

Este módulo tem a seguinte tarefa pendente: Incluir a definição de projeção antes deste ponto, pois ela será usada durante a demonstração

Lema (Farkas)

Se $C\subset \mathbb {R} ^{n}$ um cone convexo fechado, então $C=(C^{*})^{*}$ .

Demonstração

Seja

y\in (C^{*})^{*}

e

w={\text{proj}}_{C}(y)

. Sabendo que a projeção de um ponto sobre um conjunto convexo é única, será mostrado que

w=y

e então ficará provada a inclusão

C\supset (C^{*})^{*}

. Disto seguirá a igualdade entre os dois conjuntos, já que

C

é sempre um subconjunto de

(C^{*})^{*}

.

Pelo teorema da projeção (ver Izmailov & Solodov (2007)), tem-se que $(y-w)^{\top }(x-w)\leq 0,\ \forall x\in C$ . Usando o fato de que $C$ é cone, segue que $0\in C$ e $2w\in C$ e substituindo isto na equação acima obtem-se

(y-w)^{\top }(-w)\leq 0

e

(y-w)^{\top }w\leq 0

.

Dessas desigualdades, conclui-se que $(y-w)^{\top }w=0$ .

De $(y-w)^{\top }(x-w)=(y-w)^{\top }x-(y-w)^{\top }w\leq 0$ , tem-se que $(y-w)^{\top }x\leq 0,\ \forall x\in C$ .

Usando a definição de cone polar, isso implica que $y-w\in C^{*}$ .

Uma vez que $y\in (C^{*})^{*}$ , significa que $(y-w)^{\top }y\leq 0$ .

Desses fatos acima se conclui que

\|y-w\|^{2}=(y-w)^{\top }(y-w)=(y-w)^{\top }y-(y-w)^{\top }w\leq 0

Isso mostra que $y=w$ .

Definição

Dado $x\in C$ , se diz que $d\in \mathbb {R} ^{n}$ é uma direção viável em $x$ , com respeito a $C$ , quando existe $\epsilon >0$ tal que

x+td\in C,\ \forall t\in [0,\epsilon ]

.

O conjunto de todas as direções viáveis em

x

, com respeito ao conjunto

C

, será denotado por

V_{C}(x)

.

Esse conjunto $V_{C}(x)$ é o cone das direções viáveis em $x$ , com respeito a $C$ .

Definição

Uma direção $d\in \mathbb {R} ^{n}$ é uma direção de descida da função $f$ em $x$ , se existe $\epsilon >0$ tal que

f(x+td)<f(x),\ \forall t\in (0,\epsilon ]

.

O conjunto das direções de descida será denotado por

D(x)

.

Caracterização das direções de descida

Lema

Seja $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ uma função diferenciável em $x\in \mathbb {R} ^{n}$ . Então

$\nabla f(x)^{\top }d\leq 0,\ \forall d\in D(x)$ .
$d\in \mathbb {R} ^{n}$ satisfaz $\nabla f(x)^{\top }d<0\ \Rightarrow d\in D(x)$ .

Demonstração

1) Seja

d\in D(x)

. Então,

\forall t\in (0,\epsilon ]

tem-se

f(x+td)<f(x)

.

Usando a série de Taylor, tem-se

f(x)+t\nabla f(x)^{\top }d+o(t)<f(x)

Sendo $t\neq 0$ ,

\nabla f(x)^{\top }d+{\frac {o(t)}{t}}<0

.

Passando o limite com $t\rightarrow 0$ tem-se que $\nabla f(x)^{\top }d\leq 0$ .

2) Novamente aplicando Taylor em $f(x+td)-f(x)$ tem-se

f(x+td)-f(x)=t\nabla f(x)^{\top }d+o(t)

.

Como $t\neq 0$ , tem-se

f(x+td)-f(x)=t(\nabla f(x)^{\top }d+{\frac {o(t)}{t}})

.

Pela hipótese $\nabla f(x)^{\top }d<0$ , com isto

\lim _{t\rightarrow 0}{(\nabla f(x)^{\top }d+{\frac {o(t)}{t}})}=\nabla f(x)^{\top }d<0

.

Pelo teorema da conservação do sinal, existe $\epsilon >0$ tal que $\nabla f(x)^{\top }d+{\frac {o(t)}{t}}<0,\ \forall t\in (0,\epsilon ]$ .

Portanto,

t(\nabla f(x)^{\top }d+{\frac {o(t)}{t}})<0

f(x+td)<f(x)\ \forall t\in (0,\epsilon ]

.

Conclui-se então que $d\in D(x)$ .

O cone viável linearizado

Definição

Dado $x\in C=\{x\in \mathbb {R} ^{n};g_{i}(x)\leq 0{\text{ e }}h_{j}(x)=0\}$ , a desigualdade $g_{i}(x)\leq 0$ é uma restrição ativa em $x$ se $g_{i}(x)=0$ .

Observações

O conjunto formado pelos índices das restrições de desigualdade ativas é denotado por $I(x)$ . Assim,

I(x)=\{i:g_{i}(x)=0\}

Definição

Dado um ponto $x\in C$ e o conjunto $I(x)$ , se define o cone viável linearizado de $C$ a partir de $x$ como

L(x,C)=\{d\in \mathbb {R} ^{n}:\nabla g_{j}(x)^{\top }d\leq 0,\ \forall j\in I(x)\ {\text{e}}\ \nabla h_{i}(x)^{\top }d=0,\ \forall i=1,\dots ,q\}

.

$L(x,C)$ é um cone não-vazio convexo e fechado pois, $0\in L(x,C)$ . E se $y,w\in L(x,C)$ , tem-se

\nabla h_{i}(x)^{\top }(\alpha y+(1-\alpha )w)=\alpha \nabla h_{i}(x)^{\top }y+(1-\alpha )\nabla h_{i}(x)^{\top }w=\alpha 0+(1-\alpha )0=0

e

\nabla g_{j}(x)^{\top }(\alpha y+(1-\alpha )w)=\alpha \nabla g_{j}(x)^{\top }y+(1-\alpha )\nabla g_{j}(x)^{\top }w\leq \alpha 0+(1-\alpha )0\leq 0

.

Portanto $\alpha y+(1-\alpha )w\in L(x,C)$ mostrando que $L(x,C)$ é convexo.

Para mostrar que $L(x,C)$ é fechado, pode-se pegar uma sequência convergente $(d^{k})\in L(x,C)$ e mostrar que o ponto de acumulação dela esta em $L(x,C)$ .

Tem-se que $\nabla h_{i}(x)^{\top }d^{k}=0\ {\text{e}}\ \nabla g_{j}(x)^{\top }d^{k}\leq 0,\ \forall k\in \mathbb {N}$ .

Passando o limite com $k\rightarrow \infty$ , obtem-se

0=\lim _{k\rightarrow \infty }{\nabla h_{i}(x)^{\top }d^{k}}=\nabla h_{i}(x)^{\top }\lim _{k\rightarrow \infty }{d^{k}}=\nabla h_{i}(x)^{\top }d

e

0\geq \lim _{k\rightarrow \infty }{\nabla g_{j}(x)^{\top }d^{k}}=\nabla g_{j}(x)^{\top }\lim _{k\rightarrow \infty }{d^{k}}=\nabla g_{j}(x)^{\top }d

.

Isso mostra que $L(x,C)$ é fechado.

Lema (Caratheodory)

Sejam $y_{1},\dots ,y_{m},w_{1},\dots ,w_{p}\in \mathbb {R} ^{n}$ . Seja $x\in \mathbb {R} ^{n}$ com $x\neq 0$ e $\alpha _{1},\dots ,\alpha _{m},\beta _{1},\dots ,\beta _{p}$ escalares tais que $\beta _{j}\geq 0\ \forall j=1,\dots ,p$ e

x=\sum _{i=1}^{m}\alpha _{i}y_{i}+\sum _{j=1}^{p}\beta _{j}w_{j}

.

Então existem subconjuntos

I\subset \{1,\dots ,m\}{\text{, }}J\subset \{1,\dots ,p\}

e escalares

\alpha _{i}^{*}

com

i\in I

e

\beta _{j}^{*}\ \forall j\in J

tais que

x=\sum _{i\in I}\alpha _{i}^{*}y_{i}+\sum _{j\in J}\beta _{j}^{*}w_{j}

e os vetores

\{y_{i}\}_{i\in I}\cup \{w_{j}\}_{j\in J}

são linearmente independentes.

Demonstração

Sem perda de generalidade, suponha que

\alpha _{i}\neq 0\ \forall i=1,\dots ,m

e

\beta _{j}>0,\ \forall j=1,\dots ,p

. Considere que

\{y_{1},\dots ,y_{m},w_{1},\dots ,w_{p}\}

sejam linearmente dependentes.

Portanto existem escalares $\lambda _{i}$ com $i=1,\dots ,m$ e $\delta _{j}$ com $j=1,\dots ,p$ não todos nulos tais que

0=\sum _{i=1}^{m}\lambda _{i}y_{i}+\sum _{j=1}^{p}\delta _{j}w_{j}

Multiplicando a igualdade acima por $t$ e subtraindo de

x=\sum _{i=1}^{m}\alpha _{i}y_{i}+\sum _{j=1}^{p}\beta _{j}w_{j}

tem-se

x=\sum _{i=1}^{m}(\alpha _{i}-t\lambda _{i})y_{i}+\sum _{j=1}^{p}(\beta _{j}-t\delta _{j})w_{j}

Para $t=0$ certamente nenhum dos coeficientes acima se anula.

Seja ${\bar {t}}$ o $t$ de menor módulo que anula pelo menos um dos coeficientes $\alpha _{i}-t\lambda _{i}$ ou $\beta _{j}-t\delta _{j}$ . Então

x=\sum _{i=1}^{m}(\alpha _{i}-{\bar {t}}\lambda _{i})y_{i}+\sum _{j=1}^{p}(\beta _{j}-{\bar {t}}\delta _{j})w_{j}

Assim, se escreve $x$ como combinação linear de no máximo $m+p-1$ vetores já que $\beta _{j}-{\bar {t}}\delta _{j}\geq 0$ .

Repetindo esse processo obtem-se uma combinação linearmente independente.

Definição

Dado um ponto $x\in C$ , se define o cone $G(x)$ por

G(x)=\{\sum _{i=1}^{q}\alpha _{i}\nabla h_{i}(x)+\sum _{j\in I(x)}\beta _{j}\nabla g_{j}(x):\beta _{j}\geq 0,\ \forall j\in I(x)\}

.

A seguir, serão mostradas algumas propriedades deste cone.

Lema

Para qualquer $x\in C$ , $G(x)$ é um cone convexo e fechado.

Demonstração

Primeiro será mostrado que

G(x)

é de fato um cone. Seja

d\in G(x)

e

t\geq 0

. Então tem-se

td=\sum _{i=1}^{q}t\alpha _{i}\nabla h_{i}(x)+\sum _{j\in I(x)}t\beta _{j}\nabla g_{j}(x)

.

Como $t\beta _{j}\geq 0$ tem-se que $td\in G(x)$ .

Agora, será provado que $G(x)$ é convexo. Para isso seja $y,w\in G(x)$ , isto é,

y=\sum _{i=1}^{q}\alpha _{i}\nabla h_{i}(x)+\sum _{j\in I(x)}\beta _{j}\nabla g_{j}(x)

e

w=\sum _{i=1}^{q}\lambda _{i}\nabla h_{i}(x)+\sum _{j\in I(x)}\delta _{j}\nabla g_{j}(x)

e

t\in [0,1]

.

Logo tem-se,

ty+(1-t)w=\sum _{i=1}^{q}(t\alpha _{i}+(1-t)\lambda _{i})\nabla h_{i}(x)+\sum _{j\in I(x)}(t\beta _{j}+(1-t)\delta _{j})\nabla g_{j}(x)

.

Como $t\beta _{j}+(1-t)\delta _{j}\geq 0$ visto que $\beta _{j}\geq 0$ e $\delta _{j}\geq 0$ . Com isso concluímos que $ty+(1-t)w\in G(x)$ mostrando que $G(x)$ é convexo.

Para mostrar que $G(x)$ é fechado, toma-se uma sequência convergente em $G(x)$ e se mostra que o ponto de acumulação dela pertence a $G(x)$ .

Para isso seja $(z^{k})\subset G(x)$ com $z^{k}\rightarrow z\in \mathbb {R} ^{n}$ . Será mostrado que $z\in G(x)$ .

Escrevendo $G(x)$ em forma matricial tem-se $G(x)=\{A\Delta +B\Omega :\Omega \geq 0\}$ .

Pelo Lema de Caratheodory podemos assumir que $C=(A\ B)$ tem colunas linearmente independentes, e portanto $C^{\top }C$ é não singular.

Uma vez que $(z^{k})\subset G(x)$ , existem $\Gamma ^{k}=(\Delta ^{k}\ \Omega ^{k})^{t}$ com $\Omega ^{k}\geq 0$ tais que $z^{k}=C\Gamma ^{k}$ .

Uma vez que $C^{\top }C$ é não singular, $\Gamma ^{k}=(C^{\top }C)^{-1}C^{\top }z^{k}$ .

Passando o limite obtem-se,

(\Delta \ \Omega )^{t}=\Gamma =\lim _{k\rightarrow \infty }{\Gamma ^{k}}=(C^{\top }C)^{-1}C^{\top }z

com

\Omega \geq 0

.

Isso mostra que $C\Omega \in G(x)$ .

Agora passando o limite em $z^{k}=C\Omega ^{k}$ obtém-se $z=C\Omega$ , mostrando que $z\in G(x)$ .

Lema

Para qualquer $x\in C$ , $G(x)=L(x,C)^{*}$ .

Demonstração

Como

L(x,C)

e

G(x)

são convexos e fechados, tem-se que

L(x,C)=(L(x,C)^{*})^{*}

e

G(x)=(G(x)^{*})^{*}

. Será mostrado então que

L(x,C)=G(x)^{*}

.

Seja $d\in L(x,C)$ . Assim, dado $y\in G(x)$ tem-se

d^{\top }y=d^{\top }(\sum _{i=1}^{q}\alpha _{i}\nabla h_{i}(x)+\sum _{j\in I(x)}\beta _{j}\nabla g_{j}(x))

d^{\top }y=\sum _{i=1}^{q}\alpha _{i}d^{\top }\nabla h_{i}(x)+\sum _{j\in I(x)}\beta _{j}d^{\top }\nabla g_{j}(x)

Mas $\beta \geq 0$ e $d^{\top }\nabla h_{i}(x)=0$ e $d^{\top }\nabla g_{j}(x)\leq 0$ .

Conclui-se então que $d^{\top }y\leq 0$ . Como $y$ é arbitrário, $d\in G(x)^{*}$ .

Agora a volta, seja $d\in G(x)^{*}$ , isto é, $d^{\top }y\leq 0\ \forall y\in G(x)$ .

Em particular, uma vez que $\nabla h_{i}(x)$ e $-\nabla h_{i}(x)\in G(x)\ \forall i=1,\dots ,q$ , tem-se que $d^{\top }\nabla h_{i}(x)=0$ .

Além disso, uma vez que $\nabla g_{j}(x)\in G(x)\ \forall j\in I(x)$ , tem-se que $d^{\top }\nabla g_{j}(x)\leq 0$ .

Logo $d\in L(x,C)$ .

O cone tangente

Definição

Um vetor $d\in \mathbb {R} ^{n}$ é chamado direção tangente em $C$ a partir de $x\in C$ quando ou $d=0$ ou $\exists (x^{k})\subset C$ tal que

x^{k}\rightarrow x

e

{\frac {x^{k}-x}{\|x^{k}-x\|}}\rightarrow {\frac {d}{\|d\|}}

.

Observações

O conjunto de todas as direções tangentes no ponto $x\in C$ , é denominado cone tangente, e denotado por $T(x,C)$ .
Se $a\in C$ , então $T(a,C)$ também pode ser descrito como

T(a,C)=\left\{d\in ;\exists \{d_{k}\}{\text{ com }}d_{k}\to d;\quad \exists \{t_{k}\}{\text{ com }}t_{k}\to 0{\text{ tais que }}x=a+t_{k}d_{k}\in C,\,\forall k\right\}

Exercício

Verifique que $T(a,C)$ é de fato um cone (e portanto merece ser chamado de "cone tangente").

Resolução
A resolução deste exercício é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

Exemplo de cone tangente

Determinar o cone tangente ao ponto $a=(0,0)$ do quadrado unitário com vértices $(0,0)$ , $(0,1)$ , $(-1,1)$ e $(-1,0)$ .

Resolução

Cone tangente a um quadrado unitário com vértice na origem.

Dado qualquer ponto $d=(d_{0},d_{1})$ do 2º quadrante (formado pelos pontos $(x,y)$ tais que $x<0$ e $y>0$ ), pode-se definir:

t_{k}=\left({\frac {1}{2}}\right)^{k}

d_{k}=d

Com essas escolhas, tem-se:

t_{k}\to 0

~~$d_{k}\to d$~~

Logo, $a+t_{k}d_{k}=a+\left({\frac {1}{2}}\right)^{k}d=(0,0)+\left({\frac {d_{0}}{2^{k}}},{\frac {d_{1}}{2^{k}}}\right)=\left({\frac {d_{0}}{2^{k}}},{\frac {d_{1}}{2^{k}}}\right)\in C$ .

Propriedades do cone tangente

O cone tangente definido anteriormente tem as seguintes propriedades:

$T(a,C)$ é fechado e $0\in T(a,C)$
Se $C\subset D$ então $T(a,C)\subset T(a,D)$
Se $V$ é uma vizinhança de $a$ , então $T(a,C)=T(a,V\cap C)$

Observação

A terceira propriedade indica que o cone tangente só depende do que ocorre bem perto de $a$ , no conjunto $C$ .

Lema

Para qualquer $x\in C$ , $T(x,C)$ é fechado.

Demonstração

Seja

(d^{k})\subset T(x,C)

com

d^{k}\rightarrow d\in \mathbb {R} ^{n}

. Será mostrado que

d\in T(x,C)

.

Caso $d=0$ , $d\in T(x,C)$ . Então, suponha-se que $d\neq 0$ .

Neste caso, sem perda de generalidade pode-se considerar que $d^{k}\neq 0,\ \forall k\in \mathbb {N}$ , pois $d^{k}\rightarrow d$ .

Fixando $k\in \mathbb {N}$ tem-se que $d^{k}\in T(x,C)$ . Portanto, existe $(x^{k,j})_{j\in \mathbb {N} }\subset C$ tal que $x^{k,j}\rightarrow x$ e ${\frac {x^{k,j}-x}{\|x^{k,j}-x\|}}\rightarrow {\frac {d^{k}}{\|d^{k}\|}}$ quando $j\rightarrow \infty$ .

Assim para $\epsilon ={\frac {1}{k}}$ existe $j_{k}\in \mathbb {N}$ tal que para $j\geq j_{k}$ , tal que $\|x^{k,j}-x\|<{\frac {1}{k}}$ e ${\bigg |}{\frac {x^{k,j}-x}{\|x^{k,j}-x\|}}-{\frac {d^{k}}{\|d^{k}\|}}{\bigg |}<{\frac {1}{k}}$ .

Em particular, tomando $j=j_{k}$ tem-se

\|x^{k,j_{k}}-x\|<{\frac {1}{k}}

e

{\bigg |}{\frac {x^{k,j_{k}}-x}{\|x^{k,j_{k}}-x\|}}-{\frac {d^{k}}{\|d^{k}\|}}{\bigg |}<{\frac {1}{k}}

.

Tomando o limite quando $k\rightarrow \infty$ , obtem-se que $x^{k}\rightarrow x$ e

{\bigg |}{\frac {x^{k,j_{k}}-x}{\|x^{k,j_{k}}-x\|}}-{\frac {d}{\|d\|}}{\bigg |}\leq {\bigg |}{\frac {x^{k,j_{k}}-x}{\|x^{k,j_{k}}-x\|}}-{\frac {d^{k}}{\|d^{k}\|}}{\bigg |}+{\bigg |}{\frac {d^{k}}{\|d^{k}\|}}-{\frac {d}{\|d\|}}{\bigg |}\rightarrow 0

.

Logo ${\frac {x^{k}-x}{\|x^{k}-x\|}}\rightarrow {\frac {d}{\|d\|}}$ .

Isso mostra que $d\in T(x,C)$ .

Exercício

Verificar que:

$T(a,C)\subset L(a,C)$ .
Se $C=\{(x,y)\in \mathbb {R} ^{2};x^{2}+y\leq 0;\quad x^{2}-y\leq 0\}$ e $a=(0,0)$ , então $T(a,C)\not =L(a,C)$ .

Demonstração

1) Seja

d\in T(a,C)

,

d\neq 0

. Logo

\exists (x^{k})\subset C

tal que

x^{k}\neq a

,

x^{k}\rightarrow a

e

{\frac {x^{k}-a}{\|x^{k}-a\|}}\rightarrow {\frac {d}{\|d\|}}

.

Usando Taylor em torno de $a$ tem-se

0=h_{j}(x^{k})=h_{j}(a)+\nabla h_{j}(x)^{\top }(x^{k}-a)+o(\|x^{k}-a\|)

.

Já que $x^{k}\neq a$ , então $\|x^{k}-a\|\neq 0$ logo pode-se dividir e obtem-se

\nabla h_{j}(a)^{\top }{\frac {(x^{k}-a)}{\|x^{k}-a\|}}+{\frac {o(\|x^{k}-a\|)}{\|x^{k}-a\|}}=0

.

Passando o limite quando $k\rightarrow \infty$ , tem-se $\nabla h_{j}(a)^{\top }{\frac {d}{\|d\|}}=0$ .

Novamente usando Taylor em torno de $a$ para $i\in I(x)$ tem-se

g_{i}(a)+\nabla g_{i}(a)^{\top }(x^{k}-a)+o(\|x^{k}-a\|)\leq 0

\nabla g_{i}(a)^{\top }{\frac {(x^{k}-a)}{\|x^{k}-a\|}}+{\frac {o(\|x^{k}-a\|)}{\|x^{k}-a\|}}\leq 0

Passando o limite quando $k\rightarrow \infty$ tem-se $\nabla g_{i}(a)^{\top }{\frac {d}{\|d\|}}=\leq 0$ .

Donde se conclui que $d\in L(a,C)$ .

2)

Este módulo tem a seguinte tarefa pendente: Colocar figura

Lema

Se $a\in C$ é um mínimo local do problema (P), então $\nabla f(a)^{\top }d\geq 0,\ \forall d\in T(a,C)$ .

Demonstração

Por Taylor tem-se

0\geq f(x^{k})-f(a)=\nabla f(a)^{\top }(x^{k}-a)+o(\|x^{k}-a\|)

0\geq \nabla f(a)^{\top }{\frac {(x^{k}-a)}{\|x^{k}-a\|}}+{\frac {o(\|x^{k}-a\|)}{\|x^{k}-a\|}}

Passando o limite quando $k\rightarrow \infty$ obtem-se

0\geq \nabla f(a)^{\top }{\frac {d}{\|d\|}}

Donde $\nabla f(a)^{\top }d\leq 0\ \forall d\in T(a,C)$ .

Teorema KKT

Teorema (Condições de KKT)

Seja $C=\{x\in \mathbb {R} ^{n};g_{i}(x)\leq 0{\text{ e }}h_{j}(x)=0\}$ e considere $a\in C$ um minimizador local do problema

(P)\left\{{\begin{matrix}\min f(x)\\x\in C\end{matrix}}\right.

Se

T(a,C)^{*}=L(a,C)^{*}

, então existem

u\in \mathbb {R} ^{p}

e

v\in \mathbb {R} ^{q}

tais que:

$-\nabla f(a)=\sum _{i=1}^{p}u_{i}\nabla g_{i}(a)+\sum _{j=1}^{q}v_{j}\nabla h_{j}(a)$
$u_{i}\geq 0,\ \forall i=1,\dots ,p$
$u_{i}g_{i}(a)=0,\ \forall i=1,\dots ,p$ .

Demonstração

Considere

a

um minimizador local do problema (P). Então

(-\nabla f(a))^{\top }d\leq 0,\ \forall d\in T(a,C)

. Pela definição de cone polar isso significa que

-\nabla f(a)\in T(a,C)^{*}

.

Pela hipotése tem-se $-\nabla f(a)\in L(a,C)^{*}$ . Como $L(a,C)=G(a)^{*}$ obtem-se que $-\nabla f(a)\in (G(a)^{*})^{*}$ .

Como foi visto acima $G(a)$ é um cone convexo e fechado. Portanto usando o Lema de Farkas obtem-se que $-\nabla f(a)\in G(a)$ .

Pela definição de $G(a)$ , existem escalares $\delta _{i}$ com $i\in I(a)$ e $\lambda _{j}$ com $j=1,\dots ,q$ tais que

-\nabla f(a)=\sum _{i\in I(a)}\delta _{i}\nabla g_{i}(a)+\sum _{j=1}^{q}\lambda _{j}\nabla h_{j}(a)

com

\delta _{i}\geq 0\ \forall i\in I(a)

.

Como ${\text{card}}I(a)\leq p$ , define-se $v_{j}=\lambda _{j},\ \forall j=1,\dots ,q$ e $u_{i}={\begin{cases}\delta _{i}&\forall i\in I(a)\\0&\forall i\notin I(a)\end{cases}}$

Como $g_{i}(a)=0,\ \forall i\in I(a)$ obtem-se $u_{i}g_{i}(a)=0\ \forall i=1,\dots ,p$ .

Com isso fica provado o Teorema de KKT.