数理解析研究所講究録
第 1548 巻 2007 年 107-114107
無制約最小化問題に対する拡張 Barzilai-Borwein 法について(Wakamatsu Takahiko)(Narushima Yasushi)
Graduate School of Science,
Tokyo University of Science
東京理科大学・数理情報科学科
矢部 博(Yabe Hiroshi)
Department of Mathematical Information Science,
Tokyo University of Science
東京理科大学大学院・理学研究科
東京理科大学大学院・理学研究科

1

峻彦
康史

若松
成島

はじめに以下の無制約最小化問題を取り扱う.

min$f(x)= \frac{1}{2}x^{T}Ax-b^{T}x$,(1)

但し, $A\in R^{nXn}$ は正定値対称行列, $b\in R^{n}$ とする. このとき, 問題 (1) こ対する最急降下方向を用いた勾配法を考える. その反復式は以下のようなものである.
$x_{k+1}=x_{k}- \frac{1}{\alpha_{k}}g_{k}$,(2)をにおける $f$ の勾配ベクトル,但し,をステップ幅とする. 最急降下法では,正確な直線探索を行った
まが採用される. このときの$g_{k}$$x_{k}$$\frac{1}{\alpha_{k}}$$\alpha_{k}1$$\alpha_{k}$(3)$\alpha_{k}=\frac{g_{k}^{T}Ag_{k}}{g_{k}^{T}g_{k}}$で表わされる. 最急降下法は最適化においてたびたび用いられる方法であるが, ヘッセ行列 $A$ の条件数が大きいときには収束が遅いことが知られている. これを改良するために, いくつかのの選び方が研究されている. 準一-n ートン法において, 近$\alpha_{k}$似行列に課される条件としてセカント条件$Bs_{k-1}=y_{k-1}$が知られている. 但し $B$ はヘッセ行列の近似行列とし, $s_{k-1}=x_{k}-x_{k-1}$ ,$y_{k-1}=g_{k}-g_{k-1}$ とする. Barzilai and Borwein [1] はを決める際に, セカント条
件の $B$ をに置き換え, 以下のような最小化問題を考えた.
$\nabla^{2}f(x_{k})$$\alpha_{k}$$\alpha I$$\alpha_{k}=\arg\min_{\alpha}||\alpha Is_{k-1}-y_{k-1}||_{2}$.

この最小化問題の解は,$\alpha_{k}=\frac{s_{k-1}^{T}y_{k-1}}{s_{k-1}^{T}s_{k-1}}$

(4)

108
を用いた勾配法は, Barzilai-Borwein 法と呼ばれるもので, 実用上
では最急降下法に比べて少ない反復回数で収束することが知られている. BarzilaiBorwein 法の収束性については, Raydan [4] が狭義凸 2 次関数に対する大域的収束性を示し, Dai and Liao [2] が R-l 次収束性を示している. さらに近年, Friedlanderet al. [3] は, Barzilai-Borwein 法を含む方法として遅延付き勾配法を提案した. 遅延は次のようなものである.
付き勾配法におけるとなる.

この$\alpha_{k}$$\alpha_{k}$$\alpha_{k}=$(5)$\frac{g_{\nu(k)}^{T}A^{\rho(k)+1}g_{\nu(k)}}{g_{\nu(k)}^{T}A^{\rho(k)}g_{\nu(k)}}$$\nu(k)$$\in$$\{k,k-1, \ldots,\max\{0,k-m\}\}$$\rho(k)$$\in$$\{q_{1}, \ldots,q_{m}\}$,,

但し, $m$ は正整数, $qj(j=1, \ldots, m)$ は $\%\geq-2$ を満たす整数とする. 遅延付き勾配法
については, Friedlander et al. [3] が狭義凸 2 次関数に対する大域的収束性をしめし,さらに特別な仮定のもとで -超 1 次収束性を示している.
$Q$2

提案する解法
本論では, 次の$\alpha_{k}$を利用する勾配法を提案する.
$\alpha_{k}=\sum_{1=1}^{\ell}\phi_{i^{\frac{g_{\nu_{j}(k)}^{T}A^{\rho:(k)+1}g_{\nu_{1}(k)}}{g_{\nu.(k)}^{T}A^{\rho i(k)}g_{\nu_{j}(k)}}}}.$$\phi;\geq 0(i=1, \ldots,\ell)$

,(6)

’

$\sum_{=j1}^{\ell}\phi_{i}=1$,$\nu_{1}(k)$$\in$$\{k,k-1, \ldots,\max\{0, k-m\}\}$$\rho_{i}(k)$$\in$$\{q_{1}, \ldots,q_{m}\}$,,は正整数, $\%(j=1, \ldots, m)$ は整数とする. これを拡張 Barzilai-Borwein 法
はのレイリー商の凸結合であり, が正定値対称行列であることと呼ぶ. またから,

但し,$\ell,$$m$$\alpha_{k}$

$A$

$A$

$0<\lambda_{\min}\leq\alpha_{k}\leq\lambda_{\max}$

が成り立っ. 但し,

for all$k$

