en:intro:researches:fixedpoint

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.

  1. 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. It 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$.
  2. 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.

Acceleration Algorithms for Solving Fixed Point Problems

Acceleration of the Krasnosel'skii-Mann Algorithm

We numerically and theoretically 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 papers (You can get our papers from Publications page).

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 (You can get our papers from Publications page).

Related Acceleration Methods

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 papers (You can get our papers from Publications page).

1)
We may define $T$ by $T := P_I P_{I-1} \cdots P_1$ or $T:= \sum_{i\in \mathcal{I}} w_i P_i$, where $(w_i)_{i\in \mathcal{I}} \subset (0,1)$ satisfies $\sum_{i\in\mathcal{I}} w_i =1$.
2)
$P_i$ is defined by $P_i(x) \in C_i$ and $\|P_i(x) - x \| = \inf_{y\in C_i}\| y-x \|$ $(x\in H)$, and it satisfies the nonexpansivity condition.
3)
It is defined by $\mathrm{Id}(x) := x$ $(x\in H)$.
  • en/intro/researches/fixedpoint.txt
  • 最終更新: 2018/07/02 10:29
  • by Hideaki IIDUKA