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

Cones

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.

Observações:

• $C^{*}$ é um cone: Se $d\in C^{*}$ 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^{*}$, 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.

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

O cone viável linearizado

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

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

Predefinição:Lema Predefinição:Demonstração

Predefinição:Definição

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

O cone tangente

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

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)$. Predefinição:Resolução

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

Predefinição:Lema Predefinição:Demonstração

Predefinição:Exercício Predefinição:Demonstração

Teorema KKT

Predefinição:AutoCat