は, それぞれ行列 $A$ の最小固有値と最大固有値である. ここで, (2) と $g_{k}=Ax_{k}-b$ から$\lambda_{\min}$と$\lambda_{\max}$$s_{k}=- \frac{1}{\alpha_{k}}g_{k}$(7)$y_{k}=As_{k}$

(8)

および

109を得る. よって (6) の$\alpha_{k}$は, (7), (8) から,$\alpha_{k}$(9)$= \sum_{j=1}^{\ell}\phi_{i^{\frac{s_{\nu_{j}(k)}^{T}A^{\rho i(k)+1}s_{\nu_{j}(k)}}{s_{\nu_{j}(k)}^{T}A^{\rho j}t^{k)_{S_{\nu_{j}(k)}}}}}}$$= \sum_{i--1}^{\ell}\phi_{i^{\frac{y_{\nu_{j(k)}}^{T}A^{\beta j.(k)-1}y_{\nu_{j}\langle k)}}{y_{\nu:\{k)}^{T}A^{\rho.(k)-2}y_{\nu:(k)}}}}$と書き換えることができる. このとき, (6) において, $\ell=1,$ $\nu_{1}(k)=k,$ $\rho_{1}(k)=0$ というパラメータを選んだときは, 最急降下法 (3) となり, (9) において, $\ell=1,$ $\nu_{1}(k)=$$\max\{0, k-1\},$ $\rho_{1}(k)=0$ というパラメータを選んだときは, Barzilai-Borwein 法 (4)となり, (6) において, $\ell=1,$ $q_{j}\geq-2$ というパラメータを選んだときは, 遅延付き勾配法 (5) となる. 提案した方法のアルゴリズムは次のようなものである.

アルゴリズム (拡張 Barzilai-Borwein 法)

Step$0$. 初期点$X_{O}$を与え, $k=0$ とする. 停止条件を満たしていれば終了し, さもなければ Step 1 へ進む.

Step 1. パラメータ
Step 2.

$\alpha_{k}$を計算する.

$x_{k+1}=x_{k}- \frac{1}{\alpha_{k}}g_{k}$により, 点$x_{k}$を更新する.

Step 3. 停止条件を満たしているならば終了する.
Step 4. $karrow k+1$ とし, Step 1 へ進む.

3

大域的収束性

提案した拡張 Barzilai-Borwein 法の大域的収束性を示す.
を最小化問題 (1) の唯を拡張 Barzilai-Borwein 法によって生成される点列, $e_{k}=x_{*}-x_{k}$一の最小解,を誤差とする. このとき $b=Ax_{*}$ より,$x_{*}$$\{x_{k}\}$$g_{k}$が成立するので,$e_{k+1}$と$e_{k}$$=Ax_{k}-b$$=$$Ax_{k}-Ax_{*}$$=$$-Ae_{k}$の関係式は,$e_{k+1}$$=$$x_{*}-x_{k+1}$$=$$e_{k}+ \frac{1}{\alpha_{k}}g_{k}$$=$$\frac{1}{\alpha_{k}}(\alpha_{k}I-A)e_{k}$(10)110となる. ここで, 行列 $A$ の固有値をとし, 対応する正規直交化しとする. このとき, 初期誤差 はある定数岬,た固有ベクトルをを用いて$\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$$v_{1},$$v_{2},$$\ldots,$$v_{n}$$d_{2}^{0},$$e_{0}$$\theta_{n}$$\ldots,$$e_{0}= \sum_{i=1}^{n}\theta_{i}v_{i}$と表すことができ, (10) より,$= \prod_{j=0}^{k}\frac{1}{\alpha_{j}}(\alpha_{j}I-A)e_{0}$$e_{k+1}$$\{\prod_{j=0}^{k}\frac{1}{\alpha_{j}}(\alpha_{j}I-A)\}(\sum_{j--1}^{n}\theta_{1}v;)$$= \sum_{1=1}^{n}\theta_{j}\{\prod_{j=0}^{k}\frac{1}{\alpha_{j}}(\alpha_{j}I-A)\}v_{i}$$= \sum_{i=1}^{n}ff_{1}\{\prod_{j=0}^{k}\frac{1}{\alpha_{j}}(\alpha_{j}-\lambda_{i})\}v_{i}$を得る. このことから$e_{k+1}$.と $d^{k+1}$ はそれぞれ$e_{k+1}= \sum_{1=1}^{n}d_{1}^{k+1}v_{i}$および$d_{1}^{k+1}=d_{j}^{0} \prod_{j=0}^{k}(\frac{\alpha_{j}-\lambda_{i}}{\alpha_{j}})$と表すことができる. これらを利用すれば, 以下の補題が成立する.

補題 1
数列

$\{d_{1}^{k}\}$は, 収束因子$1-\lambda_{1}/\lambda_{n}$で$0$に 1 次収束する.

補題 2ある整数 $p(2\leq p\leq n)$ に対して, 数列$\{d_{1}^{k}\},$$\{d_{2}^{k}\},$$\{d_{p-1}^{k}\}$$\ldots,$がすべて$0$に収束する

ならば,$\lim_{karrow}\inf_{\infty}|d_{p}^{k}|=0$が成立する.

