数理解析研究所講究録
第 1643 巻 2009 年 50-5350
不動点集合上の凸最適化問題に関する共役勾配法
飯塚秀明 (Hideaki IIDUKA)
九州工業大学ネットワークデザイン研究センター
東京都千代田区内幸町 2-2-3 日比谷国際ビル lF 107 区
Email: iiduka@ndrc.kyutech.ac.jp

キーワード : 凸最適化問題、 非拡大写像、 不動点、 共役勾配法

1

はじめに$H$を内積$\langle\cdot,$$\cdot\rangle$とその内積で定義されたノルムに、 幾つかの定義を必要とする$||T(x)-T(y)\Vert\leq||x-y\Vert$$||\cdot||$をもつ実ヒルベルト空間とする。 まず、初め: $T;Harrow H$ が非拡大 [10] であるとは、任意の$x,$ $y\inが成り立っときをいう。 $A:Harrow H$ が $\alpha>0$ をもつ強単調 (H$ に対して$\sim$強単調) であるとは、任意の $x,$ $y\in H$ に対して $\langle x-y,$ $A(x)-A(y)\rangle\geq\alpha||x-y\Vert^{2}$ が成立するときをいう。 また、 $A$ が $L>0$ をもつリプシッツ連続 (L- リプシッツ連続) であるとは、任意の $x,$ $y\in H$ に対して$||A(x)-A(y)||\leq L\Vert x-y||$が成立するときをいう。 この論文では、次の凸最遁化問■を議論する :問題 11. $T:Harrow H$ は非拡大写像で Fix $(T);=\{x\in H:T(x)=x\}\neq\emptyset$ とし、 $f:Harrow R$ はフレッシェ微分可能で、 $\nabla f:Harrow H$ は$\alpha$-強単調かつ L- リプシッツ連続とする。 このとき、$f(x^{*})= \min_{x\in Fix(T)}f(x)$となる $x^{*}\in$ Fix $(T)$ を見つけよ。

制約付き最適化問題に関するよく知られた手法は、 次の射影勾配法であろう : $x_{1}\in H,$ $x_{n+1}=$$l*\ltimes(\tau)(x_{n}-\lambda_{n}\nabla f(x_{n}))(n\in N)_{\text{。}}$

ただし、 $\lambda>0$、$h_{ix(T)}:Harrow H$ は Fix $(T)$ への上への距離射影とする。 しかしながら、 $P_{Fix(T)}$ の陽な表現は一般に知られていないので、 $P_{Ftx(T)}$ を計算することが困難である。 例えば、 次の二つのケースを挙げる。 ケース 1: $C_{i}\subset H(i=1,2, \ldots,m)$ を空でない単純な閉凸集合 ($C_{i}$は閉球、 閉錐など) とし、 $C:= \bigcap_{i=1}^{m}C_{i}\neq\emptyset$ とする。 一般には $C$ の形状は大変複雑なために $C$ への距離射影点$)$を計算することは困難である。 そのため、 $\hat{x}=P_{C}(x)(x\in H$ は任意の$P_{C}$を得ることは難しい。 ケース 2: $C:= \{\hat{x}\in D:g(\hat{x})=\min_{x\in D}g(x)\}$ とする。 ただし、 $D\subset H$は空でない単純な閉凸集合、 $g:Harrow \mathbb{R}$ は凸で、 $\nabla g:Harrow H$ はて、$P_{C}$$\langle x-y,$ $\nabla g(x)-\nabla g(y)\rangle\geq\alpha\Vert\nabla g(x)-\nabla g(y)||^{2})$とする。

