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
Cones
editar- Definição
Um conjunto é um cone quando
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
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- Lema
Seja uma função diferenciável em . Então
- .
- 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- 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
- .
- 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
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 é,
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,
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- 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
editarDeterminar o cone tangente ao ponto do quadrado unitário com vértices , , e .
Resolução |
---|
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
editarO cone tangente definido anteriormente tem as seguintes propriedades:
- é fechado e
- Se então
- 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
Tomando o limite quando , obtem-se que e
Logo . Isso mostra que .
|
- Exercício
Verificar que:
- .
- Se e , então .
- 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 KKT
editar- Teorema (Condições de KKT)
Seja e considere um minimizador local do problema
- .
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
Como , define-se e Como obtem-se . Com isso fica provado o Teorema de KKT.
|