これらの補題から以下の収束定理が導かれる.
定理 1最小化問題 (1) }こ対して,$x_{*}$を拡張 Barzilai-Borwein 法によって生成される点列,はに大域的収束する.
を唯一の最小解とする. このとき, 点列$\{x_{k}\}$$\{x_{k}\}$$x_{*}$

1114

数値実験

この節では, 数値実験結果を報告する. テスト問題として扱ったのは以下の狭義凸2 次関数である.
$f(x)= \frac{1}{2}x^{T}Diag(\lambda_{1}, \ldots, \lambda_{n})x$,$x\in R^{n}$

但し, 次元 , ヘッセ行列の条件数 cond はそれぞれ $10^{2},10^{3},10^{4}$ として, ヘッセ行列$\lambda_{n}=cond$ とし, $\lambda_{1}<\lambda;<\lambda_{n}(i=2, ..,n-1)$の固有値 $\lambda;(i=1, \ldots, n)$ はとする. 今回は $\lambda;(i=2, \ldots, n-1)$ をランダムに発生させ, 10 回実験した. 各数表には, その反復回数の平均値を示した. 太字になっている数値は, その項目において反復回数が一番少なかったものである. また, 初期点は は $(x_{1}, \ldots, x_{n})^{T}=(1, \ldots, 1)^{T}$$n$$\lambda_{1}=1,$$x_{0}$として, 停止条件は $||g_{k}||_{2}\leq 10^{-8}$ とした. このとき, Barzilai-Borwein 法, 遅延付112
き勾配法, 拡張 Barzilai-Borwein 法の反復回数を比較する. はじめに表 1 では, パラメータに関しては $\rho;(k)=0$ で固定し, 他のパラメータに関しては $\ell=1$の場合, $\nu_{1}(k)=k-1,$ $k-2,$ $k-3,$ $k-4,$ $k-5$ として, $\ell=2$ の場合, $\phi_{i}=0.5$ ,$\rho;(k)$$\nu_{1}(k)=k-1,$$k-2,k-3,$ $k-4,$ $\nu_{2}(k)=k-2,$ $k-3,$ $k-4,$ $k-5$ として実験を行っこの結果からわかるように, $\ell=2$ とした拡張 Barzilai-Borwein 法は, BarzilaiBorwein 法や遅延付き勾配法と同等の反復回数で収束している. 次に表 2 では, パラメータに関しては $\nu_{i}(k)=k-1$ で固定し, 他のパラメータに関しては $\ell=1$ の場
合, $\rho_{1}(k)=0,1,2,3$ として, $\ell=2$ の場合, $\phi_{i}=0.5,$ $\rho_{1}(k)=0,1,2,3,$ $\nu_{2}(k)=1,2,3,4$として実験を行った. この結果から $\ell=2$ とした拡張 Barzilai-Borwein 法は, Barzilaiた.

$\nu_{i}(k)$表 2: パラメータ $\rho;(k)$ を動かした場合の反復回数

Borwein 法や遅延付き勾配法より反復回数が増加している. よってパラメータは, なるべく変動させないで固定した方が良いことがわかる. 最後に表 3 では, パラ$\rho;(k)$113に関しては $\nu_{1}(k)=k-4,$ $\nu_{2}(k)=k-5,$ $\rho;(k)=1$ で固定し, 他のパラメータに関しては $\ell=1$ の場合, $\phi_{1}=1$ として, $\ell=2$ の場合, $\phi_{1}=0.75$ ,0.5,0.25,メータ$\nu_{i}(k),$$\rho;(k)$$\phi_{2}=0.25,0.5,0.75$として実験を行った. この結果から $\ell=2$ とした拡張 Barzilai-表 3: パラメータ$\phi_{i}$を動かした場合の反復回数

Borwein 法は, パラメータ : の選び方によって, Barzilai-Borwein 法や遅延付き勾配$\phi$

法より反復回数を減少させることが出来ることがわかる. しかし, 今回の実験では顕著な傾向は存在せず, どのようなパラメータを選べば反復回数が減少するかは今のところ明らかではない.

114

5

おわりに

本論文では, 拡張 Barzilai-Borwein 法を提案し, その大域的収束性を示した. また,数値実験により有効性を検証した. 今後の課題は, 提案した方法に含まれるパラメータの選び方, -超 1 次収束性の証明, および一般関数への適用などがあげられる.
$Q$

参考文献
[1] J. Barzilai and J. M. Borwein, Two point step size gradient methods, IMA
Numer. Anal., 8 (1988), pp. 141-148.

$J$.

[2] Y. H. Dai and L. Z. Liao, R-linear convergence of the Barzilai and Borwein
gradient method, IMA J. Numer. Anal., 22 (2002), pp. 1-10.
[3] A. Ftiedlander, J. M. Martinez, B. Molina, and M. Raydan, Gradient methodwith retards and generalizations, SIAM J. Numer. Anal., 36 (1999), pp. 275-289.
[4] M. Raydan, On the Barzilai and Borwein choice of steplength for the gradientmethod, IMA J. Numer. Anal., 13 (1993), pp. 321-326.