Mostrar código-fonte de 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

:<math>(P)\left\{\begin{matrix}
\min f(x)\\
g_i(x) \le 0; i = 1, \ldots, p\\
h_j(x) = 0; j = 1, \ldots, q
\end{matrix}\right.</math>

== Cones ==

{{Definição
|Um conjunto <math>C \in \mathbb{R}^n</math> é um '''cone''' quando 
:<math>d \in C \Rightarrow td \in C, \forall t \in \mathbb R_{+}</math>
}}
[[Imagem:Cone em duas dimensões.svg|200px|thumb|right|Exemplo de um cone no <math>\mathbb{R}^2</math>.]]

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.

{{clear}}

{{Definição
| Dado um subconjunto <math>C \subset \mathbb{R}^n</math>, o cone polar de <math>C</math> é o conjunto definido por 
:<math>C^{*}=\{ p\in \mathbb{R}^n : p^{\top}x\leq 0,\ \forall x \in C \}</math>.
}}

Observações:
* <math>C^{*}</math> é um cone: Se <math>d \in C^{*}</math> tem-se que <math>d^{\top}x\leq 0,\ \forall x\in C</math>. Logo, para qualquer <math>t\in \mathbb R_+</math>, vale <math>(td)^{\top}x=t d^{\top}x\leq 0,\ \forall x\in C </math>. Disto segue que <math>td\in C^{*}</math>, mostrando que <math>C^{*}</math> é um cone.
* Sempre se tem que <math>C\subseteq (C^{*})^{*}</math> (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 <math>C</math> seja um cone convexo fechado.

{{Tarefa|Incluir a definição de projeção antes deste ponto, pois ela será usada durante a demonstração}}

{{Lema||(Farkas)
|Se <math>C\subset \mathbb{R}^n </math> um cone convexo fechado, então <math>C=(C^{*})^{*}</math>.
}}
{{Demonstração
|Seja <math>y\in (C^{*})^{*}</math> e <math>w=\text{proj}_{C}(y)</math>. Sabendo que a projeção de um ponto sobre um conjunto convexo é única, será mostrado que <math>w=y</math> e então ficará provada a inclusão <math>C \supset (C^{*})^{*}</math>. Disto seguirá a igualdade entre os dois conjuntos, já que <math>C</math> é sempre um subconjunto de <math>(C^{*})^{*}</math>.
Pelo teorema da projeção (ver [[Otimização/Bibliografia#Izmailov & Solodov (2007)|Izmailov & Solodov (2007)]]), tem-se que <math>(y-w)^{\top}(x-w)\leq 0,\ \forall x\in C</math>. Usando o fato de que <math>C</math> é cone, segue que <math>0\in C</math> e <math>2w\in C</math> e substituindo isto na equação acima obtem-se
:<math>(y-w)^{\top}(-w)\leq 0</math> e <math>(y-w)^{\top}w\leq 0</math>.
Dessas desigualdades, conclui-se que <math>(y-w)^{\top}w=0</math>.

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

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

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

Desses fatos acima se conclui que 
:<math>\|y-w\|^2=(y-w)^{\top}(y-w)=(y-w)^{\top}y-(y-w)^{\top}w\leq 0</math>

Isso mostra que <math>y=w</math>.

}}

{{Definição
|Dado <math>x\in C</math>, se diz que '''<math>d\in \mathbb{R}^n</math> é uma direção viável em <math>x</math>, com respeito a <math>C</math>''', quando existe <math>\epsilon > 0</math> tal que
::<math>x+td \in C,\ \forall t\in [0, \epsilon]</math>.
:O conjunto de todas as direções viáveis em <math>x</math>, com respeito ao conjunto <math>C</math>, será denotado por <math>V_C(x)</math>.
}}

Esse conjunto <math>V_C(x)</math> é o cone das direções viáveis em <math>x</math>, com respeito a <math>C</math>.

{{Definição
|Uma direção <math>d\in \mathbb{R}^n</math> é uma '''direção de descida da função <math>f</math> em <math>x</math>''', se existe <math>\epsilon >0</math> tal que
::<math>f(x+td) < f(x),\ \forall t\in (0, \epsilon]</math>.
:O conjunto das direções de descida será denotado por <math>D(x)</math>.
}}

== Caracterização das direções de descida ==

{{Lema
|Seja <math>f: \mathbb{R}^n \rightarrow \mathbb{R}</math> uma função diferenciável em <math>x\in \mathbb{R}^n</math>. Então
# <math>\nabla f(x)^{\top}d \leq 0,\ \forall d\in D(x)</math>.
# <math>d\in \mathbb{R}^n</math> satisfaz <math>\nabla f(x)^{\top}d < 0 \ \Rightarrow d\in D(x)</math>. 
}}

{{Demonstração
| 1) Seja <math>d\in D(x)</math>. Então, <math>\forall t \in (0, \epsilon]</math> tem-se <math>f(x+td)<f(x)</math>.

Usando a série de Taylor, tem-se
:<math>f(x)+t\nabla f(x)^{\top}d + o(t)< f(x)</math>

Sendo <math>t\neq 0</math>, 
:<math>\nabla f(x)^{\top}d + \frac{o(t)}{t}< 0</math>.

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

2) Novamente aplicando Taylor em <math>f(x+td)-f(x)</math> tem-se
:<math>f(x+td)-f(x)=t\nabla f(x)^{\top}d + o(t)</math>.

Como <math>t\neq 0</math>, tem-se
:<math>f(x+td)-f(x)=t(\nabla f(x)^{\top}d +\frac{o(t)}{t} )</math>.

Pela hipótese <math>\nabla f(x)^{\top}d<0 </math>, com isto
:<math>\lim_{t\rightarrow 0}{(\nabla f(x)^{\top}d +\frac{o(t)}{t})}=\nabla f(x)^{\top}d<0</math>.

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

Portanto,
:<math>t(\nabla f(x)^{\top}d +\frac{o(t)}{t})<0</math>
:<math>f(x+td)<f(x)\ \forall t\in (0, \epsilon]</math>.

Conclui-se então que <math>d\in D(x)</math>.
}}

== O cone viável linearizado ==

{{Definição
|Dado <math>x \in C = \{ x \in \mathbb{R}^n; g_i(x) \le 0 \text{ e } h_j(x) = 0\}</math>, a desigualdade <math>g_i(x) \le 0</math> é uma '''restrição ativa''' em <math>x</math> se <math>g_i(x)=0</math>.
}}
;Observações
* O conjunto formado pelos índices das restrições de desigualdade ativas é denotado por <math>I(x)</math>. Assim,
:<math>I(x)=\{i:g_{i}(x)=0\}</math>

{{Definição
| Dado um ponto <math>x\in C</math> e o conjunto <math>I(x)</math>, se define o '''cone viável linearizado''' de <math>C</math> a partir de <math>x</math> como
:<math>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\}</math>.
}}

<math>L(x, C)</math> é um cone não-vazio convexo e fechado pois, <math>0\in L(x, C)</math>. E se <math>y, w \in L(x, C)</math>, tem-se
:<math>\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</math> e
:<math>\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</math>.

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

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

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

Passando o limite com <math>k \rightarrow \infty</math>, obtem-se
:<math>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</math> e
:<math>0\ge \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</math>.

Isso mostra que <math>L(x, C)</math> é fechado.


{{Lema||(Caratheodory)
|Sejam <math>y_1, \dots, y_m, w_1, \dots, w_p \in \mathbb{R}^n</math>. Seja <math>x\in \mathbb{R}^n</math> com <math>x\neq 0</math> e <math>\alpha_1, \dots, \alpha_m, \beta_1, \dots, \beta_p</math> escalares tais que<math>\beta_j\ge 0\ \forall j=1, \dots, p</math> e
:<math>x=\sum_{i=1}^m \alpha_{i}y_{i}+\sum_{j=1}^p \beta_{j}w_j</math>.

Então existem subconjuntos <math>I\subset \{1, \dots, m\}\text{, } J\subset\{1, \dots, p\}</math> e escalares <math>\alpha_{i}^{*}</math> com <math>i\in I </math>e <math>\beta_{j}^{*}\ \forall j\in J</math> tais que 
:<math>x=\sum_{i\in I} \alpha_{i}^{*}y_{i}+\sum_{j\in J} \beta_{j}^{*}w_j</math> e os vetores <math>\{y_i\}_{i\in I}\cup \{w_j\}_{j\in J}</math> são linearmente independentes.
}}
{{Demonstração
|Sem perda de generalidade, suponha que <math>\alpha_{i}\neq 0\ \forall i=1, \dots, m</math> e <math>\beta_j>0,\ \forall j=1, \dots, p</math>. Considere que <math>\{y_1, \dots, y_m, w_1, \dots, w_p\}</math> sejam linearmente dependentes.

Portanto existem escalares <math>\lambda_i</math> com <math>i=1, \dots, m</math> e <math>\delta_j</math> com <math>j=1, \dots, p</math> não todos nulos tais que
:<math>0=\sum_{i=1}^m \lambda_{i}y_{i}+\sum_{j=1}^p \delta_{j}w_j</math>

Multiplicando a igualdade acima por <math>t</math> e subtraindo de 
:<math>x=\sum_{i=1}^m \alpha_{i}y_{i}+\sum_{j=1}^p \beta_{j}w_j</math> tem-se

:<math>x=\sum_{i=1}^m (\alpha_{i}-t\lambda_i)y_{i}+\sum_{j=1}^p (\beta_{j}-t\delta_j)w_j</math>

Para <math>t=0</math> certamente nenhum dos coeficientes acima se anula.

Seja <math>\bar{t}</math> o <math>t</math> de menor módulo que anula pelo menos um dos coeficientes <math>\alpha_{i}-t\lambda_i</math> ou <math>\beta_{j}-t\delta_j</math>. Então 
:<math>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</math>

Assim, se escreve <math>x</math> como combinação linear de no máximo <math>m+p-1</math> vetores já que <math>\beta_{j}-\bar{t}\delta_j\ge 0</math>.

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


{{Definição
| Dado um ponto <math>x\in C</math>, se define o cone <math>G(x)</math> por 
::<math>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}\ge 0,\ \forall j\in I(x)\}</math>.
}}

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

{{Lema
|Para qualquer <math>x\in C</math>, <math>G(x)</math> é um cone convexo e fechado. 
}}
{{Demonstração
| Primeiro será mostrado que <math>G(x)</math> é de fato um cone. Seja <math>d\in G(x)</math> e <math>t\ge 0</math>. Então tem-se
:<math>td=\sum_{i=1}^q t\alpha_{i}\nabla h_{i}(x) +\sum_{j\in I(x)} t\beta_{j}\nabla g_{j}(x)</math>.

Como <math>t\beta_{j}\ge 0</math> tem-se que <math>td\in G(x)</math>.

Agora, será provado que <math>G(x)</math> é convexo. Para isso seja <math>y, w\in G(x)</math>, isto é, 
:<math>y=\sum_{i=1}^q \alpha_{i}\nabla h_{i}(x) +\sum_{j\in I(x)} \beta_{j}\nabla g_{j}(x)</math> e
:<math>w=\sum_{i=1}^q \lambda_{i}\nabla h_{i}(x) +\sum_{j\in I(x)} \delta_{j}\nabla g_{j}(x)</math> e <math>t\in [0, 1]</math>.

Logo tem-se, 
:<math>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)</math>.

Como <math>t\beta_{j}+(1-t)\delta_{j}\ge 0</math> visto que <math>\beta_{j}\ge 0</math> e <math>\delta_{j}\ge 0</math>. Com isso concluímos que <math>ty+(1-t)w\in G(x)</math> mostrando que <math>G(x)</math> é convexo. 

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

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

Escrevendo <math>G(x)</math> em forma matricial tem-se <math>G(x)=\{A\Delta+B\Omega:\Omega\ge 0 \}</math>.

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

Uma vez que <math>(z^k)\subset G(x)</math>, existem <math>\Gamma^{k}=(\Delta^{k}\ \Omega^{k})^t</math> com <math>\Omega^{k}\ge 0</math> tais que <math>z^{k}=C\Gamma^{k}</math>.

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

Passando o limite obtem-se, 
:<math>(\Delta \ \Omega)^t=\Gamma=\lim_{k\rightarrow \infty}{\Gamma^{k}}=(C^{\top}C)^{-1}C^{\top}z</math> com <math>\Omega\ge 0</math>.

Isso mostra que <math>C\Omega \in G(x)</math>.

Agora passando o limite em <math>z^k=C\Omega^k</math> obtém-se <math>z=C\Omega</math>, mostrando que <math>z\in G(x)</math>.

}}

{{Lema
|Para qualquer <math>x\in C</math>, <math>G(x)=L(x, C)^{*}</math>. 
}}
{{Demonstração
| Como <math>L(x, C)</math> e <math>G(x)</math> são convexos e fechados, tem-se que <math>L(x, C)=(L(x, C)^{*})^{*}</math> e <math>G(x)=(G(x)^{*})^{*}</math>. Será mostrado então que <math>L(x, C)=G(x)^{*}</math>.
Seja <math>d\in L(x, C)</math>. Assim, dado <math>y\in G(x)</math> tem-se
:<math>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))</math>
:<math>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)</math>

