数理解析研究所講究録
第 1685 巻 2010 年 26-31

26

不動点集合上の変分不等式問題に関する不動点最適化アルゴリズム
飯塚秀明 (Hideaki Iiduka)

九州工業大学ネットワークデザイン研究センター(Network Design Research Center,Kyushu Institute of Technology)
東京都千代田区内幸町 2-2-3 日比谷国際ビル lF 107 区
Email : iiduka@ndrc.kyutech.ac.jp

1

はじめに$H$を内積$\langle\cdot,$$\cdot\rangle$とその内積で定義されたノルムをもつ実ヒルベルト空$\Vert\cdot\Vert$間とする。 この論文では、 次の不動点集合上の変分不等式問題を議論する。

問題 1.1. $T:Harrow H$ は非拡大写像で Fix $(T);=\{x\in H:T(x)=x\}\neq\emptyset$とし、 $A:Harrow H$ は単調かつ、 連続とする。 このとき、$\langle v-x^{*},$$A(x^{*})\rangle\geq 0(v\in$Fix $(T))$となる $x^{*}\in$ Fix $(T)$ を見つけよ。
$A$が強単調かつ、 リプシッツ連続作用素のとき、 問題 1.1 を解くための幾つかのアルゴリズムが提案されている$[$13, 1, 3, 4, 8 。この問題に関する先$]$

駆的なアルゴリズムーハイブリッド最急降下法-は、 [13] で提案されている。

1 では、 問題 1.1 の応用として信号復元問題を考察し、 その問題に関する反復手法を提案している。 [3] では、 準非拡大写像の不動点集合上での変分不等式に関するアルゴリズムを与えている。 [1, 4, 8] では、 ハイブリッド最急$[$$]$降下法を加速させるためのアルゴリズムを提案している。 $A$ が逆強単調のときのアルゴリズムは、 [10, 11, 6] で提案されている。

27

本論文では、 $A$ が単調かつ、 連続な作用素に関する問題 1.1 を解くための不動点最適化アルゴリズムとその収束解析を提案する。 これらの結果や証明、 また、 応用 (電力制御問題) については、 [5, 9, 7] を参照にされたい。

2

不動点最適化アルゴリズムとその収束解析
この章では、 $T:Harrow H$ は firmly nonexpansive 写像 [12] (任意の $x,$ $y\in$$H$に対して、 $\langle x-y,$ $T(x)-T(y))\geq\Vert T(x)-T(y)\Vert^{2}$ が成立) であると仮定する。 問題 1.1 に関する不動点最適化アルゴリズムを提案する。

アルゴリズム 2.1 ([5]).

Step . $x_{1}\in H$$0$、$\lambda_{1}\in(0,1)$ 、$\alpha_{1}\in(0,1]$を任意に選び、 $n$ $:=1$ と置く。

