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 \ 왼쪽 \ | d \ 오른쪽 \ | ^ 2 \ 베타 \ 왼쪽 (\ bar {x}, \ lambda d \ 오른쪽) $
하지만 $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ 및 $ \ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0 $ as $ \ 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} $는 로컬 최소값이므로 $ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right와 같은 $ \ delta> 0 $가 있습니다. ), \ 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} \ 오른쪽), \ 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는 볼록합니다. $ min \ : f \ left (x \ right) $ 여기서 $ x \ in S $.
그때:
$ \ bar {x} $는 글로벌 최적 솔루션입니다.
$ \ bar {x} $가 엄격 로컬 최소값이거나 f가 엄격 볼록 함수 인 경우 $ \ bar {x} $는 고유 한 글로벌 최적 솔루션이며 강력한 로컬 최소값이기도합니다.
증명
$ \ bar {x} $를 $ x \ neq \ bar {x} $ 및 $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ 오른쪽) $
$ \ 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 $ 문제를 고려하면 $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T 인 경우 $ \ bar {x} $가 최적의 솔루션입니다. \ 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 $
$ \ 오른쪽 화살표 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 $ as $ x \ rightarrow \ bar {x} $
$ \ 오른쪽 화살표 f \ left (x \ right) -f \ left (\ bar {x} \ right) = \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x } \ 오른쪽) \ 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 $
$ {f} ''x = \ frac {1} {x}> 0 $
따라서이 함수는 엄격하게 볼록합니다.
$ f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R} $는 완전 볼록입니다.