Mas <math>\beta\ge 0</math> e <math>d^{\top}\nabla h_i(x)=0</math> e <math>d^{\top}\nabla g_j(x)\leq 0</math>.

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

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

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

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

Logo <math>d\in L(x, C)</math>. 
}}

== O cone tangente ==

{{Definição
| Um vetor <math>d\in \mathbb{R}^n</math> é chamado '''direção tangente em <math>C</math> a partir de <math>x\in C</math>''' quando ou <math>d=0</math> ou <math>\exist (x^k)\subset C</math> tal que
:<math>x^k\rightarrow x</math> e <math>\frac{x^k-x}{\|x^k-x\|}\rightarrow \frac{d}{\|d\|}</math>.
}}

;Observações
* O conjunto de todas as direções tangentes no ponto <math>x \in C</math>, é denominado '''cone tangente''', e denotado por <math>T(x, C)</math>.
* Se <math>a \in C</math>, então <math>T(a, C)</math> também pode ser descrito como
:<math>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\}</math>

{{Exercício
|Verifique que <math>T(a, C)</math> é de fato um cone (e portanto merece ser chamado de "cone tangente").
}}
{{Resolução}}

==== Exemplo de cone tangente ====

Determinar o cone tangente ao ponto <math>a = (0, 0)</math> do quadrado unitário com vértices <math>(0, 0)</math>, <math>(0, 1)</math>, <math>(-1, 1)</math> e <math>(-1, 0)</math>.
{{Resolução
|[[Imagem:Cone tangente de um quadrado unitário.svg|200px|thumb|right|Cone tangente a um quadrado unitário com vértice na origem.]]
Dado qualquer ponto <math>d = (d_0, d_1) </math> do 2º quadrante (formado pelos pontos <math>(x, y)</math> tais que <math>x<0</math> e <math>y>0</math>), pode-se definir:

:<math>t_k = \left(\frac{1}{2}\right)^k</math>
:<math>d_k = d</math>
Com essas escolhas, tem-se:
:<math>t_k \to 0</math>
:<s><math>d_k \to d</math></s>
Logo, <math>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</math>.

}}