Step 1. $x_{n}\in H$ が与えられたとき、 $\lambda_{n}\in(0,1)$、$\alpha_{n}\in(0,1]$を選び、$\{\begin{array}{l}y_{n}:=T(x_{n}-\lambda_{n}A(x_{n})),x_{n+1}:=\alpha_{n}x_{n}+(1-\alpha_{n})y_{n}\end{array}$を計算する。 $n$ $:=n+1$ と置き、 Stepl へ行く。

アルゴリズム 2.1 に関する収束解析を提案する。
定理 2.2 ([5]). (I)$\bigcap_{n=n_{0}}^{\infty}\{x\in$

する
$($ii

$*$

lo

$(A(x_{n}))_{n\in \mathbb{N}}$Fix $(T):\langle x_{n}-x,$ $A(x_{n})\rangle\geq 0\}$ を満たす$(\alpha_{n})_{n\in \mathbb{N}}\subset[0,1)$$) \sum_{n=1}^{\infty}\lambda_{n}^{2}<\infty$$(x_{n})_{n\in \mathbb{N}}$(b) [$(T(x_{n}))$と、$(\lambda_{n})_{n\in \mathbb{N}}\subset(0,1)$$(y_{n})_{n\in \mathbb{N}}$、$:=$が存在するとは、 (i) $\lim\sup_{narrow\infty}\alpha_{n}<1$、は有界。の関係] $\lim_{narrow\infty}\Vert x_{n}-y_{n}\Vert=0$$T(x_{n})\Vert=0$ が成り立つ。

$*1$$no\in \mathbb{N}$$\subset\Omega$を満たす点列とする。 このとき、 以下が成立する。

(a) [有界性]$(x_{n})$は有界、 (II) VI(Fix $(T),$ $A$ )詳細については、 注意 23 を見よ。

、$\lim_{narrow\infty}\Vert x_{n}-$28(c) [ $(x_{n})$ の収束性] $\lim_{narrow\infty}\Vert x_{n}-y_{n}\Vert/\lambda_{n}=0^{*2}$ ならば、$(x_{n})_{n\in \mathbb{N}}$は問題 1.1 の解に弱収束する。
注意 2.3.

$x_{n}\in$

Fix $(T)(n\geq n_{0})$ となる(II) は成立する。 条件 (ii) の代わりに、$n_{0}\in \mathbb{N}$が存在するとすると、条件$\sum_{n=1}^{\infty}\lambda_{n}<\infty$を満たす点列$(\lambda_{n})$を利用することができれば、 条件 (II) を仮定することなく、 アルゴリズム

2.1 が問題 1.1 の解に弱収束することが証明できる [7]。しかしながら、 [5, 7]の数値例で見られるように、 $\lambda_{n}:=1/n^{2},1/n^{3}$ をもつアルゴリズム 2.1 が収

束条件 $\Vert x_{n}-y_{n}\Vert=o(\lambda_{n})$ を満たすことはほとんどない。 そのことから、 こ
こでは、 条件 (II) を仮定することにする。

3

数値例
アルゴリズム 2.1 の有効性と収束性を実演するために、 次の問題に関する数値例を与える。 その他の数値実験については、 [5, 7] を参照されたい。
問題 3.1.

$Q\in \mathbb{R}^{64\cross 64}$$\{x\in \mathbb{R}^{64}:\Vert x\Vert^{2}\leq 1\}$、を [2] で得られた半正定値行列とする。 また、 $C_{1}:=$$C_{2}:=\{x\in \mathbb{R}^{64}:\Vert x-(1,1,0, \ldots, 0)^{T}\Vert^{2}\leq 1\}$とする。 このとき、minimize$T:\mathbb{R}^{64}arrow \mathbb{R}^{64}$$f(x):= \frac{1}{2}\langle x,$$Q(x)\}$

st. $x\in C:=C_{1}\cap C_{2}$ .

を以下で定義する : 任意の$x\in \mathbb{R}^{64}$$T(x):= \frac{1}{2}P_{C_{1}}(x)+\frac{1}{2}P_{C_{2}}(x)$

に対して、

.

このとき、 $T$ は firmly nonexpansive 写像になり、 $C=$ Fix $(T)$ を満たす。

$*2$

