解の値の下限と主双対解析
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/26 02:14 UTC 版)
「フランク・ウルフのアルゴリズム」の記事における「解の値の下限と主双対解析」の解説
f {\displaystyle f} は凸関数であるから、任意の二点 x , y ∈ D {\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}} に対し次の不等式が成立する。 f ( y ) ≥ f ( x ) + ( y − x ) T ∇ f ( x ) {\displaystyle f(\mathbf {y} )\geq f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )} この不等式は（未知の）最適解 x ∗ {\displaystyle \mathbf {x} ^{*}} f ( x ∗ ) ≥ f ( x ) + ( x ∗ − x ) T ∇ f ( x ) {\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )} ある点 x {\displaystyle \mathbf {x} } について、最適な下限は次のように与えられる。 f ( x ∗ ) ≥ f ( x ) + ( x ∗ − x ) T ∇ f ( x ) ≥ min y ∈ D { f ( x ) + ( y − x ) T ∇ f ( x ) } = f ( x ) − x T ∇ f ( x ) + min y ∈ D y T ∇ f ( x ) {\displaystyle {\begin{aligned}f(\mathbf {x} ^{*})&\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geq \min _{\mathbf {y} \in D}\left\{f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )\right\}\\&=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )\end{aligned}}} フランク・ウルフのアルゴリズムは、各反復において上式最終項の最適化問題を解くので、降下方向決定部分問題における解 s k {\displaystyle \mathbf {s} _{k}} を用いて解の下限 l k {\displaystyle l_{k}} を徐々に更新していくことができる。すなわち、 l 0 = − ∞ {\displaystyle l_{0}=-\infty } とおくと次のように更新すればよい。 l k := max ( l k − 1 , f ( x k ) + ( s k − x k ) T ∇ f ( x k ) ) {\displaystyle l_{k}:=\max(l_{k-1},f(\mathbf {x} _{k})+(\mathbf {s} _{k}-\mathbf {x} _{k})^{T}\nabla f(\mathbf {x} _{k}))} このように未知の最適値の下限を知ることができると、終止条件として用いることができるため実用上有用である。また、各反復においてつねに l k ≤ f ( x ∗ ) ≤ f ( x k ) {\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})} が成立するため、近似の精度を効率的にみつもることができる。 この双対ギャップ（英語版）、すなわち f ( x k ) {\displaystyle f(\mathbf {x} _{k})} と l k {\displaystyle l_{k}} との差も同一の収束速度で減少すること、つまり f ( x k ) − l k = O ( 1 / k ) {\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k)} が成立することが知られている。
※この「解の値の下限と主双対解析」の解説は、「フランク・ウルフのアルゴリズム」の解説の一部です。
「解の値の下限と主双対解析」を含む「フランク・ウルフのアルゴリズム」の記事については、「フランク・ウルフのアルゴリズム」の概要を参照ください。
- 解の値の下限と主双対解析のページへのリンク
