Optimización convexa: función diferenciable

Sea S un conjunto abierto no vacío en $ \ mathbb {R} ^ n $, entonces se dice que $ f: S \ rightarrow \ mathbb {R} $ es diferenciable en $ \ hat {x} \ en S $ si existe un vector $ \ bigtriangledown f \ left (\ hat {x} \ right) $ llamado vector degradado y una función $ \ 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} \ derecha) + \ izquierda \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ in S $ donde

$ \ 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} \ derecha] _ {x = \ hat {x}} ^ {T} $

Teorema

sea ​​S un conjunto convexo abierto no vacío en $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $ diferenciable en S. Entonces, f es convexa si y solo si 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) $

Prueba

Sea f una función convexa. es decir, 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) $

donde $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ como $ \ lambda \ rightarrow 0 $

Dividiendo por $ \ lambda $ en ambos lados, obtenemos -

$ 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

Sea 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) PS

Demostrar que f es convexa.

Como S es 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 \ en S $, por lo tanto

$ 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) $

Dado que, $ x_2, x_3 \ in S $ por lo tanto

$ 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 \ derecha) $

Por lo tanto, combinando las ecuaciones anteriores, obtenemos:

$ \ 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

sea ​​S un conjunto convexo abierto no vacío en $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $ diferenciable en S, entonces f es convexa en S si y solo si para cualquier $ 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 PS

Prueba

sea ​​f una función convexa, luego usando el 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) $ y

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

Sumando las dos ecuaciones anteriores, obtenemos:

$ \ 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

Sea para cualquier $ x_1, x_2 \ en S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Demostrar que f es convexa.

Sea $ x_1, x_2 \ en S $, por lo tanto, por el teorema del valor medio, $ \ 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 es un 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 $, 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 \ derecha) \ 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 las ecuaciones anteriores, obtenemos:

$ \ 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) $

Por tanto, utilizando el último teorema, f es una función convexa.

Función dos veces diferenciable

Sea S un subconjunto no vacío de $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $ entonces se dice que f es dos veces diferenciable en $ \ bar {x} \ en S $ si existe un vector $ \ bigtriangledown f \ left (\ bar {x} \ right), una \: nXn $ matriz $ H \ left (x \ right) $ (llamada matriz de Hesse) y una función $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ tal que $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ izquierda (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) + \ frac {1} {2} \ izquierda (x- \ bar {x} \ derecha) H \ izquierda (\ bar {x} \ derecha) \ izquierda (x- \ bar {x} \ derecha) $

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