詳細については、 第 3 章、 [5,$7|$を見よ。

29

そのことから、 問題 3.1 のアルゴリズムは次のようになる。

$x_{1}\in \mathbb{R}^{64}$,$\{\begin{array}{l}y_{n}:=T(x_{n}-\frac{1}{(n+1)^{c}}Q(x_{n})),x_{n+1}:=ax_{n}+(1-a)y_{n} (n\in \mathbb{N}).\end{array}$

ただし、 $a\in[0,1),$ $c\in[1, \infty)$ である。 もし、$n_{0}\in \mathbb{N}$$(\nabla f(x_{n}))_{n\in \mathbb{N}}$が有界で,が存在して、$x_{n}\in C(n\geq n_{0}),$$(X_{n}:=(n+1)^{c}\Vert x_{n}-y_{n}\Vert)_{n\in \mathbb{N}}arrow 0$

ならば、 定理 22 により、 アルゴリズム 2.1 は問題 3.1,$(A:=\nabla f$,Fix $(T)=C$ のときの問題 1.1) の解に収束する。 $C$ のコンパクト性と$\nabla f$の連続性により、 条件 (I) は成立する。 実験に関しては、 初期点$x_{1};=(-0.5, -0.5, \ldots, -0.5)^{T}\in \mathbb{R}^{64\text{、}}a:=0,1\prime 4,12,3/4$、$c;=1,2,3$を用いた。 アルゴリズム 2.1 の必要な反復回数は、 図 1 で示されている。 図 1 は、 $a:=0,1/4,1/2,3/4$が$c=1$ のとき、に収束し、 $x_{n}\in$ Fix $(T)=C(n\geq 100)$ が満たされている、 つまり、 条
件 (II) を満たすことを示している。 さらに、 図から、 $f(x_{n})$ が同じ値$(f(x_{n})\approx 0.452(n\geq 100))$

ら、 $a:=0,1/4,1/2,3/4$解に収束する。 速く$(X_{n})_{n\in \mathbb{N}}$$0$、$(X_{n})_{n\in \mathbb{N}}$、$0$に収束していることも分かる。 以上のことか$c=1$ のときの提案アルゴリズムは問題 3.1 のに収束する点列 $(c=2,3)$ を利用すると、 図 1 から、は $0$ に収束しない、 つまり、収束条件を満たさないことが分かる。

参考文献[1] P. L. Combettes, A block-iterative surrogate constmint splitting
method for quadmtic signal recovery, IEEE Trans. Signal Process.

51, no 7, pp. 1771-1782, July 2003.
[2] P. C. Hansen, Regularization Tools Version 4.1 (for Matlab Version7.3), Available: http://www2.imm.dtu.dk/ pch/Regutools/$\tilde$30

図1

問題 3.1 の解への収束について[3] S. A. Hirstoaga, Itemtive selection methods for common fixed pointpmblems, J. Math. Anal. Appl., 324 (2006), 1020-1035.
[4] H. Iiduka, Hybwtd conjugate gmdient method for a convex optimization pmblem over the fixed-point set of a nonexpansive mapping, J.

Optim. Theory Appl., 140 (2009), 463-475.

[5] H. Iiduka, A new itemtive algorithm for the variational inequality

problem over the fixed point set of a firmly nonexpansive mapping,

optimization, accepted for publication.
[6] H. Iiduka, An itemtive $algori\cdot thm$ for the tntple-hierarchical optimization pmblem, J. Optim. Theory Appl., accepted for publication.
[7] H. Iiduka, Fixed point optimization algorithm and its application topower contml in CDMA data networks, submitted.

31[8] H. Iiduka and I. Yamada, A use of conjugate gmdient direction forthe convex optimization pmblem over the fixed point set of a nonexpansive mapping, SIAM J. Optim., 19 (2009), 1881-1893.
[9] H. Iiduka and I. Yamada, An ergodic algorithm for the power-contml

games for CDMA data networks, J. Math. Model. Algorithms, 8(2009), 1-18.

[10] P. E. Maing\’e and A. Moudafi Strong convergence of an itemtive

method for hiemrchical fixed-point problems, Pacific J. Optim. 3(2007), 529-538.

[11] A. Moudafi, Krasnoselski-Mann itemtion for hiemrchical fixed-pointpmblems, Inverse Problems 23 (2007), 1635-1640.
[12] W. Takahashi, Nonlinear Functional Analysis, Yokohama Publish-ers, Yokohama, 2000.
[13] I. Yamada, The hybrid steepest descent method for the variational

inequality pmblem over the intersection of fixed point sets of nonex-pansive mappings, in Inherently Parallel Algorithms for Feasibilityand optimization and Their Applications (D. Butnariu, Y. Censorand S. Reich Eds.), Elsevier, New York, 2001, pp. 473-504.