$\alpha$$P_{C}$-逆強単調 (任意の $x,$ $y\in H$ に対しの陽な表現は知られていないので、を直接計算することはできない。

制約集合への距離射影の陽な表現が知られていない、または、それを計算することが困難な場合の最適化問題を解決するために、次の予法 [11, 12, 13] が提案されている。 この手法は $P_{Fix(T)}$ の代わりに非拡大写像 $T$ を用いることでアルゴリズムを計算可能にしている : $x_{1}\in H,$ $x_{n+1};=T(x_{n}-\mu\alpha_{n}\nabla f(x_{n}))$$(n\in N)$ 。ただし、 $\mu>0,$はゆっくりと減少する点列とする。 この手法は、 問題$(\alpha_{n})_{n\in N}\subset(0,1]$1.1 の一意解に強収束することが保証されている [11, 12, 13]。上記の 2 つのケースを再度、 考察する。 ケース 1: 写像 $T(x):= \sum_{i=1}^{m}\omega_{i}P_{C_{l}}(x)(x\in H)$ を定義する。 ただし、$(\omega_{*})_{1=1}^{m}$を満たす点列とする。 この写像の計算は簡単であり、 (i)Fix $(T)$ $=$ C、及び、 (ii)$T$

は $\sum_{i=1}^{m}\omega_{i}=1$は非拡大の性質をもつ。 よって、 11, 12, 13 による手法はケース 1 での問題 11 の意解に強収束する。 ケース 2:$[$$]$$T(x):=P_{D}[x-\lambda\nabla g(x)](x\in H,$ $\lambda\in(0,2\alpha])$と定義することで、 (i) Fix(T) $=$ C、及び、 (ii) $T$ は非拡大が得られる。 上のケースと同様にして、 11, 12, 13 による手法がこのケースでの問題 11 の一意$[$$]$解に強収束することが保証される。
先駆的な手法 [11, 12, 13] は、 最急降下方向砺: $=-\nabla f(x_{n})$ を利用している。 制約無し最適化問題

51
では、 一般に、 共役勾配方向 $d_{n}:=-\nabla f(x_{n})+\beta_{n}d_{n-1}$ を利用したアルゴリズム (共役勾配法と呼ばれる) が最急降下法と比べて高速に解を近似させることができる。 本論文では、 11, 12, 13 を加速さ$[$$]$せるために、 共役勾配方向を利用した問題 11 に関するアルゴリズムを提案する。 また、 提案手法に関する問題 11 の解への収束性についても提案する。 これらの詳しい結果は、 4, 7 を参照されたい。
$[$2$]$

共役勾配方向を利用したアルゴリズムとその収束解析
我々は、 次の手法を提案する :アルゴリズム 21([4, 7]). $f:Harrow \mathbb{R}$ と $T;Harrow H$ は問題 11 と同じ仮定を満たすものとする。

Step . $\mu>0$ をとる。 $x_{1}\in H$ $\alpha_{1}\in(0,1]$ を任意に選び、 $d_{1}:=-\nabla f(x_{1})$Step 1. $x_{n}\in H.$ $d_{m}\in H$ が与えられたとき、 $\alpha_{n}\in(0,1]$ を選び、$n:=1$ と置く。

$0$

、

、

$x_{n+1}:=T(x_{n}+\mu\alpha_{n}d_{n})$(1)$d_{n+1}:=-\nabla f(x_{n+1})+\beta_{n+1}d_{n}$(2)を計算する。

Step 2.

$\beta_{n+1}\in[0,$ $\infty)$を選び、を計算する。 $n:=n+1$ と置き、 Stepi へ行く。
注意 22. (a) $T$ が $H$ 上の恒等写像、 $\mu:=1$ とするとアルゴリズム 21 は制約無し最適化問題に関する共役勾配法と一致する。 (1) 及び (2) により、 探索方向

$d_{n}$は、$[$11, 12, 13 の手法と共役勾配法の二$]$つのアイデアを合わせることで定義されていることがわかる。
b) 問題 11 に関する反復手法はの性質に応じて提案されている。
$($$\nabla f$

連続に関するアルゴリズムは、 [1, 3, 4, 7, 11, 12, 13] に提案されている。
ズムは、 8, 9 にある。 また、$[$$]$$\nabla f$が単調かつヘミ連続のケースでは $[5]$$\nabla f$が強単調かつリプシッツ$\nabla f$が逆強単調でのアルゴリ

単調作用素に関する手法は 6$[$、$]$で提案している。
アルゴリズム 21 に関する収束解析についても提案する :定理 23([4, 7]). $\mu\in(0,2\alpha/L^{2})$ とし、$( ii)\sum_{n=1}^{\infty}\alpha_{n}=\infty$$\alpha_{n}/\alpha_{n+1}\leq\sigma$、、(iii)$(\alpha_{n})_{n\in N}\subset(0,1]$$\sum_{n=1}^{\infty}|\alpha_{n+1}-\alpha_{n}|<\infty$$( v)\lim_{narrow\infty}\beta_{n}=0$、$(\beta_{n})_{n\geq 2}\subset[0, \infty)$、(iv) ある$\sigma\geq 1$

は、 (i) $\lim_{narrow\infty}\alpha_{n}=0$、と任意の $n\in N$ に対して、を満たす点列とする。

もし、 $(\nabla f(x_{n}))_{n\in N}$ が有界ならば、 アルゴリズム 21 で生成される点列$(x_{n})_{n\epsilon N}$

は、 問題 11 の一意解に強収束する。

3 数値例
アルゴリズム 21 の有効性と収束性を実演するために、 次の問題を議論する。 詳しくは、 [4, 7] を参照されたい。
問題$\theta.1$.

$Q\in \mathbb{R}^{64x64}$

を [2] で得られた正定値行列、 $b:=(-1, -2, \ldots, -64)^{T}\in \mathbb{R}^{64}$ とする。 また、$C_{1}:=\{x\in \mathbb{R}^{64}:\Vert x\Vert^{2}\leq 1\}$、

$C_{2}:=\{x\in \mathbb{R}^{64};\Vert x-(1,1,0, \ldots, 0)^{T}\Vert^{2}\leq 1\}$$\min f(x):=\frac{1}{2}\langle x,$ $Q(x))+\langle b,x\rangle s.t$とする。 このとき、. $x\in C:=C_{1}\cap C_{2}$ .

