差分

このページの2つのバージョン間の差分を表示します。

--- intro:researches:fixedpoint [2016/03/18 13:38] – Hideaki IIDUKA
+++ intro:researches:fixedpoint [2016/07/09 19:57] – Hideaki IIDUKA
@@ 行 1: / 行 1: @@
 ====== 不動点近似法の研究紹介 ======
 ===== 不動点問題とその応用例 =====
-ここでは、ノルム$\| \cdot \|$と内積$\langle \cdot, \cdot \rangle$をもつHilbert空間$H$上の不動点問題について考察しましょう。
+ノルム$\| \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)$を満たす写像です。
+ただし、$T \colon H \to H$は**非拡大写像 (nonexpansive mappping)**、すなわち、$\|T(x) - T(y) \| \leq \| x-y \|$ $(x,y\in H)$を満たす写像です。
 [[http://ja.wikipedia.org/wiki/不動点定理|不動点定理]]は、
 [[http://ja.wikipedia.org/wiki/ステファン・バナフ|Banach]], [[http://ja.wikipedia.org/wiki/ライツェン・エヒベルトゥス・ヤン・ブラウワー|Brouwer]],
@@ 行 17: / 行 17: @@
   - **制約付き凸最適化問題 (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$を見つける問題が制約付き凸最適化問題です。凸最適化問題の応用例については、[[intro:researches:optimization|最適化アルゴリズム]]ページをご参照下さい。\\ $T := P_C (\mathrm{Id} - \alpha \nabla f)$と定義しましょう。ただし、$\mathrm{Id}$は$H$上の恒等写像(($\mathrm{Id}(x) := x$ $(x\in H)$が定義です。))であり、$P_C$は$C$への距離射影、$\alpha \in (0,2/L]$とします。このとき、写像$T$は非拡大となり、$T$の不動点は$f$の$C$上の最小解$x^\star$と一致します。
-===== 既存の不動点近似法と共通の性質について =====
+==== 既存の不動点近似法 ====
 不動点問題を解くための解法としては、以下の有用な3つの不動点近似法が知られています。
@@ 行 23: / 行 23: @@
   * [[http://dx.doi.org/10.1090/S0002-9904-1967-11864-0|Halpern]] アルゴリズム
   * [[http://dx.doi.org/10.1016/S0022-247X(02)00458-4|Hybrid]] アルゴリズム
-反復回数$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*}
-で定義される共役勾配方向(($(\beta_n)_{n\in\mathbb{N}} \subset (0,\infty)$です。))と既存の不動点近似法を融合することにより加速法を考案しています。
-以降では、既存の不動点近似法の加速に関する我々の研究成果を紹介します。
 ===== 不動点を見つけるための加速法 =====
 ==== Krasnosel'skii-Mann アルゴリズムの加速 ====
-Krasnosel'skii-Mann アルゴリズム(($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)$です。))
+Krasnosel'skii-Mann アルゴリズムに基づいた手法を考案し、提案手法が既存手法よりも高速に不動点に収束することを示しました。研究成果については、以下の論文に纏めてあります(論文は[[intro:publications|研究業績等一覧]]から入手できます)。
-\begin{align*}
+  * [[:iiduka:|H. Iiduka]]: [[http://fixedpointtheoryandapplications.springeropen.com/articles/10.1186/s13663-016-0567-7| Line Search Fixed Point Algorithms Based on Nonlinear Conjugate Gradient Directions: Application to Constrained Smooth Convex Optimization]], Fixed Point Theory and Applications, Vol. 2016, No. 77, 2016.
-x_{n+1} := \alpha_n x_n + \left( 1- \alpha_n \right) T \left(x_n\right) \text{ } (n\in \mathbb{N})
+  * [[:kaz|K. Hishinuma]] and [[:iiduka:|H. Iiduka]]: [[http://www.ybook.co.jp/online-p/JNCA/Open/16/jncav16n11p2243-oa/FLASH/index.html|On Acceleration of the Krasnosel'skii-Mann Fixed Point Algorithm Based on Conjugate Gradient Method for Smooth Optimization]], Journal of Nonlinear and Convex Analysis: Special Issue-Dedicated to Wataru Takahashi on the occasion of his 70th birth day, Vol. 16, No. 11, pp. 2243-2254, 2015.
-\end{align*}
-と共役勾配方向の概念を合わせたアルゴリズムを提案し、そのアルゴリズムが$T$の不動点に弱収束((点列$(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)$を満たすときを言います。))することを証明しました。
-上記1,2について、Krasnosel'skii-Mann アルゴリズムと提案手法の数値比較を行い、提案手法が既存手法よりも高速に不動点に収束することを示しました。研究成果については、以下の論文に纏めてあります。
-  * [[:kaz:|K. Hishinuma]] and [[:iiduka:|H. Iiduka]]: On Acceleration of the Krasnosel'skii-Mann Fixed Point Algorithm Based on Conjugate Gradient Method for Smooth Optimization, submitted.
-**実験結果 (公開予定)**
 ==== Halpern アルゴリズムの加速 ====
-Halpern アルゴリズム(($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)$があります。))
+Halpern アルゴリズムと提案手法の数値比較を行い、提案手法が既存手法よりも高速に不動点に収束することを示しました。この成果については、以下の論文に纏めてあります(論文は[[intro:publications|研究業績等一覧]]から入手できます)。
-\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$の不動点に強収束((点列$(x_n)_{n\in\mathbb{N}}$が$x^\star$ $(\in H)$に強収束するとは、$\lim_{n\to\infty} \| x_n - x^\star \| = 0$ を満たすときを言います。))することを証明しました。
-上記1,2について、Halpern アルゴリズムと提案手法の数値比較を行い、提案手法が既存手法よりも高速に不動点に収束することを示しました。この成果については、以下の論文に纏めてあります。
   * [[:kaito:|K. Sakurai]] and [[:iiduka:|H. Iiduka]]: [[http://www.fixedpointtheoryandapplications.com/content/2014/1/202|Acceleration of the Halpern Algorithm to Search for a Fixed Point of a Nonexpansive Mapping]], Fixed Point Theory and Applications, Vol. 2014, 202, 2014.
-**実験結果 (公開予定)**
 ==== 関連する加速法 ====
-不動点集合上の凸最適化問題に関する加速法についは、以下の結果にあります。興味のある方は、是非、ご参照下さい。
+不動点集合上の凸最適化問題に関する加速法については、以下の結果にあります。ご興味のある方は、是非、ご参照下さい(論文は[[intro:publications|研究業績等一覧]]から入手できます)。
   * [[:iiduka:|H. Iiduka]]: [[http://link.springer.com/article/10.1007/s10107-013-0741-1|Acceleration Method for Convex Optimization over the Fixed Point Set of a Nonexpansive Mapping]], Mathematical Programming, Vol. 149, No. 1, pp. 131-165, 2015.
   * [[:iiduka:|H. Iiduka]]: [[http://www.sciencedirect.com/science/article/pii/S0096300311000099|Three-term Conjugate Gradient Method for the Convex Optimization Problem over the Fixed Point Set of a Nonexpansive Mapping]], Applied Mathematics and Computation, Vol. 217, No. 13, pp. 6315-6327, 2011.
-  * [[:iiduka:|H. Iiduka]] and I. Yamada: [[http://epubs.siam.org/action/showAbstract?page=1881&volume=19&issue=4&journalCode=sjope8|A Use of Conjugate Gradient Direction for the Convex Optimization Problem over the Fixed Point Set of a Nonexpansive Mapping]], SIAM Journal on Optimization, Vol. 19, No. 4, pp. 1881-1893, 2009.
+  * [[:iiduka:|H. Iiduka]] and [[http://www.sp.ss.titech.ac.jp/index.php?%BB%B3%C5%C4%20%B8%F9|I. Yamada]]: [[http://epubs.siam.org/action/showAbstract?page=1881&volume=19&issue=4&journalCode=sjope8|A Use of Conjugate Gradient Direction for the Convex Optimization Problem over the Fixed Point Set of a Nonexpansive Mapping]], SIAM Journal on Optimization, Vol. 19, No. 4, pp. 1881-1893, 2009.