intro:researches:fixedpoint

不動点近似法の研究紹介

不動点問題とその応用例

ノルム$\| \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空間に限らず、より一般な空間上での非線形写像の不動点の存在性やその近似法について研究が今なお盛んに行われています。以下に不動点問題の重要な例を紹介します。

  1. 凸実行可能問題 (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$1)を用いて、$T := P_1 P_2 \cdots P_I$と定義2)します。このとき、$T$は非拡大写像となり、$\mathrm{Fix}(T) = C = \bigcap_{i\in \mathcal{I}} C_i$を満たします。
  2. 制約付き凸最適化問題 (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) \quad (x\in C)\end{align*}を満たす点$x^\star$を見つける問題が制約付き凸最適化問題です。凸最適化問題の応用例については、最適化アルゴリズムページをご参照下さい。
    $T := P_C (\mathrm{Id} - \alpha \nabla f)$と定義しましょう。ただし、$\mathrm{Id}$は$H$上の恒等写像3)であり、$P_C$は$C$への距離射影、$\alpha \in (0,2/L]$とします。このとき、写像$T$は非拡大となり、$T$の不動点は$f$の$C$上の最小解$x^\star$と一致します。

既存の不動点近似法

不動点問題を解くための解法としては、以下の有用な3つの不動点近似法が知られています。

不動点を見つけるための加速法

Krasnosel'skii-Mann アルゴリズムの加速

Krasnosel'skii-Mann アルゴリズムに基づいた手法を考案し、提案手法が既存手法よりも高速に不動点に収束することを示しました。研究成果については、以下の論文に纏めてあります (論文は研究業績等一覧から入手できます)。

Halpern アルゴリズムの加速

Halpern アルゴリズムと提案手法の数値比較を行い、提案手法が既存手法よりも高速に不動点に収束することを示しました。この成果については、以下の論文に纏めてあります (論文は研究業績等一覧から入手できます)。

関連する加速法

不動点集合上の凸最適化問題に関する加速法については、以下の結果にあります。ご興味のある方は、是非、ご参照下さい(論文は研究業績等一覧から入手できます)。

1)
$P_i$は$P_i(x) \in C_i$, $\|P_i(x) - x \| = \inf_{y\in C_i}\| y-x \|$ $(x\in H)$として定義される非拡大写像です。
2)
$T$の構成方法は幾つかあります。例えば、$T := P_I P_{I-1} \cdots P_1$や$T:= \sum_{i\in \mathcal{I}} w_i P_i$と定義してもよいです。ただし、$(w_i)_{i\in \mathcal{I}} \subset (0,1)$は$\sum_{i\in\mathcal{I}} w_i =1$を満たすとします。
3)
$\mathrm{Id}(x) := x$ $(x\in H)$が定義です。
  • intro/researches/fixedpoint.txt
  • 最終更新: 2020/04/06 14:48
  • by Hideaki IIDUKA