미분 가능한 Quasiconvex 함수

정리

S를 $ \ mathbb {R} ^ n $ 및 $ f : S \ rightarrow \ mathbb {R} $에서 S에서 미분 할 수있는 비어 있지 않은 볼록 집합이라고 가정하면 f는 $ x_1, x_2의 경우에만 quasiconvex입니다. \ in S $ 및 $ f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $, $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_2-x_1 \ right) \ leq 0 $

증명

f를 quasiconvex 함수라고합니다.

$ x_1, x_2 \ in S $에서 $ f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $

$ x_2에서 f의 미분, \ lambda \ in \ left (0, 1 \ right) $

$ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) = f \ left (x_2 + \ lambda \ left (x_1-x_2 \ right) \ right) = f \ left (x_2 \ right ) + \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) $

$ + \ lambda \ 왼쪽 \ | x_1-x_2 \ 오른쪽 \ | \ alpha \ left (x_2, \ lambda \ left (x_1-x_2 \ right) \ right) $

$ \ 오른쪽 화살표 f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) -f \ left (x_2 \ right) -f \ left (x_2 \ right) = \ bigtriangledown f \ left (x_2 \ 오른쪽) ^ T \ 왼쪽 (x_1-x_2 \ 오른쪽) $

$ + \ lambda \ 왼쪽 \ | x_1-x_2 \ 오른쪽 \ | \ alpha \ left (x2, \ lambda \ left (x_1-x_2 \ right) \ right) $

그러나 f는 quasiconvex이므로 $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right) $

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) + \ lambda \ left \ | x_1-x_2 \ 오른쪽 \ | \ alpha \ left (x_2, \ lambda \ left (x_1, x_2 \ right) \ right) \ leq 0 $

하지만 $ \ alpha \ left (x_2, \ lambda \ left (x_1, x_2 \ right) \ right) \ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $

따라서 $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $

반대

$ x_1, x_2 \ in S $ 및 $ f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $, $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1, x_2 \ 오른쪽) \ leq 0 $

f가 quasiconvex임을 나타 내기 위해, 즉 $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right) $

Proof by contradiction

$ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $가 있다고 가정합니다. $ f \ left (x_2 \ right) <f \ left (x_3 \ right) $ 일부 $ \ lambda \ in \ 왼쪽 (0, 1 \ 오른쪽) $

$ x_2 $ 및 $ x_3의 경우, \ ​​bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) \ leq 0 $

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

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

$ x_1 $ 및 $ x_3의 경우, \ ​​bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_3 \ right) \ leq 0 $

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

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

따라서 위의 방정식에서 $ \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) = 0 $

$ U = \ left \ {x : f \ left (x \ right) \ leq f \ left (x_2 \ right), x = \ mu x_2 + \ left (1- \ mu \ right) x_3, \ mu \ in 정의 \ 왼쪽 (0,1 \ 오른쪽) \ 오른쪽 \} $

따라서 $ x_0 \ in U $에서 $ x_0 = \ mu_0 x_2 = \ mu x_2 + \ left (1- \ mu \ right) x_3 $ for some $ \ mu _0 \ in \ left (0,1 \ right ) $는 $ x_3 $ 및 $ \ hat {x} \ in \ left (x_0, x_1 \ right) $에 가장 가까운 평균값 정리로,

$$ \ frac {f \ left (x_3 \ right) -f \ left (x_0 \ right)} {x_3-x_0} = \ bigtriangledown f \ left (\ hat {x} \ right) $$

$$ \ 오른쪽 화살표 f \ left (x_3 \ right) = f \ left (x_0 \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x_3-x_0 \ right) $$

$$ \ 오른쪽 화살표 f \ left (x_3 \ right) = f \ left (x_0 \ right) + \ mu_0 \ lambda f \ left (\ hat {x} \ right) ^ T \ left (x_1-x_2 \ right) $ $

$ x_0 $은 $ x_1 $와 $ x_2 $와 $ f \ left (x_2 \ right) <f \ left (\ hat {x} \ right) $의 조합이므로

시작 절차를 반복하면 $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x_1-x_2 \ right) = 0 $

따라서 위의 방정식을 결합하면 다음을 얻을 수 있습니다.

$$ f \ 왼쪽 (x_3 \ 오른쪽) = f \ 왼쪽 (x_0 \ 오른쪽) \ leq f \ 왼쪽 (x_2 \ 오른쪽) $$

$$ \ 오른쪽 화살표 f \ 왼쪽 (x_3 \ 오른쪽) \ leq f \ 왼쪽 (x_2 \ 오른쪽) $$

따라서 그것은 모순입니다.

예

Step 1 − $ f \ 왼쪽 (x \ 오른쪽) = X ^ 3 $

$ Let f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $

$ \ Rightarrow x_ {1} ^ {3} \ leq x_ {2} ^ {3} \ Rightarrow x_1 \ leq x_2 $

$ \ bigtriangledown f \ left (x_2 \ right) \ left (x_1-x_2 \ right) = 3x_ {2} ^ {2} \ left (x_1-x_2 \ right) \ leq 0 $

따라서 $ f \ left (x \ right) $는 quasiconvex입니다.

Step 2 − $ f \ left (x \ right) = x_ {1} ^ {3} + x_ {2} ^ {3} $

$ \ hat {x_1} = \ left (2, -2 \ right) $ 및 $ \ hat {x_2} = \ left (1, 0 \ right) $

따라서 $ f \ left (\ hat {x_1} \ right) = 0, f \ left (\ hat {x_2} \ right) = 1 \ Rightarrow f \ left (\ hat {x_1} \ right) \ setminus <f \ 왼쪽 (\ hat {x_2} \ 오른쪽) $

따라서 $ \ bigtriangledown f \ left (\ hat {x_2} \ right) ^ T \ left (\ hat {x_1}-\ hat {x_2} \ right) = \ left (3, 0 \ right) ^ T \ left (1, -2 \ 오른쪽) = 3> 0 $

따라서 $ f \ left (x \ right) $는 quasiconvex가 아닙니다.