==== Propriedades do cone tangente ====

{{Wikipédia|Cone tangente}}

O cone tangente definido anteriormente tem as seguintes propriedades:
# <math>T(a, C)</math> é fechado e <math>0 \in T(a, C)</math>
# Se <math>C \subset D</math> então <math>T(a, C) \subset T(a, D)</math>
# Se <math>V</math> é uma vizinhança de <math>a</math>, então <math>T(a, C) = T(a, V \cap C)</math>

;Observação
A terceira propriedade indica que o cone tangente só depende do que ocorre bem perto de <math>a</math>, no conjunto <math>C</math>.


{{Lema
|Para qualquer <math>x\in C</math>, <math>T(x, C)</math> é fechado. 
}}
{{Demonstração
|Seja <math>(d^k)\subset T(x, C)</math> com <math>d^k\rightarrow d\in \mathbb{R}^n</math>. Será mostrado que <math>d\in T(x, C)</math>.

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

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

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

Assim para <math>\epsilon=\frac{1}{k}</math> existe <math>j_k\in \mathbb{N}</math> tal que para <math>j\ge j_k</math>, tal que <math>\|x^{k, j}-x\|<\frac{1}{k}</math> e <math>\bigg|\frac{x^{k, j}-x}{\|x^{k, j}-x\|}- \frac{d^k}{\|d^k\|}\bigg|<\frac{1}{k}</math>.

Em particular, tomando <math>j=j_k</math> tem-se
:<math>\|x^{k, j_k}-x\|<\frac{1}{k}</math> e <math>\bigg|\frac{x^{k, j_k}-x}{\|x^{k, j_k}-x\|}- \frac{d^k}{\|d^k\|}\bigg|<\frac{1}{k}</math>.

Tomando o limite quando <math>k\rightarrow \infty</math>, obtem-se que <math>x^k\rightarrow x</math> e
:<math>\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</math>.

Logo <math>\frac{x^k-x}{\|x^k-x\|}\rightarrow \frac{d}{\|d\|}</math>.

Isso mostra que <math>d\in T(x, C)</math>.

}}


