Выпуклая оптимизация — дифференцируемая функция

Пусть S — непустое открытое множество в  mathbbRn$\ mathbb {R} ^ n$, тогда f:S rightarrow mathbbR$f: S \ rightarrow \ mathbb {R}$ называется дифференцируемым в  hatx inS$\ hat {x} \ in S$, если существует вектор  bigtriangledownf left( hatx right)$\ bigtriangledown f \ left (\ hat {x} \ right)$, называемый вектором градиента, и функция  alpha: mathbbRn rightarrow mathbbR$\ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R}$ такая, что

$ f \ left (x \ right) = f \ left (\ hat {x} \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x- \ hat {x} \ правый) + \ левый \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ in S $, где

 alpha left( hatx,x− hatx right) rightarrow0 bigtriangledownf left( hatx right)= left[ frac частичныйf частичныйx1 frac частичныйf частичныйx2... frac частичныйf частичныйxn right]Tx= hatx$\ alpha \ left (\ hat {x}, x- \ hat {x} \ right) \ rightarrow 0 \ bigtriangledown f \ left (\ hat {x} \ right) = \ left [\ frac {\ частичный f} {\ частичный x_1} \ frac {\ частичный f} {\ частичный x_2} ... \ frac {\ частичный f} {\ частичный x_n} \ right] _ {x = \ hat {x}} ^ {T}$

теорема

пусть S — непустое открытое выпуклое множество в  mathbbRn$\ mathbb {R} ^ n$, и пусть f:S rightarrow mathbbR$f: S \ rightarrow \ mathbb {R}$ дифференцируемо на S. Тогда f выпукло тогда и только тогда, когда для x1,x2 inS, bigtriangledownf left(x2 right)T left(x1−x2 right) leqf left(x1 right)−f left(x2 right)$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)$

доказательство

Пусть f — выпуклая функция. то есть для x1,x2 inS, lambda in left(0,1 right)$x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right)$

f left[ lambdax1+ left(1− lambda right)x2 right] leq lambdaf left(x1 right)+ left(1− lambda right)f left(x2 право)$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 \ право)$

 Rightarrowf left[ lambdax1+ left(1− lambda right)x2 right] leq lambda left(f left(x1 right)−f left(x2 right) right)+f left(x2 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(x1 right)−f left(x2 right) right) geqf left(x2+ lambda left(x1−x2 right) right)−f left(x2 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(x1 right)−f left(x2 right) right) geqf left(x2 right)+ bigtriangledownf left(x2 right)T left(x1−x2 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) \ лямбда +$

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

где  alpha left(x2, lambda left(x1−x2 right) right) rightarrow0$\ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0$ как  lambda rightarrow0$\ lambda \ rightarrow 0$

Разделив  lambda$\ lambda$ на обе стороны, получим —

f left(x1 right)−f left(x2 right) geq bigtriangledownf left(x2 right)T left(x1−x2 right)$f \ left (x_1 \ right) -f \ left (x_2 \ right) \ geq \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right)$

обратный

Пусть для x1,x2 inS, bigtriangledownf left(x2 right)T left(x1−x2 right) leqf left(x1 right)−f left(x2 right)$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)$

Чтобы показать, что f выпуклая.

Поскольку S выпуклый, x3= lambdax1+ left(1− lambda right)x2 inS, lambda in left(0,1 right)$x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right)$

Так как x1,x3 inS$x_1, x_3 \ in S$, следовательно,

f left(x1 right)−f left(x3 right) geq bigtriangledownf left(x3 right)T left(x1−x3 right)$f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 -x_3 \ right)$

 Rightarrowf left(x1 right)−f left(x3 right) geq bigtriangledownf left(x3 right)T left(x1− lambdax1− left(1− lambda) right)x2 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)$

 Rightarrowf left(x1 right)−f left(x3 right) geq left(1− lambda right) bigtriangledownf left(x3 right)T left(x1−x2 право)$\ 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 \ право)$

Так как, x2,x3 inS$x_2, x_3 \ in S$, следовательно,

f left(x2 right)−f left(x3 right) geq bigtriangledownf left(x3 right)T left(x2−x3 right)$f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right)$

 Rightarrowf left(x2 right)−f left(x3 right) geq bigtriangledownf left(x3 right)T left(x2− lambdax1− left(1− lambda) right)x2 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)$

 Rightarrowf left(x2 right)−f left(x3 right) geq left(− lambda right) bigtriangledownf left(x3 right)T left(x1−x2 верно)$\ 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 \ верно)$

