微分可能な準凸関数

定理

Sを$ \ mathbb {R} ^ n $の空でない凸集合とし、$ f：S \ rightarrow \ mathbb {R} $をSで微分可能とすると、fは、$ 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_2-x_1 \ right） \ leq 0 $

証明

fを準凸関数とします。

$ 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 \ left \ | x_1-x_2 \ right \ | \ alpha \ left（x_2、\ lambda \ left（x_1-x_2 \ right）\ right）$

$ \ Rightarrow 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 \ right）^ T \ left（x_1-x_2 \ right）$

$ + \ lambda \ left \ | x_1-x_2 \ right \ | \ alpha \ left（x2、\ lambda \ left（x_1-x_2 \ right）\ right）$

ただし、fは準凸であるため、$ 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 \ right \ | \ 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 \ right）\ leq 0 $

fが準凸であることを示すには、$ 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にあるとします。 \ left（0、1 \ right）$

$ 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を定義します\ left（0,1 \ right）\ right \} $

したがって、$ 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_0 \ in U $を見つけることができます。 ）$は$ 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）$$

$$ \ Rightarrow f \ left（x_3 \ right）= f \ left（x_0 \ right）+ \ bigtriangledown f \ left（\ hat {x} \ right）^ T \ left（x_3-x_0 \ right）$$

$$ \ Rightarrow 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 \ left（x_3 \ right）= f \ left（x_0 \ right）\ leq f \ left（x_2 \ right）$$

$$ \ Rightarrow f \ left（x_3 \ right）\ leq f \ left（x_2 \ right）$$

したがって、それは矛盾です。

例

Step 1 − $ f \ left（x \ right）= 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）$は準凸です。

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 \ left（\ hat {x_2} \ right）$

したがって、$ \ bigtriangledown f \ left（\ hat {x_2} \ right）^ T \ left（\ hat {x_1}-\ hat {x_2} \ right）= \ left（3、0 \ right）^ T \ left （1、-2 \ right）= 3> 0 $

したがって、$ f \ left（x \ right）$は準凸ではありません。