{{Exercício
|Verificar que:
# <math>T(a, C) \subset L(a, C)</math>.
# Se <math>C = \{(x, y) \in \mathbb{R}^2; x^2 + y \le 0;\quad x^2 - y \le 0\}</math> e <math>a = (0, 0)</math>, então <math>T(a, C) \not = L(a, C)</math>.
}}
{{Demonstração
| 1) Seja <math>d\in T(a, C)</math>, <math>d\neq 0</math>. Logo <math>\exist (x^k)\subset C</math> tal que <math>x^k\neq a</math>, <math>x^k\rightarrow a</math> e <math>\frac{x^k-a}{\|x^k-a\|}\rightarrow \frac{d}{\|d\|}</math>.

Usando Taylor em torno de <math>a</math> tem-se
:<math>0=h_j(x^k)=h_j(a)+\nabla h_j(x)^{\top}(x^k-a)+o(\|x^k-a\|)</math>. 

Já que <math>x^k\neq a</math>, então <math>\|x^k-a\|\neq 0</math> logo pode-se dividir e obtem-se
:<math>\nabla h_j(a)^{\top}\frac{(x^k-a)}{\|x^k-a\|}+\frac{o(\|x^k-a\|)}{\|x^k-a\|}=0</math>.

Passando o limite quando <math>k\rightarrow \infty</math>, tem-se <math>\nabla h_j(a)^{\top}\frac{d}{\|d\|}=0</math>.

Novamente usando Taylor em torno de <math>a</math> para <math>i\in I(x)</math> tem-se
:<math>g_i(a)+\nabla g_i(a)^{\top}(x^k-a)+o(\|x^k-a\|)\leq 0</math>

::<math>\nabla g_i(a)^{\top}\frac{(x^k-a)}{\|x^k-a\|}+\frac{o(\|x^k-a\|)}{\|x^k-a\|}\leq 0</math>

Passando o limite quando <math>k\rightarrow \infty</math> tem-se <math>\nabla g_i(a)^{\top}\frac{d}{\|d\|}=\leq 0</math>.

Donde se conclui que <math>d\in L(a, C)</math>.

2) {{Tarefa| Colocar figura}}
}}