Таким образом, объединяя приведенные выше уравнения, получаем —

 lambda left(f left(x1 right)−f left(x3 right) right)+ left(1− lambda right) left(f left(x2 right)−f left(x3 right) right) geq0$\ 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$

 Rightarrowf left(x3 right) leq lambdaf left(x1 right)+ left(1− lambda right)f left(x2 right)$\ Rightarrow f \ left (x_3 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right)$

теорема

пусть S — непустое открытое выпуклое множество в  mathbbRn$\ mathbb {R} ^ n$, и пусть f:S rightarrow mathbbR$f: S \ rightarrow \ mathbb {R}$ дифференцируемо на S, тогда f выпукло на S тогда и только тогда, когда для любой x1,x2 inS, left( bigtriangledownf left(x2 right)− bigtriangledownf left(x1 right) right)T left(x2−x1 right) geq0$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$

доказательство

пусть f — выпуклая функция, тогда используя предыдущую теорему —

 bigtriangledownf left(x2 right)T left(x1−x2 right) leqf left(x1 right)−f left(x2 right)$\ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right)$ и

 bigtriangledownf left(x1 right)T left(x2−x1 right) leqf left(x2 right)−f left(x1 right)$\ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right)$

Сложив два приведенных выше уравнения, получим —

 bigtriangledownf left(x2 right)T left(x1−x2 right)+ bigtriangledownf left(x1 right)T left(x2−x1 right) leq0$\ 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( bigtriangledownf left(x2 right)− bigtriangledownf left(x1 right) right)T left(x1−x2 right) leq0$\ 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( bigtriangledownf left(x2 right)− bigtriangledownf left(x1 right) right)T left(x2−x1 right) geq0$\ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0$

обратный

Пусть для любого x1,x2 inS, left( bigtriangledownf left(x2 right)− bigtriangledownf left(x1 right) right)T left(x2−x1 right) geq0$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$

Чтобы показать, что f выпуклая.

Пусть x1,x2 inS$x_1, x_2 \ in S$, то есть по теореме о среднем значении  fracf left(x1 right)−f left(x2 right)x1−x2= bigtriangledownf left(x right),x in left(x1−x2 right) Rightarrowx= lambdax1+ left(1− lambda right)x2$\ 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$, поскольку S — выпуклое множество.

 Rightarrowf left(x1 right)−f left(x2 right)= left( bigtriangledownf left(x right)T right) left(x1−x2 right)$\ 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)$

за x,x1$x, x_1$ мы знаем —

 left( bigtriangledownf left(x right)− bigtriangledownf left(x1 right) right)T left(x−x1 right) geq0$\ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x-x_1 \ right) \ geq 0$

 Rightarrow left( bigtriangledownf left(x right)− bigtriangledownf left(x1 right) right)T left( lambdax1+ left(1− lambda right)x2−x1 right) geq0$\ 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 \ right) \ geq 0$

 Rightarrow left( bigtriangledownf left(x right)− bigtriangledownf left(x1 right) right)T left(1− lambda right) left(x2−x1 right)) geq0$\ 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 bigtriangledownf left(x right)T left(x2−x1 right) geq bigtriangledownf left(x1 right)T left(x2−x1 right)$\ 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)$

Комбинируя вышеприведенные уравнения, получим —

 Rightarrow bigtriangledownf left(x1 right)T left(x2−x1 right) leqf left(x2 right)−f left(x1 right)$\ 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)$

Следовательно, используя последнюю теорему, f является выпуклой функцией.

Дважды дифференцируемая функция

Пусть S — непустое подмножество в  mathbbRn$\ mathbb {R} ^ n$, и пусть f:S rightarrow mathbbR$f: S \ rightarrow \ mathbb {R}$, тогда f называется дважды дифференцируемым в  barx inS$\ bar {x} \ in S$, если существует вектор  bigtriangledownf left( barx right),матрицаnXn$\ bigtriangledown f \ left (\ bar {x} \ right), матрица \: nXn$ H left(x right)$H \ left (x \ right)$ (называемая гессианской матрицей) и функция  alpha: mathbbRn rightarrow mathbbR$\ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R}$ такой, что f left(x right)=f left( barx+x− barx right)=f left( barx right)+ bigtriangledownf left( barx right)T left(x− barx right)+ frac12 left(x− barx right)H left( barx right) left(x− barx right)$f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ left (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) + \ frac {1} {2} \ left (x- \ bar {x} \ right) H \ left (\ bar {x} \ right) \ left (x- \ bar {x} \ right)$

где  alpha left( barx,x− barx right) rightarrowOasx rightarrow barx$\ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow Oasx \ rightarrow \ bar {x}$