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

1. $\nabla f(x)^{\top }d\leq 0,\ \forall d\in D(x)$.
2. $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:

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

1. $T(a,C)\subset L(a,C)$.
2. 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:

1. $-\nabla f(a)=\sum _{i=1}^{p}u_{i}\nabla g_{i}(a)+\sum _{j=1}^{q}v_{j}\nabla h_{j}(a)$
2. $u_{i}\geq 0,\ \forall i=1,\dots ,p$
3. $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.