{{Lema
|Se <math>a\in C</math> é um mínimo local do problema (P), então <math>\nabla f(a)^{\top}d\ge 0,\ \forall d\in T(a, C)</math>.
}}
{{Demonstração
| Por Taylor tem-se
:<math>0\ge f(x^k)-f(a)=\nabla f(a)^{\top}(x^k-a)+o(\|x^k-a\|)</math>

:<math>0\ge \nabla f(a)^{\top}\frac{(x^k-a)}{\|x^k-a\|}+\frac{o(\|x^k-a\|)}{\|x^k-a\|}</math>

Passando o limite quando <math>k\rightarrow \infty</math> obtem-se

:<math>0\ge \nabla f(a)^{\top}\frac{d}{\|d\|}</math>

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

}}

== Teorema KKT ==
{{Teorema|(Condições de KKT)
|Seja <math>C = \{ x \in \mathbb{R}^n; g_i(x) \le 0 \text{ e } h_j(x) = 0\}</math> e considere <math>a\in C</math> um minimizador local do problema 
:<math>(P)\left\{\begin{matrix}
\min f(x)\\
x \in C
\end{matrix}\right.</math>

Se <math>T(a, C)^{*}=L(a, C)^{*}</math>, então existem <math>u \in \mathbb{R}^p</math> e <math>v \in \mathbb{R}^q</math> tais que:
#<math>-\nabla f(a) = \sum_{i=1}^p u_i\nabla g_i(a) + \sum_{j=1}^q v_j\nabla h_j(a)</math>
#<math>u_i \ge 0,\ \forall i=1, \dots, p</math>
#<math>u_ig_i(a)=0,\ \forall i=1, \dots, p</math>.

}}
{{Demonstração
| Considere <math>a</math> um minimizador local do problema '''(P)'''. Então <math>(-\nabla f(a))^{\top}d\leq 0,\ \forall d\in T(a, C)</math>. Pela definição de cone polar isso significa que <math>-\nabla f(a)\in T(a, C)^{*}</math>.

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

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

Pela definição de <math>G(a)</math>, existem escalares <math>\delta_i</math> com <math>i\in I(a)</math> e <math>\lambda_j</math> com <math>j=1, \dots, q</math> tais que
:<math>-\nabla f(a) = \sum_{i\in I(a)} \delta_i\nabla g_i(a) + \sum_{j=1}^q \lambda_j\nabla h_j(a)</math> com <math>\delta_i\ge 0\ \forall i\in I(a)</math>.

Como <math>\text{card}I(a)\leq p</math>, define-se <math>v_j = \lambda_j,\ \forall j=1, \dots, q</math> e <math>u_i=\begin{cases} 
 \delta_i & \forall i\in I(a) \\
 0 & \forall i\notin I(a) 
\end{cases}
</math>

Como <math>g_i(a)=0,\ \forall i\in I(a)</math> obtem-se <math>u_ig_i(a)=0\ \forall i=1, \dots, p</math>.

Com isso fica provado o Teorema de KKT.

}}


{{AutoCat}}