文書の過去の版を表示しています。
Fixed Point Algorithms
Fixed Point Problem and Its Applications
Consider the following fixed point problem on a real Hilbert space with inner product $\langle \cdot, \cdot \rangle$ and norm $\| \cdot \|$: \begin{align*} \text{Find } x \in \mathrm{Fix}\left(T\right) := \left\{ x\in H \colon T \left( x \right) = x \right\}, \end{align*} where $T \colon H \to H$ is nonexpansive (i.e., $\|T(x) - T(y) \| \leq \| x-y \|$ $(x,y\in H)$). A number of fixed point theorems have been studied by renowned mathematicians, such as Banach, Brouwer, Caristi, Fan, Kakutani, Kirk, Schauder, Takahashi, and so on. We give the following two examples of the fixed point problem.
- Convex Feasibility Problem:
The problem is to find \begin{align*}x^\star \in C:= \bigcap_{i\in \mathcal{I}} C_i,\end{align*} where $C_i$ $(\subset H)$ $(i\in \mathcal{I} := \{1,2,\ldots,I \})$ is nonempty, closed, and convex. This problem includes practical problems, such as signal recovery problem.
Let us define $T := P_1 P_2 \cdots P_I$1), where $P_i$ $(i\in \mathcal{I})$ stands for the metric projection onto $C_i$.2) Accordingly, $T$ is nonexpansive and $\mathrm{Fix}(T) = C = \bigcap_{i\in \mathcal{I}} C_i$. - Constrained Convex Optimization Problem:
Suppose that $C$ $(\subset H)$ is nonempty, closed, and convex, $f\colon H \to \mathbb{R}$ is Fréchet differentiable and convex, and its gradient, denoted by $\nabla f$, is Lipschitz continuous with a constant $L$ $(>0)$. The constrained convex optimization problem is to find \begin{align*}x^\star \in C \text{ such that } f(x^\star) \leq f(x) \text{ for all } x\in C.\end{align*} See Optimization Algorithms page for examples of the convex optimization problem.
Here, we define $T := P_C (\mathrm{Id} - \alpha \nabla f)$, where $\mathrm{Id}$ is the identity mapping on $H$,3) $P_C$ is the metric projection onto $C$, and $\alpha \in (0,2/L]$. Then, $T$ is nonexpansive and a fixed point of $T$ coincides with a minimizer of $f$ over $C$.
Conventional Fixed Point Algorithms
The following three algorithms are good ways to solve the fixed point problem.
- The Krasnosel'skii–Mann Algorithm
- The Halpern Algorithm
- The Hybrid Algorithm
Acceleration Algorithms for Solving Fixed Points
Acceleration of the Krasnosel'skii-Mann Algorithm
We numerically compared our algorithm with the Krasnosel’skii-Mann algorithm and showed that it reduces the running time and iterations needed to find a fixed point compared with that algorithm. It is summarized as the following paper.
- K. Hishinuma and H. Iiduka: 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.
Acceleration of the Halpern Algorithm
We presented an algorithm to accelerate the Halpern algorithm and proved that, under certain assumptions, our algorithm strongly converges to a fixed point of $T$. We numerically compared our algorithm with the Halpern algorithm and showed that it reduces the running time and iterations needed to find a fixed point compared with that algorithm. It is summarized as the following paper.
- K. Sakurai and H. Iiduka: Acceleration of the Halpern Algorithm to Search for a Fixed Point of a Nonexpansive Mapping, Fixed Point Theory and Applications, Vol. 2014, 202, 2014.
関連する加速法
不動点集合上の凸最適化問題に関する加速法については、以下の結果にあります。ご興味のある方は、是非、ご参照下さい。
- H. Iiduka: Acceleration Method for Convex Optimization over the Fixed Point Set of a Nonexpansive Mapping, Mathematical Programming, Vol. 149, No. 1, pp. 131-165, 2015.
- H. Iiduka: 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.
- H. Iiduka and I. Yamada: 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.
Acceleration of the Krasnosel'skii-Mann Algorithm
We devised an algorithm combining the ideas of the Krasnosel'skii-Mann algorithm4) defined by \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*} and the conjugate gradient method, and proved that, under certain assumptions, the algorithm weakly converges to a fixed point of $T$.5) We numerically compared our algorithm with the Krasnosel’skii-Mann algorithm and showed that it reduces the running time and iterations needed to find a fixed point compared with that algorithm. It is summarized as the following paper.
- K. Hishinuma and H. Iiduka: On Acceleration of the Krasnosel'skii-Mann Fixed Point Algorithm Based on Conjugate Gradient Method for Smooth Optimization, submitted.
Numerical Results (coming soon)
Acceleration of the Halpern Algorithm
The Halpern algorithm6) is \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*} We presented an algorithm to accelerate the Halpern algorithm and proved that, under certain assumptions, our algorithm strongly converges to a fixed point of $T$.7) We numerically compared our algorithm with the Halpern algorithm and showed that it reduces the running time and iterations needed to find a fixed point compared with that algorithm. It is summarized as the following paper.
- K. Sakurai and H. Iiduka: Acceleration of the Halpern Algorithm to Search for a Fixed Point of a Nonexpansive Mapping, Fixed Point Theory and Applications, Vol. 2014, 202, 2014.
Numerical Results (coming soon)
Related Work
We have presented the following acceleration methods for convex optimization over the fixed point sets of nonexpansive mappings. If you are interested, please see the following paper.
- H. Iiduka: Acceleration Method for Convex Optimization over the Fixed Point Set of a Nonexpansive Mapping, Mathematical Programming, Vol. 149, No. 1, pp. 131-165, 2015.
- H. Iiduka: 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.
- H. Iiduka and I. Yamada: 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.