# 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} _{+}$
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.

### Lema (Farkas)

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

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

## 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.

### 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.

### Lema

Para qualquer $x\in C$, $G(x)=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").

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

#### 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.

##### 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 :

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

## 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$.