Function in mathematical optimization
数学的最適化 において 、 近似演算子は、 ヒルベルト空間 から への適切な [注 1] 下半連続 凸関数 に関連付けられた 演算子 であり 、次のように定義されます。 [1] f {\displaystyle f} X {\displaystyle {\mathcal {X}}} [ − ∞ , + ∞ ] {\displaystyle [-\infty ,+\infty ]}
prox f ( v ) = arg min x ∈ X ( f ( x ) + 1 2 ‖ x − v ‖ X 2 ) . {\displaystyle \operatorname {prox} _{f}(v)=\arg \min _{x\in {\mathcal {X}}}\left(f(x)+{\frac {1}{2}}\|x-v\|_{\mathcal {X}}^{2}\right).} このクラスの任意の関数について、上記の右辺の最小値は一意であるため、近似演算子は明確に定義されます。近似演算子は近似勾配法で使用され、 全変動ノイズ除去 などの 微分不可能 な最適化問題に関連する最適化アルゴリズムで頻繁に使用されます。
プロパティ 適切な下側半連続凸関数には、 最適 化に役立ついくつかの特性があります。 prox {\displaystyle {\text{prox}}} f {\displaystyle f}
の不動点は の 最小値です 。 prox f {\displaystyle {\text{prox}}_{f}} f {\displaystyle f} { x ∈ X | prox f x = x } = arg min f {\displaystyle \{x\in {\mathcal {X}}\ |\ {\text{prox}}_{f}x=x\}=\arg \min f} 最小化への大域収束は次のように定義される： ならば 、任意の初期点 に対して 、再帰は として 収束する。 が無限次元の 場合、この収束は弱収束となる可能性がある。 [2] arg min f ≠ ∅ {\displaystyle \arg \min f\neq \varnothing } x 0 ∈ X {\displaystyle x_{0}\in {\mathcal {X}}} ( ∀ n ∈ N ) x n + 1 = prox f x n {\displaystyle (\forall n\in \mathbb {N} )\quad x_{n+1}={\text{prox}}_{f}x_{n}} x n → x ∈ arg min f {\displaystyle x_{n}\to x\in \arg \min f} n → + ∞ {\displaystyle n\to +\infty } X {\displaystyle {\mathcal {X}}} 近似演算子は 射影演算子 の一般化として見ることができる。実際、空でない閉凸集合の 0- 特性関数 である 特定のケースでは 、 f {\displaystyle f} ∞ {\displaystyle \infty } ι C {\displaystyle \iota _{C}} C {\displaystyle C} prox ι C ( x ) = argmin y { 1 2 ‖ x − y ‖ 2 2 if y ∈ C + ∞ if y ∉ C = argmin y ∈ C 1 2 ‖ x − y ‖ 2 2 {\displaystyle {\begin{aligned}\operatorname {prox} _{\iota _{C}}(x)&=\operatorname {argmin} \limits _{y}{\begin{cases}{\frac {1}{2}}\left\|x-y\right\|_{2}^{2}&{\text{if }}y\in C\\+\infty &{\text{if }}y\notin C\end{cases}}\\&=\operatorname {argmin} \limits _{y\in C}{\frac {1}{2}}\left\|x-y\right\|_{2}^{2}\end{aligned}}} 近接演算子は実際には射影演算子の一般化であることを示しています。 関数が 確実に非拡張的で あるとは、次の場合です 。 ( ∀ ( x , y ) ∈ X 2 ) ‖ prox f x − prox f y ‖ 2 ≤ ⟨ x − y , prox f x − prox f y ⟩ {\displaystyle (\forall (x,y)\in {\mathcal {X}}^{2})\quad \|{\text{prox}}_{f}x-{\text{prox}}_{f}y\|^{2}\leq \langle x-y\ ,{\text{prox}}_{f}x-{\text{prox}}_{f}y\rangle } 関数の近似演算子は、 関数の モロー包絡線 の勾配と次の恒等式によって関連しています 。 M λ f {\displaystyle M_{\lambda f}} λ f {\displaystyle \lambda f} ∇ M λ f ( x ) = 1 λ ( x − p r o x λ f ( x ) ) {\displaystyle \nabla M_{\lambda f}(x)={\frac {1}{\lambda }}(x-\mathrm {prox} _{\lambda f}(x))} の近接演算子は を包含することで特徴付けられる 。ここで は の サブ 微分 であり、次のように与えられる。 f {\displaystyle f} p = prox f ( x ) ⇔ x − p ∈ ∂ f ( p ) {\displaystyle p=\operatorname {prox} _{f}(x)\Leftrightarrow x-p\in \partial f(p)} ∂ f {\displaystyle \partial f} f {\displaystyle f} ∂ f ( x ) = { u ∈ R N ∣ ∀ y ∈ R N , ( y − x ) T u + f ( x ) ≤ f ( y ) } {\displaystyle \partial f(x)=\{u\in \mathbb {R} ^{N}\mid \forall y\in \mathbb {R} ^{N},(y-x)^{\mathrm {T} }u+f(x)\leq f(y)\}} 特に、 が微分可能な場合、上記の式は に簡約されます 。 f {\displaystyle f} p = prox f ( x ) ⇔ x − p = ∇ f ( p ) {\displaystyle p=\operatorname {prox} _{f}(x)\Leftrightarrow x-p=\nabla f(p)}
注記 ^ ヒルベルト空間 上の （拡張）実数値 関数 f は 、 と全く等しくなく 、 その像にない 場合に、適切 であるという。 + ∞ {\displaystyle +\infty } − ∞ {\displaystyle -\infty }
参考文献 ^ Neal ParikhとStephen Boyd (2013). 「近似アルゴリズム」 (PDF) . 最適化の基礎と動向 . 1 (3): 123– 231. 2019年1月29日 閲覧 。 ^ Bauschke, Heinz H.; Combettes, Patrick L. (2017). ヒルベルト空間における凸解析と単調作用素理論 . CMS Books in Mathematics. ニューヨーク: Springer. doi :10.1007/978-3-319-48311-5. ISBN 978-3-319-48310-8 。
参照
外部リンク 
![{\displaystyle [-\infty ,+\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7a5a5ba47896e8fdd43cf7f311db27350f0f8ff)
