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$は非拡大写像、すなわち、$\|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) \text{ } (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つの不動点近似法が知られています。

title : Fixed points of nonexpanding maps author : B. Halpern journal : Bulletin of the American Mathematical Society volume : 73 (6) pages : 957–961 year : 1967 url : http://dx.doi.org/10.1090/S0002-9904-1967-11864-0)]

  • Hybrid アルゴリズム [(hybrid»

title : Strong convergence theorems for nonexpansive mappings and nonexpansive semigroups authors : K. Nakajo\; W. Takahashi journal : Journal of Mathematical Analysis and Applications volume : 279 (2) pages : 372–379 year : 2003 url : http://dx.doi.org/10.1016/S0022-247X(02)00458-4)]

反復回数$n$のときの$T$の不動点に対する近似点を$x_n$とします。既存の不動点近似法に共通しているアルゴリズムの構成方法は、次の反復$(n+1)$の近似点$x_{n+1}$を構成するために、 \begin{align*} y_{n} := T \left(x_n \right) \end{align*} を計算することです。いま、上記2の例について考察しましょう。 このケースでは、 \begin{align*} y_n = P_C \left(x_n - \alpha \nabla f \left(x_n \right) \right) \end{align*} となり、$f$の$x_n$での最急降下方向$d_{n} := -\nabla f (x_n)$を利用していることが分かります。 一般には、最急降下法の最小解への収束速度は遅いため、最急降下法を加速させるための有用な手法が多く提案されています。 本研究では、特に、最急降下法を加速させることができる共役勾配法 [(cgm» title : Numerical Optimization authors : J. Nocedal\; S. Wright published : 2006 publisher : Springer pages : 664 isbn : 978-0-387-40065-5 url : http://www.springer.com/mathematics/book/978-0-387-30303-1)] に着目し、共役勾配法と既存の不動点近似法の概念を合わせた新しいアルゴリズムについて研究をしています。 具体的には、 \begin{align*} d_{n+1} := -\nabla f \left(x_{n+1} \right) + \beta_{n+1} d_n \text{ } (n\in\mathbb{N}) \end{align*} で定義される共役勾配方向4)と既存の不動点近似法を融合することにより加速法を考案しています。

以降では、既存の不動点近似法の加速に関する我々の研究成果を紹介します。

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

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

Krasnosel'skii-Mann アルゴリズム5) \begin{align*} x_{n+1} := \alpha_n x_n + \left( 1- \alpha_n \right) T \left(x_n\right) \text{ } (n\in \mathbb{N}) \end{align*} と共役勾配方向の概念を合わせたアルゴリズムを提案し、そのアルゴリズムが$T$の不動点に弱収束6)することを証明しました。 上記1,2について、Krasnosel'skii-Mann アルゴリズムと提案手法の数値比較を行い、提案手法が既存手法よりも高速に不動点に収束することを示しました。研究成果については、以下の論文に纏めてあります。

  • K. Hishinuma and H. Iiduka: On Acceleration of the Krasnosel'skii-Mann Fixed Point Algorithm Based on Conjugate Gradient Method for Smooth Optimization, submitted.

実験結果 (公開予定)

Halpern アルゴリズムの加速

Halpern アルゴリズム7) \begin{align*} x_{n+1} := \alpha_n x_0 + \left( 1- \alpha_n \right) T \left(x_n\right) \text{ } (n\in \mathbb{N}) \end{align*} と共役勾配方向の概念を合わせたアルゴリズムを提案し、そのアルゴリズムが$T$の不動点に強収束8)することを証明しました。 上記1,2について、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)$が定義です。
4)
$(\beta_n)_{n\in\mathbb{N}} \subset (0,\infty)$です。
5)
$x_0\in H$とし、$(\alpha_n)_{n\in\mathbb{N}}$は$\sum_{n=0}^\infty \alpha_n (1-\alpha_n) = \infty$を満たす点列とします。例としては、$\alpha_n := a \in (0,1)$です。
6)
点列$(x_n)_{n\in\mathbb{N}}$が$x^\star$ $(\in H)$に弱収束するとは、$\lim_{n\to\infty} \langle x_n, x \rangle = \langle x^\star,x \rangle$ $(x\in H)$を満たすときを言います。
7)
$x_0\in H$とし、$(\alpha_n)_{n\in\mathbb{N}}$は$\lim_{n\to\infty} \alpha_n = 0, \sum_{n=0}^\infty \alpha_n = \infty$を満たす点列とします。例としては、$\alpha_n := 1/(n+1)$があります。
8)
点列$(x_n)_{n\in\mathbb{N}}$が$x^\star$ $(\in H)$に強収束するとは、$\lim_{n\to\infty} \| x_n - x^\star \| = 0$ を満たすときを言います。
  • intro/researches/fixedpoint.1458275848.txt.gz
  • 最終更新: 2018/06/01 16:40
  • (外部編集)