Otimização convexa - função diferenciável

Seja S um conjunto aberto não vazio em $ \ mathbb {R} ^ n $, então $ f: S \ rightarrow \ mathbb {R} $ é dito ser diferenciável em $ \ hat {x} \ in S $ se existe um vetor $ \ bigtriangledown f \ left (\ hat {x} \ right) $ chamado vetor gradiente e uma função $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ tal que

$ f \ left (x \ right) = f \ left (\ hat {x} \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x- \ hat {x} \ direita) + \ esquerda \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ in S $ onde

$ \ alpha \ left (\ hat {x}, x- \ hat {x} \ right) \ rightarrow 0 \ bigtriangledown f \ left (\ hat {x} \ right) = \ left [\ frac {\ partial f} {\ parcial x_1} \ frac {\ parcial f} {\ parcial x_2} ... \ frac {\ parcial f} {\ parcial x_n} \ direita] _ {x = \ hat {x}} ^ {T} $

Teorema

seja S um conjunto convexo aberto não vazio em $ \ mathbb {R} ^ n $ e seja $ f: S \ rightarrow \ mathbb {R} $ diferenciável em S. Então, f é convexo se e somente se para $ x_1, x_2 \ in S, \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $

Prova

Seja f uma função convexa. ou seja, para $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

$ f \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $

$ \ Rightarrow f \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] \ leq \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right ) + f \ left (x_2 \ right) $

$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 + \ lambda \ left (x_1-x_2 \ right) \ right) - f \ left (x_2 \ right) $

$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 \ right) + \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ lambda + $

$ \ left \ | \ lambda \ left (x_1-x_2 \ right) \ right \ | \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) -f \ left (x_2 \ right) \ right) $

onde $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $

Dividindo por $ \ lambda $ em ambos os lados, obtemos -

$ f \ left (x_1 \ right) -f \ left (x_2 \ right) \ geq \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) $

Conversar

Deixe para $ x_1, x_2 \ in S, \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $

Para mostrar que f é convexo.

Como S é convexo, $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

Como $ x_1, x_3 \ em S $, portanto

$ f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 -x_3 \ right) $

$ \ Rightarrow f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 - \ lambda x_1- \ left (1- \ lambda \ right) x_2 \ right) $

$ \ Rightarrow f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ left (1- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 - x_2 \ right) $

Uma vez que, $ x_2, x_3 \ em S $, portanto

$ f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) $

$ \ Rightarrow f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2- \ lambda x_1- \ left (1- \ lambda \ right) x_2 \ right) $

$ \ Rightarrow f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ left (- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ direita) $

Assim, combinando as equações acima, obtemos -

$ \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_3 \ right) \ right) + \ left (1- \ lambda \ right) \ left (f \ left (x_2 \ right) -f \ left (x_3 \ right) \ right) \ geq 0 $

$ \ Rightarrow f \ left (x_3 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $

Teorema

seja S um convexo aberto não vazio definido em $ \ mathbb {R} ^ n $ e seja $ f: S \ rightarrow \ mathbb {R} $ diferenciável em S, então f é convexo em S se e somente se para qualquer $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Prova

seja f uma função convexa, então usando o teorema anterior -

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $ e

$ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $

Adicionando as duas equações acima, obtemos -

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) + \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Conversar

Deixe para qualquer $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Para mostrar que f é convexo.

Seja $ x_1, x_2 \ em S $, portanto, pelo teorema do valor médio, $ \ frac {f \ left (x_1 \ right) -f \ left (x_2 \ right)} {x_1-x_2} = \ bigtriangledown f \ left ( x \ right), x \ in \ left (x_1-x_2 \ right) \ Rightarrow x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ porque S é um conjunto convexo.

$ \ Rightarrow f \ left (x_1 \ right) - f \ left (x_2 \ right) = \ left (\ bigtriangledown f \ left (x \ right) ^ T \ right) \ left (x_1-x_2 \ right) $

por $ x, x_1 $, nós sabemos -

$ \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x-x_1 \ right) \ geq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2- x_1 \ direita) \ geq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (1- \ lambda \ right) \ left (x_2-x_1 \ right) ) \ geq 0 $

$ \ Rightarrow \ bigtriangledown f \ left (x \ right) ^ T \ left (x_2-x_1 \ right) \ geq \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) $

Combinando as equações acima, obtemos -

$ \ Rightarrow \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $

Portanto, usando o último teorema, f é uma função convexa.

Função duas vezes diferenciável

Seja S um subconjunto não vazio de $ \ mathbb {R} ^ n $ e seja $ f: S \ rightarrow \ mathbb {R} $ então f é dito ser duas vezes diferenciável em $ \ bar {x} \ em S $ se existe um vetor $ \ bigtriangledown f \ left (\ bar {x} \ right), uma \: nXn $ matriz $ H \ left (x \ right) $ (chamada de matriz Hessiana) e uma função $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ de forma que $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ esquerda (\ bar {x} \ direita) + \ bigtriangledown f \ esquerda (\ bar {x} \ direita) ^ T \ esquerda (x- \ bar {x} \ direita) + \ frac {1} {2} \ esquerda (x- \ bar {x} \ direita) H \ esquerda (\ bar {x} \ direita) \ esquerda (x- \ bar {x} \ direita) $

onde $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow Oasx \ rightarrow \ bar {x} $