Saltar para o conteúdo

Otimização/KKT

Origem: Wikilivros, livros abertos por um mundo aberto.


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

Definição

Um conjunto é um cone quando

Exemplo de um cone no .

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 , o cone polar de é o conjunto definido por

.

Observações:

  • é um cone: Se tem-se que . Logo, para qualquer , vale . Disto segue que , mostrando que é um cone.
  • Sempre se tem que (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 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 um cone convexo fechado, então .

Demonstração
Seja e . Sabendo que a projeção de um ponto sobre um conjunto convexo é única, será mostrado que e então ficará provada a inclusão . Disto seguirá a igualdade entre os dois conjuntos, já que é sempre um subconjunto de .

Pelo teorema da projeção (ver Izmailov & Solodov (2007)), tem-se que . Usando o fato de que é cone, segue que e e substituindo isto na equação acima obtem-se

e .

Dessas desigualdades, conclui-se que .

De , tem-se que .

Usando a definição de cone polar, isso implica que .

Uma vez que , significa que .

Desses fatos acima se conclui que

Isso mostra que .


Definição

Dado , se diz que é uma direção viável em , com respeito a , quando existe tal que

.
O conjunto de todas as direções viáveis em , com respeito ao conjunto , será denotado por .

Esse conjunto é o cone das direções viáveis em , com respeito a .

Definição

Uma direção é uma direção de descida da função em , se existe tal que

.
O conjunto das direções de descida será denotado por .

Caracterização das direções de descida

[editar | editar código-fonte]
Lema

Seja uma função diferenciável em . Então

  1. .
  2. satisfaz .


Demonstração
1) Seja . Então, tem-se .

Usando a série de Taylor, tem-se

Sendo ,

.

Passando o limite com tem-se que .

2) Novamente aplicando Taylor em tem-se

.

Como , tem-se

.

Pela hipótese , com isto

.

Pelo teorema da conservação do sinal, existe tal que .

Portanto,

.

Conclui-se então que .

O cone viável linearizado

[editar | editar código-fonte]
Definição

Dado , a desigualdade é uma restrição ativa em se .

Observações
  • O conjunto formado pelos índices das restrições de desigualdade ativas é denotado por . Assim,
Definição

Dado um ponto e o conjunto , se define o cone viável linearizado de a partir de como

.

é um cone não-vazio convexo e fechado pois, . E se , tem-se

e
.

Portanto mostrando que é convexo.

Para mostrar que é fechado, pode-se pegar uma sequência convergente e mostrar que o ponto de acumulação dela esta em .

Tem-se que .

Passando o limite com , obtem-se

e
.

Isso mostra que é fechado.


Lema  (Caratheodory)

Sejam . Seja com e escalares tais que e

.
Então existem subconjuntos e escalares com e tais que
e os vetores são linearmente independentes.

Demonstração
Sem perda de generalidade, suponha que e . Considere que sejam linearmente dependentes.

Portanto existem escalares com e com não todos nulos tais que

Multiplicando a igualdade acima por e subtraindo de

tem-se

Para certamente nenhum dos coeficientes acima se anula.

Seja o de menor módulo que anula pelo menos um dos coeficientes ou . Então

Assim, se escreve como combinação linear de no máximo vetores já que .

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


Definição

Dado um ponto , se define o cone por

.

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

Lema

Para qualquer , é um cone convexo e fechado.

Demonstração
Primeiro será mostrado que é de fato um cone. Seja e . Então tem-se
.

Como tem-se que .

Agora, será provado que é convexo. Para isso seja , isto é,

e
e .

Logo tem-se,

.

Como visto que e . Com isso concluímos que mostrando que é convexo.

Para mostrar que é fechado, toma-se uma sequência convergente em e se mostra que o ponto de acumulação dela pertence a .

Para isso seja com . Será mostrado que .

Escrevendo em forma matricial tem-se .

Pelo Lema de Caratheodory podemos assumir que tem colunas linearmente independentes, e portanto é não singular.

Uma vez que , existem com tais que .

Uma vez que é não singular, .

Passando o limite obtem-se,

com .

Isso mostra que .

Agora passando o limite em obtém-se , mostrando que .


Lema

Para qualquer , .

Demonstração
Como e são convexos e fechados, tem-se que e . Será mostrado então que .

Seja . Assim, dado tem-se

Mas e e .

Conclui-se então que . Como é arbitrário, .

Agora a volta, seja , isto é, .

Em particular, uma vez que e , tem-se que .

Além disso, uma vez que , tem-se que .

Logo .

O cone tangente

[editar | editar código-fonte]
Definição

Um vetor é chamado direção tangente em a partir de quando ou ou tal que

e .

Observações
  • O conjunto de todas as direções tangentes no ponto , é denominado cone tangente, e denotado por .
  • Se , então também pode ser descrito como
Exercício

Verifique que é 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

[editar | editar código-fonte]

Determinar o cone tangente ao ponto do quadrado unitário com vértices , , e .

Resolução
Cone tangente a um quadrado unitário com vértice na origem.

Dado qualquer ponto do 2º quadrante (formado pelos pontos tais que e ), pode-se definir:

Com essas escolhas, tem-se:

Logo, .


Propriedades do cone tangente

[editar | editar código-fonte]
Wikipedia
Wikipedia
A Wikipédia tem mais sobre este assunto:
Cone tangente

O cone tangente definido anteriormente tem as seguintes propriedades:

  1. é fechado e
  2. Se então
  3. Se é uma vizinhança de , então
Observação

A terceira propriedade indica que o cone tangente só depende do que ocorre bem perto de , no conjunto .


Lema

Para qualquer , é fechado.

Demonstração
Seja com . Será mostrado que .

Caso , . Então, suponha-se que .

Neste caso, sem perda de generalidade pode-se considerar que , pois .

Fixando tem-se que . Portanto, existe tal que e quando .

Assim para existe tal que para , tal que e .

Em particular, tomando tem-se

e .

Tomando o limite quando , obtem-se que e

.

Logo .

Isso mostra que .



Exercício

Verificar que:

  1. .
  2. Se e , então .

Demonstração
1) Seja , . Logo tal que , e .

Usando Taylor em torno de tem-se

.

Já que , então logo pode-se dividir e obtem-se

.

Passando o limite quando , tem-se .

Novamente usando Taylor em torno de para tem-se

Passando o limite quando tem-se .

Donde se conclui que .

2)

Este módulo tem a seguinte tarefa pendente: Colocar figura
Lema

Se é um mínimo local do problema (P), então .

Demonstração
Por Taylor tem-se

Passando o limite quando obtem-se

Donde .


Teorema (Condições de KKT)

Seja e considere um minimizador local do problema

Se , então existem e tais que:
  1. .

Demonstração
Considere um minimizador local do problema (P). Então . Pela definição de cone polar isso significa que .

Pela hipotése tem-se . Como obtem-se que .

Como foi visto acima é um cone convexo e fechado. Portanto usando o Lema de Farkas obtem-se que .

Pela definição de , existem escalares com e com tais que

com .

Como , define-se e

Como obtem-se .

Com isso fica provado o Teorema de KKT.