Достаточные и необходимые условия для Global Optima

Пусть f — дважды дифференцируемая функция. Если $\ bar {x}$ является локальным минимумом, то $\ bigtriangledown f \ left (\ bar {x} \ right) = 0$ и гессенская матрица $H \ left (\ bar {x} \ right)$ является положительным полуопределенным.

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

Пусть $d \ in \ mathbb {R} ^ n$. Поскольку f дважды дифференцируема в $\ bar {x}$.

Следовательно,

$f \ left (\ bar {x} + \ lambda d \ right) = f \ left (\ bar {x} \ right) + \ lambda \ bigtriangledown f \ left (\ bar {x} \ right) ^ T d + \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d + \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d +$

$ \ lambda ^ 2 \ left \ | d \ right \ | ^ 2 \ beta \ left (\ bar {x}, \ lambda d \ right) $

Но $\ bigtriangledown f \ left (\ bar {x} \ right) = 0$ и $\ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0$ как $\ lambda \ rightarrow 0$

$\ Rightarrow f \ left (\ bar {x} + \ lambda d \ right) -f \ left (\ bar {x} \ right) = \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d$

Поскольку $\ bar {x}$ является локальным минимумом, существует такое $\ delta> 0$, что $f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right) ), \ forall \ lambda \ in \ left (0, \ delta \ right)$

теорема

Пусть $f: S \ rightarrow \ mathbb {R} ^ n$, где $S \ subset \ mathbb {R} ^ n$, можно дважды дифференцировать по S. Если $\ bigtriangledown f \ left (x \ right) = 0$ и $H \ left (\ bar {x} \ right)$ положительно полуопределен, для всех $x \ in S$ тогда $\ bar {x}$ является глобальным оптимальным решением.

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

Поскольку $H \ left (\ bar {x} \ right)$ является положительно-полуопределенным, f является выпуклой функцией над S. Поскольку f дифференцируема и выпукла в $\ bar {x}$

$\ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ leq f \ left (x \ right) -f \ left (\ bar {x} \ right), \ forall x \ in S$

Так как $\ bigtriangledown f \ left (\ bar {x} \ right) = 0, f \ left (x \ right) \ geq f \ left (\ bar {x} \ right)$

Следовательно, $\ bar {x}$ является глобальной оптимой.

теорема

Предположим, что $\ bar {x} \ in S$ является локальным оптимальным решением задачи $f: S \ rightarrow \ mathbb {R}$, где S — непустое подмножество в $\ mathbb {R} ^ n$ и S выпуклый. minf left(x right)$min \: f \ left (x \ right)$, где $x \ in S$.

Затем:

• $\ bar {x}$ — глобальное оптимальное решение.

• Если либо $\ bar {x}$ — строго локальные минимумы, либо f — строго выпуклая функция, то $\ bar {x}$ — единственное глобальное оптимальное решение, а также сильные локальные минимумы.

$\ bar {x}$ — глобальное оптимальное решение.

Если либо $\ bar {x}$ — строго локальные минимумы, либо f — строго выпуклая функция, то $\ bar {x}$ — единственное глобальное оптимальное решение, а также сильные локальные минимумы.

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

Пусть $\ bar {x}$ — другое глобальное оптимальное решение задачи, такое что $x \ neq \ bar {x}$ и $f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ right)$

Поскольку $\ hat {x}, \ bar {x} \ in S$ и S выпуклый, то $\ frac {\ hat {x} + \ bar {x}} {2} \ in S$ и f строго выпукло.

$\ Rightarrow f \ left (\ frac {\ hat {x} + \ bar {x}} {2} \ right) <\ frac {1} {2} f \ left (\ bar {x} \ right) + \ frac {1} {2} f \ left (\ hat {x} \ right) = f \ left (\ hat {x} \ right)$

Это противоречие.

Следовательно, $\ hat {x}$ — единственное глобальное оптимальное решение.

следствие

Пусть $f: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R}$ — выпуклая дифференцируемая функция, где $\ phi \ neq S \ subset \ mathbb {R} ^ n$ — выпуклое множество. Рассмотрим задачу $min f \ left (x \ right), x \ in S$, тогда $\ bar {x}$ является оптимальным решением, если $\ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S.$

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

Пусть $\ bar {x}$ является оптимальным решением, т. Е. $F \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in S$

$\ Rightarrow f \ left (x \ right) = f \ left (\ bar {x} \ right) \ geq 0$

$ f \ left (x \ right) = f \ left (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ правый) + \ левый \ | x- \ bar {x} \ right \ | \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) $

где $\ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow 0$ как $x \ rightarrow \ bar {x}$

$\ Rightarrow f \ left (x \ right) -f \ left (\ bar {x} \ right) = \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x) } \ right) \ geq 0$

следствие

Пусть f — дифференцируемая выпуклая функция в $\ bar {x}$, тогда $\ bar {x}$ — глобальный минимум, если $\ bigtriangledown f \ left (\ bar {x} \ right) = 0$

$f \ left (x \ right) = \ left (x ^ 2-1 \ right) ^ {3}, x \ in \ mathbb {R}$.

$\ bigtriangledown f \ left (x \ right) = 0 \ Rightarrow x = -1,0,1$.

$\ bigtriangledown ^ 2f \ left (\ pm 1 \ right) = 0, \ bigtriangledown ^ 2 f \ left (0 \ right) = 6> 0$.

$f \ left (\ pm 1 \ right) = 0, f \ left (0 \ right) = - 1$

Следовательно, $f \ left (x \ right) \ geq -1 = f \ left (0 \ right) \ Rightarrow f \ left (0 \ right) \ leq f \ left (x \ right) \ forall x \ in \ mathbb {R}$

$f \ left (x \ right) = x \ log x$, определенный в $S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \}$.

${f} 'x = 1 + \ log x$

${Е} '' х = \ гидроразрыва {1} {х}> 0$

Таким образом, эта функция является строго выпуклой.

$f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R}$ строго выпуклый.