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)\{\begin{array}{c}minf(x)\\ g_i(x)\le 0;i=1,\dots ,p\\ h_j(x)=0;j=1,\dots ,q\end{array}$

Cones

Definição

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

$d\in C\Rightarrow td\in C,\mathrm{\forall }t\in {ℝ}_{+}$

Exemplo de um cone no ${ℝ}^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 {ℝ}^n$, o cone polar de $C$ é o conjunto definido por

$C^{\ast }=\{p\in {ℝ}^n:p^{\mathrm{\top }}x\le 0,\mathrm{\forall }x\in C\}$.

Observações:

• $C^{\ast }$ é um cone: Se $d\in C^{\ast }$ tem-se que $d^{\mathrm{\top }}x\le 0,\mathrm{\forall }x\in C$. Logo, para qualquer $t\in {ℝ}_{+}$, vale $(td{)}^{\mathrm{\top }}x=t{d}^{\mathrm{\top }}x\le 0,\mathrm{\forall }x\in C$. Disto segue que $td\in C^{\ast }$, mostrando que $C^{\ast }$ é um cone.
• Sempre se tem que $C\subseteq (C^{\ast }{)}^{\ast }$ (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 {ℝ}^n$ um cone convexo fechado, então $C=(C^{\ast }{)}^{\ast }$.

Demonstração

Seja $y\in (C^{\ast }{)}^{\ast }$ 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^{\ast }{)}^{\ast }$. Disto seguirá a igualdade entre os dois conjuntos, já que $C$ é sempre um subconjunto de $(C^{\ast }{)}^{\ast }$. Pelo teorema da projeção (ver Izmailov & Solodov (2007)), tem-se que $(y-w{)}^{\mathrm{\top }}(x-w)\le 0,\mathrm{\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{)}^{\mathrm{\top }}(-w)\le 0$ e $(y-w{)}^{\mathrm{\top }}w\le 0$. Dessas desigualdades, conclui-se que $(y-w{)}^{\mathrm{\top }}w=0$. De $(y-w{)}^{\mathrm{\top }}(x-w)=(y-w{)}^{\mathrm{\top }}x-(y-w{)}^{\mathrm{\top }}w\le 0$, tem-se que $(y-w{)}^{\mathrm{\top }}x\le 0,\mathrm{\forall }x\in C$. Usando a definição de cone polar, isso implica que $y-w\in C^{\ast }$. Uma vez que $y\in (C^{\ast }{)}^{\ast }$, significa que $(y-w{)}^{\mathrm{\top }}y\le 0$. Desses fatos acima se conclui que $\Vert y-w{\Vert }^2=(y-w{)}^{\mathrm{\top }}(y-w)=(y-w{)}^{\mathrm{\top }}y-(y-w{)}^{\mathrm{\top }}w\le 0$ Isso mostra que $y=w$.

Definição

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

$x+td\in C,\mathrm{\forall }t\in [0,ϵ]$.

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 {ℝ}^n$ é uma direção de descida da função $f$ em $x$, se existe $ϵ>0$ tal que

$f(x+td)<f(x),\mathrm{\forall }t\in (0,ϵ]$.

O conjunto das direções de descida será denotado por $D(x)$.

Caracterização das direções de descida

Lema

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

1. $\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d\le 0,\mathrm{\forall }d\in D(x)$.
2. $d\in {ℝ}^n$ satisfaz $\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d<0\Rightarrow d\in D(x)$.

Demonstração

1) Seja $d\in D(x)$. Então, $\mathrm{\forall }t\in (0,ϵ]$ tem-se $f(x+td)<f(x)$. Usando a série de Taylor, tem-se $f(x)+t\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d+o(t)<f(x)$ Sendo $t\ne 0$, $\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d+\frac{o(t)}{t}<0$. Passando o limite com $t\to 0$ tem-se que $\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d\le 0$. 2) Novamente aplicando Taylor em $f(x+td)-f(x)$ tem-se $f(x+td)-f(x)=t\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d+o(t)$. Como $t\ne 0$, tem-se $f(x+td)-f(x)=t(\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d+\frac{o(t)}{t})$. Pela hipótese $\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d<0$, com isto $\underset{t\to 0}{lim}(\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d+\frac{o(t)}{t})=\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d<0$. Pelo teorema da conservação do sinal, existe $ϵ>0$ tal que $\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d+\frac{o(t)}{t}<0,\mathrm{\forall }t\in (0,ϵ]$. Portanto, $t(\mathrm{\nabla }f(x{)}^{\mathrm{\top }}d+\frac{o(t)}{t})<0$ $f(x+td)<f(x)\mathrm{\forall }t\in (0,ϵ]$. Conclui-se então que $d\in D(x)$.

