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

ConesEditar

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 descidaEditar

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 linearizadoEditar

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 tangenteEditar

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 tangenteEditar

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 tangenteEditar

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 KKTEditar

Teorema (Condições de KKT)

Seja   e considere   um minimizador local do problema

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

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.