不動点近似法の研究紹介

文書の過去の版を表示しています。

ここでは、ノルム $\| \cdot \|$ と内積 $\langle \cdot, \cdot \rangle$ をもつHilbert空間 $H$ 上の不動点問題について考察しましょう。 $\begin{align*} \text{Find } x \in \mathrm{Fix}\left(T\right) := \left\{ x\in H \colon T \left( x \right) = x \right\}. \end{align*}$ ただし、 $T \colon H \to H$ は非拡大写像 (nonexpansive mappping)、すなわち、 $\|T(x) - T(y) \| \leq \| x-y \|$ $(x,y\in H)$ を満たす写像です。不動点定理は、 Banach, Brouwer, Caristi, Fan, 角谷, Kirk, Schauder, 高橋といった偉大な数学者によって研究がなされ、Hilbert空間に限らず、より一般な空間上での非線形写像の不動点の存在性やその近似法について研究が今なお盛んに行われています。以下に不動点問題の重要な例を紹介します。

凸実行可能問題 (Convex Feasibility Problem):
空でない閉凸集合 $C_i$ $(\subset H)$ $(i\in \mathcal{I} := \{1,2,\ldots,I \})$ が与えられたとき、 $\begin{align*}x^\star \in C:= \bigcap_{i\in \mathcal{I}} C_i\end{align*}$ を満たす点 $x^\star$ を見つける問題を凸実行可能問題と呼びます。この問題は、信号復元問題といった実問題を含んでいます。
$C_i$ $(i\in \mathcal{I})$ への距離射影 $P_i$ ¹⁾を用いて、 $T := P_1 P_2 \cdots P_I$ と定義²⁾します。このとき、 $T$ は非拡大写像となり、 $\mathrm{Fix}(T) = C = \bigcap_{i\in \mathcal{I}} C_i$ を満たします。
制約付き凸最適化問題 (Constrained Convex Optimization Problem):
$C$ $(\subset H)$ を空でない閉凸集合とし、 $f\colon H \to \mathbb{R}$ をFréchet微分可能な凸関数でその勾配 $\nabla f$ が正係数 $L$ をもつLipschitz連続作用素とします。このとき、 $\begin{align*}f(x^\star) \leq f(x) \text{ } (x\in C)\end{align*}$ を満たす点 $x^\star$ を見つける問題が制約付き凸最適化問題です。凸最適化問題の応用例については、最適化アルゴリズムページをご参照下さい。
$T := P_C (\mathrm{Id} - \alpha \nabla f)$ と定義しましょう。ただし、 $\mathrm{Id}$ は $H$ 上の恒等写像³⁾であり、 $P_C$ は $C$ への距離射影、 $\alpha \in (0,2/L]$ とします。このとき、写像 $T$ は非拡大となり、 $T$ の不動点は $f$ の $C$ 上の最小解 $x^\star$ と一致します。