凸最適化-微分可能関数

Sを$ \ mathbb {R} ^ n $の空でない開集合とすると、$ f:S \ rightarrow \ mathbb {R} $は、$ \ hat {x} \ in S $で微分可能であると言われます。勾配ベクトルと呼ばれるベクトル$ \ bigtriangledown f \ left(\ hat {x} \ right)$と、次のような関数$ \ 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(\ hat {x}、x- \ hat {x} \ right)\ rightarrow 0 \ bigtriangledown f \ left(\ hat {x} \ right)= \ left [\ frac {\ partial f} {\ partial x_1} \ frac {\ partial f} {\ partial x_2} ... \ frac {\ partial f} {\ partial x_n} \ right] _ {x = \ hat {x}} ^ {T} $

定理

Sを$ \ mathbb {R} ^ n $の空でない開いた凸集合とし、$ f:S \ rightarrow \ mathbb {R} $をSで微分可能とします。次に、fは、$の場合に限り、凸です。 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を凸関数とします。つまり、$ x_1、x_2 \ in Sの場​​合、\ lambda \ in \ left(0、1 \ right)$

$ 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 \ 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(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(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)\ lambda + $

$ \左\ | \ 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(x_2、\ lambda \ left(x_1-x_2 \ right)\ right)\ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $

両側で$ \ lambda $で割ると、次のようになります。

$ f \ left(x_1 \ right)-f \ left(x_2 \ right)\ geq \ bigtriangledown f \ left(x_2 \ right)^ T \ left(x_1-x_2 \ 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は凸であるため、$ x_3 = \ lambda x_1 + \ left(1- \ lambda \ right)x_2 \ in S、\ lambda \ in \ left(0、1 \ right)$

$ x_1なので、x_3 \ in S $、したがって

$ f \ left(x_1 \ right)-f \ left(x_3 \ right)\ geq \ bigtriangledown f \ left(x_3 \ right)^ T \ left(x_1 -x_3 \ 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)$

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

以来、$ x_2、x_3 \ in S $したがって、

$ f \ left(x_2 \ right)-f \ left(x_3 \ right)\ geq \ bigtriangledown f \ left(x_3 \ right)^ T \ left(x_2-x_3 \ 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)$

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

$ \ Rightarrow f \ left(x_3 \ right)\ leq \ lambda f \ left(x_1 \ right)+ \ left(1- \ lambda \ right)f \ left(x_2 \ right)$

定理

Sを$ \ mathbb {R} ^ n $の空でない開いた凸集合とし、$ f:S \ rightarrow \ mathbb {R} $をSで微分可能とし、fがSで凸であるのは、任意の$ 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を凸関数とし、前の定理を使用します。

$ \ bigtriangledown f \ left(x_2 \ right)^ T \ left(x_1-x_2 \ right)\ leq f \ left(x_1 \ right)-f \ left(x_2 \ 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)$

上記の2つの方程式を追加すると、次のようになります。

$ \ 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(\ bigtriangledown f \ left(x_2 \ right)-\ bigtriangledown f \ left(x_1 \ right)\ right)^ T \ left(x_1-x_2 \ right)\ leq 0 $

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

コンバース

$ 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が凸であることを示すため。

$ x_1、x_2 \ in S $とします。したがって、平均値の定理により、$ \ 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は凸集合であるため、

$ \ 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、x_1 $の場合、私たちは知っています-

$ \ left(\ bigtriangledown f \ left(x \ right)-\ bigtriangledown f \ left(x_1 \ right)\ right)^ T \ left(x-x_1 \ right)\ geq 0 $

$ \ 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(\ 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 \ 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 \ 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は凸関数です。

2回微分可能関数

Sを$ \ mathbb {R} ^ n $の空でないサブセットとし、$ f:S \ rightarrow \ mathbb {R} $とすると、fは$ \ bar {x} \ inSで2回微分可能であると言われます。 $ベクトル$ \ bigtriangledown f \ left(\ bar {x} \ right)、\:nXn $行列$ H \ left(x \ right)$(ヘッセ行列と呼ばれる)および関数$ \ alphaが存在する場合: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $で、$ 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} \左(x- \ bar {x} \ right)H \ left(\ bar {x} \ right)\ left(x- \ bar {x} \ right)$

ここで、$ \ alpha \ left(\ bar {x}、x- \ bar {x} \ right)\ rightarrow Oasx \ rightarrow \ bar {x} $