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 .
|
Esse conjunto
é o cone das direções viáveis em
, com respeito a
.
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 .
|
- 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 .
|
- 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.
|
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, .
|
O 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
e .
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
.
- Teorema (Condições de KKT)
Seja
e considere
um minimizador local do problema

Se

, então existem

e

tais que:


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