差分

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

--- intro:researches:fixedpoint [2016/03/24 19:09] – [Krasnosel'skii-Mann アルゴリズムの加速] Hideaki IIDUKA
+++ intro:researches:fixedpoint [2020/04/06 14:48] (現在) – [不動点問題とその応用例] Hideaki IIDUKA
@@ 行 15: / 行 15: @@
 [[http://www.sci.keio.ac.jp/member/detail.php?eid=00119&katagaki=3&status=1|高橋]]といった偉大な数学者によって研究がなされ、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$を見つける問題を[[http://dx.doi.org/10.1137/S0036144593251710|凸実行可能問題]] と呼びます。この問題は、[[http://dx.doi.org/10.1109/78.782189|信号復元問題]] といった実問題を含んでいます。\\ $C_i$ $(i\in \mathcal{I})$への距離射影$P_i$(($P_i$は$P_i(x) \in C_i$, $\|P_i(x) - x  \| = \inf_{y\in C_i}\| y-x \|$ $(x\in H)$として定義される非拡大写像です。))を用いて、$T := P_1 P_2 \cdots P_I$と定義(($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$を満たすとします。))します。このとき、$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$を見つける問題が制約付き凸最適化問題です。凸最適化問題の応用例については、[[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$と一致します。
+  - **制約付き凸最適化問題 (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$を見つける問題が制約付き凸最適化問題です。凸最適化問題の応用例については、[[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$と一致します。
 ==== 既存の不動点近似法 ====
@@ 行 26: / 行 26: @@
 ===== 不動点を見つけるための加速法 =====
 ==== Krasnosel'skii-Mann アルゴリズムの加速 ====
-Krasnosel'skii-Mann アルゴリズムに基づいた手法を考案し、提案手法が既存手法よりも高速に不動点に収束することを示しました。研究成果については、以下の論文に纏めてあります(論文は[[intro:publications|研究業績等一覧]]から入手できます)。
+Krasnosel'skii-Mann アルゴリズムに基づいた手法を考案し、提案手法が既存手法よりも高速に不動点に収束することを示しました。研究成果については、以下の論文に纏めてあります (論文は[[intro:publications|研究業績等一覧]]から入手できます)。
-  * [[:iiduka:|H. Iiduka]]: [[http://arxiv.org/abs/1509.05605| Line Search Fixed Point Algorithms Based on Nonlinear Conjugate Gradient Directions: Application to Constrained Smooth Convex Optimization]], submitted.
+  * K. Fujiwara and [[:iiduka:|H. Iiduka]]: [[http://www.ybook.co.jp/online2/oplna/vol3/p189.html|Modification of the Krasnosel'skii-Mann Fixed Point Algorithm by Using Three-term Conjugate Gradients]], Linear and Nonlinear Analysis, Vol. 3, No. 2, pp.189-202, 2017.
-  * [[http://arnip.org/|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.
+  * [[: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.
+  * 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.
 ==== Halpern アルゴリズムの加速 ====
-Halpern アルゴリズムと提案手法の数値比較を行い、提案手法が既存手法よりも高速に不動点に収束することを示しました。この成果については、以下の論文に纏めてあります。
+Halpern アルゴリズムと提案手法の数値比較を行い、提案手法が既存手法よりも高速に不動点に収束することを示しました。この成果については、以下の論文に纏めてあります (論文は[[intro:publications|研究業績等一覧]]から入手できます)。
   * [[: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.
@@ 行 39: / 行 40: @@
 ==== 関連する加速法 ====
-不動点集合上の凸最適化問題に関する加速法については、以下の結果にあります。ご興味のある方は、是非、ご参照下さい。
+不動点集合上の凸最適化問題に関する加速法については、以下の結果にあります。ご興味のある方は、是非、ご参照下さい(論文は[[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 [[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.