ここで使用した $Q$ は、 最小固有値 $\lambda_{m}\ln\approx 8.5539\cross 10^{-2\text{ }}$ 最大固有値 $\lambda\max\approx 9.9251X10$ をもつ。
、

また、 $\nabla f(\cdot):=Q(\cdot)+b$ は、$\lambda$

min-強単調かつ$\lambda_{mR^{-}}$リプシッツ連続である。 $f$ の最小値に値をとる

52

図1

$[2|$で与えられた正定値行列 $Q$ と $\beta_{n+1}:=1/(n+1)^{a}(a=0,1,0.01,0.001)$ 及び $\mu:=10^{-8}$に関する解への収束について ([7] から抜粋)

点は一 $Q^{-1}(b)\approx(24.4697, -23.8379, \ldots, 620.9782)^{T}\in R^{64}$ であり、 これは $C$ に属さない。 また、 $Q$[2] と $C:=C_{1}\cap C_{2}$ の定義により、 問題 31 の正砲な解を記述することはできない。 ここでは、初期点を $x_{1}:=(-0.5, -0.5, \ldots, -0.5)^{T}\in R^{64}$ とし、 $\alpha_{n}:=1/\sqrt{n+1}$を用いた。

$P_{C_{1}}$及び$P_{C_{2}}$解消させるために、 写像の計算は簡単であるが、$T:\mathbb{R}^{64}arrow \mathbb{R}^{64}$$P_{C_{1}\cap C_{2}}$、$\beta_{n+1}:=1/(n+1)^{a}(n\in N, a>0)$の計算は必ずしも簡単ではない。 この問題をを $T(x):=(1/2)Pc_{1}(x)+(1/2)Pc_{2}(x)(x\in R^{64})$ で定義する。 このとき、 $T$ は非拡大で Fix $(T)=C:=C_{1}\cap C_{2}\neq\emptyset$ を満たす。
$\lambda_{\max}$$\lambda_{\min}$、の近似値がわかっているので、 事前に$2\lambda_{\min}/\lambda_{\max}^{2}\approx 1.7367\cross 10^{arrow 5}$を計算することができる。 よって、 $\mu:=10^{-5}$ を利用した。 このとき、 [11, 12, 13] で提案された 「ハイブリッド最急降下法」 (HSDM) に対するアルゴリズム 2.1 の必要とされる反復回数は図 1 に示されている。 図 1 は$a=0.1,0.01$ ,0.001 のときのアルゴリズム 2.1 と HSDM で生成された $||x_{n}-T(x_{n})||(n\in N)$ がに収束する、 すなわち、 提案手法と HSDM は Fix $(T)=C$ の点に収束している。 同時に、 図 1 から$0$

HSDM と比較して、 アルゴリズム 21 はく解に収束する。

$(\beta_{n+1})_{n\in N}$$f$の値を大幅に減らすことに成功しており、 HSDM よりも速がとてもゆっくり$0$に収束する点列のとき $(a=0.O1,0.001)$、アルゴリ

ズム 21 はよりよい高速性をもっ。

注意 3.2. $Q$ が単位行列のとき、 HSDM がアルゴリズム 21 よりも速い収束性をもつ場合がある $[7]$が小さい時、 最急降
制約無し最適化問題での共役勾配法は、 最大固有値と最小固有値の比。

$\lambda_{m}in/\lambda\max$

下法と比べて大変効果的である。 しかしながら、 $\lambda_{m}in/\lambda\max=1$ のときは最急降下法は有効的である。

制約付き最適化問題においてもこれらの性質が受け継がれていると考えられる。 他の数値例に関する議論については、 [4, 7] を参照されたい。

参考文献[1] P. L. Combettes, A block-iterative surrogate constraint splitting method for quadratic 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 Version 7. ), Available:$S$