O cone viável linearizado

Definição

Dado $x\in C=\{x\in {ℝ}^n;g_i(x)\le 0\text{ e }{h}_j(x)=0\}$, a desigualdade $g_i(x)\le 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 {ℝ}^n:\mathrm{\nabla }{g}_j(x{)}^{\mathrm{\top }}d\le 0,\mathrm{\forall }j\in I(x)\text{e}\mathrm{\nabla }{h}_i(x{)}^{\mathrm{\top }}d=0,\mathrm{\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

$\mathrm{\nabla }{h}_i(x{)}^{\mathrm{\top }}(\alpha y+(1-\alpha )w)=\alpha \mathrm{\nabla }{h}_i(x{)}^{\mathrm{\top }}y+(1-\alpha )\mathrm{\nabla }{h}_i(x{)}^{\mathrm{\top }}w=\alpha 0+(1-\alpha )0=0$ e

$\mathrm{\nabla }{g}_j(x{)}^{\mathrm{\top }}(\alpha y+(1-\alpha )w)=\alpha \mathrm{\nabla }{g}_j(x{)}^{\mathrm{\top }}y+(1-\alpha )\mathrm{\nabla }{g}_j(x{)}^{\mathrm{\top }}w\le \alpha 0+(1-\alpha )0\le 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 $\mathrm{\nabla }{h}_i(x{)}^{\mathrm{\top }}{d}^k=0\text{e}\mathrm{\nabla }{g}_j(x{)}^{\mathrm{\top }}{d}^k\le 0,\mathrm{\forall }k\in \mathbb{N}$.

Passando o limite com $k\to \mathrm{\infty }$, obtem-se

$0=\underset{k\to \mathrm{\infty }}{lim}\mathrm{\nabla }{h}_i(x{)}^{\mathrm{\top }}{d}^k=\mathrm{\nabla }{h}_i(x{)}^{\mathrm{\top }}\underset{k\to \mathrm{\infty }}{lim}{d}^k=\mathrm{\nabla }{h}_i(x{)}^{\mathrm{\top }}d$ e

$0\ge \underset{k\to \mathrm{\infty }}{lim}\mathrm{\nabla }{g}_j(x{)}^{\mathrm{\top }}{d}^k=\mathrm{\nabla }{g}_j(x{)}^{\mathrm{\top }}\underset{k\to \mathrm{\infty }}{lim}{d}^k=\mathrm{\nabla }{g}_j(x{)}^{\mathrm{\top }}d$.

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

Lema  (Caratheodory)

Sejam $y_1,\dots ,y_m,w_1,\dots ,w_p\in {ℝ}^n$. Seja $x\in {ℝ}^n$ com $x\ne 0$ e ${\alpha }_1,\dots ,{\alpha }_m,{\beta }_1,\dots ,{\beta }_p$ escalares tais que${\beta }_j\ge 0\mathrm{\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^{\ast }$ com $i\in I$e ${\beta }_j^{\ast }\mathrm{\forall }j\in J$ tais que

$x=\sum _{i\in I}{\alpha }_i^{\ast }{y}_i+\sum _{j\in J}{\beta }_j^{\ast }{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\ne 0\mathrm{\forall }i=1,\dots ,m$ e ${\beta }_j>0,\mathrm{\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 $\overline{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-\overline{t}{\lambda }_i)y_i+\sum _{j=1}^p({\beta }_j-\overline{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-\overline{t}{\delta }_j\ge 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\mathrm{\nabla }{h}_i(x)+\sum _{j\in I(x)}{\beta }_j\mathrm{\nabla }{g}_j(x):{\beta }_j\ge 0,\mathrm{\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\ge 0$. Então tem-se $td=\sum _{i=1}^{q}t{\alpha }_i\mathrm{\nabla }{h}_i(x)+\sum _{j\in I(x)}t{\beta }_j\mathrm{\nabla }{g}_j(x)$. Como $t{\beta }_j\ge 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\mathrm{\nabla }{h}_i(x)+\sum _{j\in I(x)}{\beta }_j\mathrm{\nabla }{g}_j(x)$ e $w=\sum _{i=1}^q{\lambda }_i\mathrm{\nabla }{h}_i(x)+\sum _{j\in I(x)}{\delta }_j\mathrm{\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)\mathrm{\nabla }{h}_i(x)+\sum _{j\in I(x)}(t{\beta }_j+(1-t){\delta }_j)\mathrm{\nabla }{g}_j(x)$. Como $t{\beta }_j+(1-t){\delta }_j\ge 0$ visto que ${\beta }_j\ge 0$ e ${\delta }_j\ge 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\to z\in {ℝ}^n$. Será mostrado que $z\in G(x)$. Escrevendo $G(x)$ em forma matricial tem-se $G(x)=\{A\mathrm{\Delta }+B\mathrm{\Omega }:\mathrm{\Omega }\ge 0\}$. Pelo Lema de Caratheodory podemos assumir que $C=(AB)$ tem colunas linearmente independentes, e portanto $C^{\mathrm{\top }}C$ é não singular. Uma vez que $(z^k)\subset G(x)$, existem ${\mathrm{\Gamma }}^k=({\mathrm{\Delta }}^k{\mathrm{\Omega }}^k{)}^t$ com ${\mathrm{\Omega }}^k\ge 0$ tais que $z^k=C{\Gamma }^k$. Uma vez que $C^{\mathrm{\top }}C$ é não singular, ${\mathrm{\Gamma }}^k=(C^{\mathrm{\top }}C{)}^{-1}{C}^{\mathrm{\top }}{z}^k$. Passando o limite obtem-se, $(\mathrm{\Delta }\mathrm{\Omega }{)}^t=\mathrm{\Gamma }=\underset{k\to \mathrm{\infty }}{lim}{\mathrm{\Gamma }}^k=(C^{\mathrm{\top }}C{)}^{-1}{C}^{\mathrm{\top }}z$ com $\mathrm{\Omega }\ge 0$. Isso mostra que $C\mathrm{\Omega }\in G(x)$. Agora passando o limite em $z^k=C{\Omega }^k$ obtém-se $z=C\mathrm{\Omega }$, mostrando que $z\in G(x)$.

Lema

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

Demonstração

Como $L(x,C)$ e $G(x)$ são convexos e fechados, tem-se que $L(x,C)=(L(x,C{)}^{\ast }{)}^{\ast }$ e $G(x)=(G(x{)}^{\ast }{)}^{\ast }$. Será mostrado então que $L(x,C)=G(x{)}^{\ast }$. Seja $d\in L(x,C)$. Assim, dado $y\in G(x)$ tem-se $d^{\mathrm{\top }}y=d^{\mathrm{\top }}(\sum _{i=1}^q{\alpha }_i\mathrm{\nabla }{h}_i(x)+\sum _{j\in I(x)}{\beta }_j\mathrm{\nabla }{g}_j(x))$ $d^{\mathrm{\top }}y=\sum _{i=1}^q{\alpha }_i{d}^{\mathrm{\top }}\mathrm{\nabla }{h}_i(x)+\sum _{j\in I(x)}{\beta }_j{d}^{\mathrm{\top }}\mathrm{\nabla }{g}_j(x)$ Mas $\beta \ge 0$ e $d^{\mathrm{\top }}\mathrm{\nabla }{h}_i(x)=0$ e $d^{\mathrm{\top }}\mathrm{\nabla }{g}_j(x)\le 0$. Conclui-se então que $d^{\mathrm{\top }}y\le 0$. Como $y$ é arbitrário, $d\in G(x{)}^{\ast }$. Agora a volta, seja $d\in G(x{)}^{\ast }$, isto é, $d^{\mathrm{\top }}y\le 0\mathrm{\forall }y\in G(x)$. Em particular, uma vez que $\mathrm{\nabla }{h}_i(x)$ e $-\mathrm{\nabla }{h}_i(x)\in G(x)\mathrm{\forall }i=1,\dots ,q$, tem-se que $d^{\mathrm{\top }}\mathrm{\nabla }{h}_i(x)=0$. Além disso, uma vez que $\mathrm{\nabla }{g}_j(x)\in G(x)\mathrm{\forall }j\in I(x)$, tem-se que $d^{\mathrm{\top }}\mathrm{\nabla }{g}_j(x)\le 0$. Logo $d\in L(x,C)$.

O cone tangente

Definição

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

$x^k\to x$ e $\frac{x^k-x}{\Vert x^k-x\Vert }\to \frac{d}{\Vert d\Vert }$.

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)=\{d\in ;\mathrm{\exists }\{d_k\}\text{ com }{d}_k\to d;\mathrm{\exists }\{t_k\}\text{ com }{t}_k\to 0\text{ tais que }x=a+t_k{d}_k\in C,\mathrm{\forall }k\}$

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)+(\frac{d_0}{2^k},\frac{d_1}{2^k})=(\frac{d_0}{2^k},\frac{d_1}{2^k})\in C$.

Propriedades do cone tangente

O cone tangente definido anteriormente tem as seguintes propriedades:

1. $T(a,C)$ é fechado e $0\in T(a,C)$
2. Se $C\subset D$ então $T(a,C)\subset T(a,D)$
3. 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\to d\in {ℝ}^n$. Será mostrado que $d\in T(x,C)$. Caso $d=0$, $d\in T(x,C)$. Então, suponha-se que $d\ne 0$. Neste caso, sem perda de generalidade pode-se considerar que $d^k\ne 0,\mathrm{\forall }k\in \mathbb{N}$, pois $d^k\to 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}\to x$ e $\frac{x^{k,j}-x}{\Vert x^{k,j}-x\Vert }\to \frac{d^k}{\Vert d^k\Vert }$ quando $j\to \mathrm{\infty }$. Assim para $ϵ=\frac{1}{k}$ existe $j_k\in \mathbb{N}$ tal que para $j\ge j_k$, tal que $\Vert x^{k,j}-x\Vert <\frac{1}{k}$ e $|\frac{x^{k,j}-x}{\Vert x^{k,j}-x\Vert }-\frac{d^k}{\Vert d^k\Vert }|<\frac{1}{k}$. Em particular, tomando $j=j_k$ tem-se $\Vert x^{k,j_k}-x\Vert <\frac{1}{k}$ e $|\frac{x^{k,j_k}-x}{\Vert x^{k,j_k}-x\Vert }-\frac{d^k}{\Vert d^k\Vert }|<\frac{1}{k}$. Tomando o limite quando $k\to \mathrm{\infty }$, obtem-se que $x^k\to x$ e $|\frac{x^{k,j_k}-x}{\Vert x^{k,j_k}-x\Vert }-\frac{d}{\Vert d\Vert }|\le |\frac{x^{k,j_k}-x}{\Vert x^{k,j_k}-x\Vert }-\frac{d^k}{\Vert d^k\Vert }|+|\frac{d^k}{\Vert d^k\Vert }-\frac{d}{\Vert d\Vert }|\to 0$. Logo $\frac{x^k-x}{\Vert x^k-x\Vert }\to \frac{d}{\Vert d\Vert }$. Isso mostra que $d\in T(x,C)$.

Exercício

Verificar que:

1. $T(a,C)\subset L(a,C)$.
2. Se $C=\{(x,y)\in {ℝ}^2;x^2+y\le 0;x^2-y\le 0\}$ e $a=(0,0)$, então $T(a,C)≠L(a,C)$.

Demonstração

1) Seja $d\in T(a,C)$, $d\ne 0$. Logo $\mathrm{\exists }(x^k)\subset C$ tal que $x^k\ne a$, $x^k\to a$ e $\frac{x^k-a}{\Vert x^k-a\Vert }\to \frac{d}{\Vert d\Vert }$. Usando Taylor em torno de $a$ tem-se $0=h_j(x^k)=h_j(a)+\mathrm{\nabla }{h}_j(x{)}^{\mathrm{\top }}(x^k-a)+o(\Vert x^k-a\Vert )$. Já que $x^k\ne a$, então $\Vert x^k-a\Vert \ne 0$ logo pode-se dividir e obtem-se $\mathrm{\nabla }{h}_j(a{)}^{\mathrm{\top }}\frac{(x^k-a)}{\Vert x^k-a\Vert }+\frac{o(\Vert x^k-a\Vert )}{\Vert x^k-a\Vert }=0$. Passando o limite quando $k\to \mathrm{\infty }$, tem-se $\mathrm{\nabla }{h}_j(a{)}^{\mathrm{\top }}\frac{d}{\Vert d\Vert }=0$. Novamente usando Taylor em torno de $a$ para $i\in I(x)$ tem-se $g_i(a)+\mathrm{\nabla }{g}_i(a{)}^{\mathrm{\top }}(x^k-a)+o(\Vert x^k-a\Vert )\le 0$ $\mathrm{\nabla }{g}_i(a{)}^{\mathrm{\top }}\frac{(x^k-a)}{\Vert x^k-a\Vert }+\frac{o(\Vert x^k-a\Vert )}{\Vert x^k-a\Vert }\le 0$ Passando o limite quando $k\to \mathrm{\infty }$ tem-se $\mathrm{\nabla }{g}_i(a{)}^{\mathrm{\top }}\frac{d}{\Vert d\Vert }=\le 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 $\mathrm{\nabla }f(a{)}^{\mathrm{\top }}d\ge 0,\mathrm{\forall }d\in T(a,C)$.

Demonstração

Por Taylor tem-se $0\ge f(x^k)-f(a)=\mathrm{\nabla }f(a{)}^{\mathrm{\top }}(x^k-a)+o(\Vert x^k-a\Vert )$ $0\ge \mathrm{\nabla }f(a{)}^{\mathrm{\top }}\frac{(x^k-a)}{\Vert x^k-a\Vert }+\frac{o(\Vert x^k-a\Vert )}{\Vert x^k-a\Vert }$ Passando o limite quando $k\to \mathrm{\infty }$ obtem-se $0\ge \mathrm{\nabla }f(a{)}^{\mathrm{\top }}\frac{d}{\Vert d\Vert }$ Donde $\mathrm{\nabla }f(a{)}^{\mathrm{\top }}d\le 0\mathrm{\forall }d\in T(a,C)$.

Teorema KKT

Teorema (Condições de KKT)

Seja $C=\{x\in {ℝ}^n;g_i(x)\le 0\text{ e }{h}_j(x)=0\}$ e considere $a\in C$ um minimizador local do problema

$(P)\{\begin{array}{c}minf(x)\\ x\in C\end{array}$

Se $T(a,C{)}^{\ast }=L(a,C{)}^{\ast }$, então existem $u\in {ℝ}^p$ e $v\in {ℝ}^q$ tais que:

1. $-\mathrm{\nabla }f(a)=\sum _{i=1}^p{u}_i\mathrm{\nabla }{g}_i(a)+\sum _{j=1}^q{v}_j\mathrm{\nabla }{h}_j(a)$
2. $u_i\ge 0,\mathrm{\forall }i=1,\dots ,p$
3. $u_i{g}_i(a)=0,\mathrm{\forall }i=1,\dots ,p$.

Demonstração

Considere $a$ um minimizador local do problema (P). Então $(-\mathrm{\nabla }f(a){)}^{\mathrm{\top }}d\le 0,\mathrm{\forall }d\in T(a,C)$. Pela definição de cone polar isso significa que $-\mathrm{\nabla }f(a)\in T(a,C{)}^{\ast }$. Pela hipotése tem-se $-\mathrm{\nabla }f(a)\in L(a,C{)}^{\ast }$. Como $L(a,C)=G(a{)}^{\ast }$ obtem-se que $-\mathrm{\nabla }f(a)\in (G(a{)}^{\ast }{)}^{\ast }$. Como foi visto acima $G(a)$ é um cone convexo e fechado. Portanto usando o Lema de Farkas obtem-se que $-\mathrm{\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 $-\mathrm{\nabla }f(a)=\sum _{i\in I(a)}{\delta }_i\mathrm{\nabla }{g}_i(a)+\sum _{j=1}^q{\lambda }_j\mathrm{\nabla }{h}_j(a)$ com ${\delta }_i\ge 0\mathrm{\forall }i\in I(a)$. Como $\text{card}I(a)\le p$, define-se $v_j={\lambda }_j,\mathrm{\forall }j=1,\dots ,q$ e $u_i=\{\begin{array}{cc}{\delta }_i& \mathrm{\forall }i\in I(a)\\ 0& \mathrm{\forall }i\notin I(a)\end{array}$ Como $g_i(a)=0,\mathrm{\forall }i\in I(a)$ obtem-se $u_i{g}_i(a)=0\mathrm{\forall }i=1,\dots ,p$. Com isso fica provado o Teorema de KKT.