http: $//www2$ . imm. dtu. dk

pch/Regutools/[3] S. A. Hirstoaga, Iterative sdec tion methods for common fired point problems, J. Math. Anal.
$/\sim$Appl., 324 (2006), 1020 1035.
[4] Hideaki Iiduka, Hybrid conjugate gradient method for a convex optimization problem over the$\cdot$

53
fixed-point set of a nonexpansive mapping, J. Optim. Theory Appl., in press.
[5] Hideaki Iiduka, A new iterative algorithm for the vanational inequality problem over the fixedpoint set of a firmly nonexpansive mapping, optimization, accepted for publication.
[6] Hideaki Iiduka and Isao Yamada, A subgradient-type method for the equilibnum problem overthe fixred point set and its applications, optimization, in press.
[7] Hideaki Iiduka and Isao Yamada, A use of conjugate gradient direction for the convex op-timization problem over thepoint set of a nonexpansive mapping, SIAM J. Optim.,
accepted for publication.
[8] P. E. Maing\’e and A. Moudafi Strong convergence of an iterative method for hierarchical fixedpoint problems, Pacific J. Optim. 3 (2007), 52&538.
[9] A. Moudafl, Krasnosdski-Mann iteration for hierarchical fixed-point problems, Inverse Problems 23 (2007), 1635-1640.
[10] W. Takahashi, Nonlinear fihnctional Analysis, Yokohama Publishers, Yokohama, 2000.
[11] I. Yamada, The hybnd steepest descent method for the variational inequality problem over theintersection of fixed point sets of nonexpansive mappings, in Inherently Parallel Algorithms
for Feasibility and optimization and Their Applications (D. Butnariu, Y. Censor and S. ReichEds.), Elsevier, New York, 2001, pp. 47&504.
[12] I. Yamada and N. Ogura, Hybred steepest descent method for variational inequality problem
over the fxed point set of certain quasi-nonexpansive mapping, Numer. Funct. Anal. Optim.
25 (2004), 619-655.
[13] I. Yamada, N. Ogura and N. Shirakawa, A numerical robust hybrid steepest descent method forthe convexly constrained generalized inverse problems, Contemp. Math. 313 (2002), 269305.
$fix\epsilon d$