数理解析研究所講究録
915 巻 1995 年 192-202

192

安定な準ニュートン法のクラスについて
八巻直–

矢部

システム計画研究所

博

東京理科大学工学部

A Class of Stable Quasi-Newton Methods
Naokazu Yamaki’Hiroshi*Research Institute of Systems Planning Ltd.
**Science University of Tokyo$\searrow^{r}\mathrm{a}.\mathrm{b}\mathrm{e}**$1

はじめに
本稿では, 次の無制約最小化問題に対する数値解法を考える.

[UMP]

$f$

: $R^{n}arrow R$ のとき, $f(x)$ を x

この問題を解くための有力な手法として,$-arrow\Sigma-$

トン法の考え方に基づいており, 総称して準$-\vee L$$\in R^{n}$について最小化せよ.

トン法が挙げられる. またその他の反復法の多くは, $–L-$
一トン法と呼ばれる. 問題 [UMP] を解くための準.
$-\wedge.\ovalbox{\tt\small REJECT}$–

トン法のアルゴリズムのプロトタイプは, 以下の通りである.

[NL]
Step

$0$

. 初期点

$x_{0}\in R^{n}$と初期行列$B_{0}\in R^{n\cross n}$を与える. $k=0$ とおく.

Step 1. $||\nabla f(xk)||$ が非常に小さいならば停止する. さもなければ Step 2 へいく.
Step 2. 次の線形方程式を解いて, 探索方向
(1.1)

Step 3.

$d_{k}$

を作る$B_{k}d=-\nabla.f(x_{k)}$$\mathrm{j}L_{k+1}’=x_{k}$+\alpha Ad みとおく. ただし,.

. は適当なステップ幅である.

$\alpha_{k}$Step 4. 新しい行列 $B_{k+1}$ を作り, $k=k+1$ とおいて, Step 1 へ行く.

$\square$自身, もしくはその近似である. アルゴリズムの Step 4 はこのはヘッセ行列方法を特徴づけるもので,を変えることによっていろいろな解法が得られる. たとえば,
ここで, 行列$\nabla^{2}f(x_{k})$$B_{k}$$B_{k}$$B_{k}=\nabla^{\underline{r_{J}}}f(X_{k})$のとき $–=$ 一トン法そのものが得られるし,$B_{k}$

を更新して $B_{k+1}$ を生成すればセカント法が得られる [8].

後者の場合, 新しい行列 $B_{k+1}$ は次式で生成される$B_{k+1}=B_{k}+\triangle B_{k}$ただし,$\Delta/B_{k}$は補正行列で, 満足すべき条件として, テイラー展開から導かれる次のセカント条件が課さ

れる.

(1.2)

,

$B_{k+1^{S}k}=y_{k}$

,

193

ここで,

(1.3)

$s_{\mathrm{k}}=x_{k+1}-x_{k}$,$y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$である.

トン法は, 現在でも最も広く用いられている手法の–つであるが, ヘッセ行列の計算がやっかいであることと, 不安定挙動を示す場合があり得ることなどの欠点をもつ. このような欠点を克服し, かっ
ニ $\mathrm{I}^{-}$

ニュートン法の利点すなわち収束の速さを確保することを目的として, 準ニュートン法が提案された. 準
ニ. 一トン法は, 非線形関数の最小点を求める手法として, 現在考えられる最有力な手法の–つである. 準. 一トン法の利点を保持するために, 近似
ニ 1 一トン法では $f(x)$ のヘッセ行列の近似行列を用いるが,準-\rightarrow
L
一トン法においては, ヘッセ行列の近似行行列に対してセカント条件といわれる条件が課せられる.
列の正定値対称性の保証が, アルゴリズムの安定性に本質的に望ましい. 実際, 有力な方法である BFGS$-\ovalbox{\tt\small REJECT}$$–.\ovalbox{\tt\small REJECT}$が正定値対称であれば, 探のヘッセ行列の近似行列の正定値対称性が保存される.
$>0$
となる
.
したがって直線探索では\alphak$f(x)$
このような手法のクラスの減少方向となり,
索ベクトルはを伴う直線探索戦略に基づく準–n $-$ トン
を, 直線探索戦略という. 本稿では, 正定値性の保証された法を, 安定な準-^ $–$ 一トン法と定義する.
方, 準– 一トン法におけるヘッセ行列の近似行列の更新公式には, 正定値性を保証しないが有力な
公式もいくつか知られている. 最近注目されている信頼領域法では, 正定値性の保存が必ずしも必要ではない. このような手法のクラスを, 信頼領域戦略という. 信頼領域戦略では直線探索の代わりに, 現在の近似解の適当な近傍で目的関数の値を小さくするような, 子問題を解くことによって次の近似解を得る.
本稿では, セカント条件と正定値対称性の, 両方を満足する行列の–般形を導出し, その性質について検討する. すなわち, 次の 3 つの条件を満足するような行列 $B+$ を考える. この条件を SSP 条件と呼ぶこ法や DFP 法では,

$B_{k}$$f$$B_{k}$

$=$

とにする.

[SSP 条件](1:S) $s^{T}z>0$ を満たすベクトル(14)$\langle$$\langle$$s,$ $z\in R^{n}$が与えられたとき, 行列 $B+$ は次の条件を満足する :$B_{+}s=z$.

2: S) 行列 $B+$ は対称である.
3: P) 行列 $B+$ は正定値である.

SSP 条件を満足する行列を, 総称して SSP 行列と呼ぶ. ここで, $s^{T}z>0$ は $B+$ が正定値であるための必要条件になっていることに注意しよう. また, 条件 (1.4) にはヘッセ行列に関する適切な情報が含まれていなければならない. セカント法の場合, 条件 (1.4) はセカント条件 (1.2) そのものになるが, 我々はセカント法に限定せず, SSP 条件を満足する準ニュートン法について議論する. なお, 以下で述べる我々の研究は, Nazareth [6] の分類によれば metric-based 法になる.

2
本節では SSP 行列の–般形とその分解型を導出する. SSP 行列の–般形が, 次の定理によって与えられる.

定理 1. 式 (2.1) によって与えられる行列 $B+$ は SSP 行列の\dashv 4 形になる. ただし,を満たす任意ベクトルである.
意行列, 眉ま$s^{T}\Phi^{\tau}u\neq 0$$\Phi$

は列フルランクな任

194

(2.1)

(2.2)
$.arrow f_{\vee}^{arrow}.\text{し}$$c-, \frac{c_{ss^{T}}c}{s^{T}CS}+\frac{\sim\gamma z^{T}}{s^{T}z}+(s^{\tau_{C}}s)ww^{T}$$=$$B_{+}$,$(I- \frac{su^{T}\Phi}{s^{T}\Phi^{T_{u}}})^{T}C(I-\frac{su^{T}\Phi}{s^{T}\Phi^{\tau_{u}}})+\frac{zz^{T}}{s^{T_{\mathrm{v}}}\sim}$

$=$

,

(2.3)

$w= \frac{\Phi^{T}u}{s^{T}\Phi^{\tau_{u}}}-\frac{Cs}{s^{T}Cs}$,$C=\Phi^{\tau}\Phi$.

証明. 式 (2.1) で与えられる行列 $B+$ が SSP 条件を満足することは, 容易に示される.
は正定値対称なので, 列フルランクな行列
SSP 条件を満足する任意の行列とする.
逆に,$\Phi=\hat{L}+$. となるとおけば $c:=\hat{B}+$ となるので,となる.
x”” が存在して,に対して, $w=0$ となる. このとき (2.1) の右辺から$\hat{B}+$$\hat{B}_{+}\text{を}$$\hat{L}+\in R^{m}$$\Phi^{T_{\mathcal{U}}}=\sim$$\hat{B}+=\hat{L}_{++}^{\tau_{\hat{L}}}$$u$$c- \frac{CsSc^{1}T}{s^{T}c_{S}^{\mathrm{t}}}+\frac{\approx z^{T}}{s^{T_{7}}\sim}+(s^{T}cs)ww^{\tau}=\hat{B}_{+}-\frac{\hat{B}_{+^{ss^{T}\hat{B}}+}}{s^{T}\hat{B}_{+}s}+\frac{\sim\sim z^{T}}{s^{T_{\vee}}\sim}=\hat{B}_{+}$

を得る. すなわち,定理が証明された.

$\hat{B}+$(2.1) は SSP 行列の–般形である.

は (2.1) の形で表される. よって,したがって,$\square$

SSP 行列の分解型に関しては, 次の系が得られる.
系 1.

ベクトル

$s$

.

$\approx\in R^{n}$は $s^{T}\approx>0$ を満たすとする.

(2.4)$N_{+}$

で与えられる行列$N_{+}\in R^{m\mathrm{x}}$の–般解になる. ただし,

”

このとき

$=$

$(I- \frac{\Phi su^{T}}{s^{T}\Phi\tau u})\Phi+\frac{uz^{T}}{\sqrt{s^{T}\approx}||u||}$$=$$\Phi-\frac{\Phi su^{T}\Phi}{s^{T}\Phi^{T}u}+\frac{u_{\wedge}^{\sim^{T}}}{\sqrt{s^{T}z}||u||}$は行列方程式$n\leq\prime m$$N_{+}^{T} \frac{\sqrt{s^{T}z}u}{||u||}$

$=$

$z$

$N_{+}s$$=$$\frac{\sqrt{s^{T}z}u}{||u||}$であり,$\Phi\in R^{m\mathrm{x}n}$と $u\in R^{m}$ は $s^{T}\Phi^{T}u\neq 0$ を満たす任意行列と任意ベクトルである.

(証明は略す.)この結果を用いて $B+=N_{++}^{T}N$ とおけば, SSP 行列の–般形が得られる. すなわち,$\Delta\backslash \prime r_{+}^{T}N_{+}$

$=$

$=$

$H_{+}=B_{+}^{-1}$

(25)

に対応する

$[(I- \frac{\Phi su^{T}}{s^{T}\Phi^{T_{u}}})\Phi+\frac{uz^{T}}{\sqrt{s^{T}z}||u||}]^{T}[(I-\frac{\Phi_{S?}\lrcorner\tau}{s^{T}\Phi^{\tau_{u}}})\Phi+\frac{uz^{T}}{\sqrt{s^{T_{\mathit{4}}}}||u||}]$$(I- \frac{su^{T}\Phi}{s^{T}\Phi^{T_{u}}})^{T}C(I-\frac{su^{T}\Phi}{s^{T}\Phi^{\tau_{u}}})+\frac{\sim\gamma z^{T}}{s^{T_{\mathcal{Z}}}}$$-\mathrm{H}\mathscr{H}$.

も, 同様に導出できる. この場合, SSP 条件の–番目は次式で置き代わる.
$H_{+}z=s$

.

195

このとき, いままでと同様の議論をすれば, SSP 条件を満足する $H+$ の–般形とその分解型が得られる :$H_{+}$$(2.6^{-}\grave{)}$$\tilde{C}-\frac{\tilde{c}_{zz^{T}}\tilde{c}}{z^{T}\overline{C}z}+\frac{ss^{T}}{z^{T_{S}}}+(z^{\tau_{\tilde{C}}}z)\tilde{w}\tilde{w}^{T}$$=$.
$(I- \frac{z\tilde{u}^{T}\tilde{\Phi}}{z^{T}\tilde{\Phi}^{\tau_{\tilde{u}}}})^{T}\tilde{C}(I-,\frac{z\tilde{u}^{T}\tilde{\Phi}}{\sim^{T}\tilde{\Phi}^{T}\tilde{u}})+\frac{ss^{T}}{s^{T_{\mathcal{Z}}}}$

$=$

ただし

,

$\overline{C}^{\mathrm{v}}=\overline{\Phi}^{\tau}\overline{\Phi}$$\overline{w}=\frac{\Phi^{\tau_{\overline{u}}}}{z^{T}\tilde{\Phi}^{T_{\overline{u}}}}-\frac{c_{z}}{z^{T’}\tilde{C}z}$(2.7)$\tilde{N}_{+}$$=$$(I- \frac{\overline{\Phi}z\tilde{u}^{T}}{z^{T}\tilde{\Phi}^{T_{\overline{u}}}}\mathrm{I}^{\overline{\Phi}}+\frac{\tilde{u}s^{T}}{\sqrt{s^{T}\sim}||\tilde{u}||}$,$= \overline{\Phi}-\frac{\overline{\Phi}z\tilde{u}^{T}\tilde{\Phi}}{z^{T}\tilde{\Phi}^{T_{\tilde{u}}}}+\frac{\tilde{u}s^{T}}{\sqrt{s^{T}z}||\tilde{u}||}$

ただし,$\overline{\Phi}$

は列フルランクな任意行列, 名は,を満たす任意ベクトルである. 逆行列の形式を用$z^{T}\overline{\Phi}^{T_{\overline{u}}}\neq 0$

いれば, 探索方向は直接$d_{k}=-H_{k}\nabla f(x_{k})$から求まり, 線形方程式を解く必要がない.

セカント法

3

本節では, 素 (制約最小化問題を解くためのセカント法を扱う. この方法は, アルゴリズム [NL] の Step 4を更新して得るもので, その際にセカント条件 (1.2) を満たすこのヘッセ行列の近似行列 $B_{k+1}$ を現在の
$B_{k}$とが要請される. –般形 (2.1), (2.4) を用いれば, SSP 条件を満足する BO 更新公式とその分解型が得ら.
,$=y_{k},$と (2.4) で $s=s_{k}$ ,
れる. 式
$,$

$(^{-}\underline{)}.1)$$\Phi=L_{k}\in R^{n\cross \mathcal{R}}$$\perp \mathrm{v}_{+}=L_{k+1},$.

$B_{k}$$=L_{k}^{T}L_{k}$$B_{k+1}=L_{k+1}^{T}L_{\lambda\cdot+1}$とおけば, 次の形式が得られる :

.

(3.1)

$B_{k+1}=B_{k}- \frac{B_{k^{S}k^{S}}TB_{k}k}{s_{k}^{T}B_{k^{S}k}}+\frac{?/ky^{\tau}k}{s_{k}^{T}yk}+(s_{k}B_{k}\tau\tau Sk)w_{k^{w_{k}}}$

.

(3.2)

ただし,
(

$L_{k+1}=L_{k}- \frac{L_{k^{S}k}u_{k}^{\tau}L_{k}}{s_{k}^{T}L_{k^{u_{k}}}T}$$+ \frac{1}{\sqrt{s_{k}^{\tau}y_{k}}}\frac{u_{k}}{||u_{k}||}y_{k}^{T}$$u_{k}$

は$s_{k}^{T}L_{k}\tau u_{k}\neq 0$,を満たす任意のベクトルで,$w_{k}= \frac{L_{k}^{\tau_{u_{k}}}}{s_{k}^{T}L_{k}^{\tau}u_{k}}-\frac{B_{k^{S}k}}{s_{k}^{T}B_{k^{S_{k}}}}.\cdot$$3.3_{\grave{J}}$式 (3.1) は正定値対称なセカント法のクラスで, パラメータベクトル $u_{k}\in R^{n}$ を含んでいる. そして (3/.2)
はその分解型である. ここで, 行列 (3.1) はランクが高々 3 の補正項をもっていることに注意しよう. 特別”は正則であると仮定する.
なを選べば, ランクが 2 の更新公式になる. 本節を通して行列$L_{k}\in R^{n\mathrm{x}}$$u_{k}$

3.1

Broyden 公式族

パラメータ $\phi_{k}\geq 0$ に対して
$u_{k}=(1- \sqrt{\phi_{k}})\frac{L_{k^{S}k}}{s_{k}^{T}B_{k}s_{k}}+\sqrt{\phi_{k}}\frac{(L_{k}^{\tau})-1_{y_{k}}}{s_{k}^{T}yk}$$(.3.4\grave{\mathit{1}}$196

とおくと, 一般形 (3.1) と (3.2) から Broyden 公式族とその分解型が得られる :(3.5)$B_{k+1}^{B\circ}ryden=B_{k}- \frac{B_{k^{S_{k}s_{k}^{\tau_{B_{k}}}}}}{s_{k}^{T}B_{k^{S}k}}+\frac{y_{k}y_{k}^{T}}{s_{k}^{T}yk}+\phi_{k}(_{S_{k}}\tau_{B_{k}k})sv_{k}v^{T}k$’(3/.6)$v_{k}= \frac{y_{k}}{s_{k}^{T}y_{k}}-\frac{B_{k^{S}k}}{s_{k}^{T}B_{k^{S_{k}}}}$(.3.7)$=$$L_{k+1}^{B\mathit{7}\mathrm{o}y\mathrm{e}}dn$,$L_{k}+(1- \sqrt{\varphi_{k}})(\frac{L_{\lambda^{S}k}}{s_{k}^{T}B_{k^{S_{k}}}}.)(\sqrt{\lambda_{k}}y_{k}-B_{k^{S}k})^{\tau}$$+ \sqrt{\phi_{k}}L_{k}(\sqrt{\lambda_{k}}B^{-1}ykk-s_{k})(\frac{?jk}{s_{k}^{T}y_{k}})^{T}$

ただし,$\phi_{k}\geq 0$,

であり$\lambda_{k}=[(1-\phi_{k})\frac{s_{k}^{T}y_{k}}{s_{k}^{T}B_{k^{S}k}}+\emptyset k\frac{y_{k}^{\tau_{B_{k}^{-}}1}y_{k}}{s_{k}^{T}y_{k}}]-1$である. 特別な$()_{\wedge}(3.7)$で軌を選べば BFGS 公式や DFP 公式 およびそれらの分解型が得られる. すなわち, 式 (3.5)$\phi_{k}$とおけば BFGS 公式とその分解型が得られる. また同様に, 式$=0$$(3_{\circ}^{\zeta}..)$と (3.7) で\mbox{\boldmath $\phi$}k $=1$とおけば DFP 公式とその分解型が得られる.
もし$B_{k}$

が正定値対称で $s_{k}^{T}y_{k}>0$ が成り立ち, かっ(3.8)$\phi_{k}>\phi_{k}^{\#}=-(\frac{(s_{k}B_{k^{S)}}T.(y_{k}\tau_{B_{k}yk}k)-1}{(s_{k}^{T}y_{k})^{2}}-1)^{-1}$となる$t^{)}k$を選べば, Broyden 公式族 (3.5) が正定値対称になることが知られている. もし立ならば,$\phi_{k}^{\#}<0$

たが, 実際は

3.2が線形独となることに注意しよう. パラメータに対する Broyden 公式族の分解型を前述しに対して分解型が得られることが期待される. これについては, 今後の課題である.
$s_{k}$と$y_{k}$$\phi_{k}\geq 0$$\phi_{k}>\phi_{k}^{\#}$

局所的超–次収束性

本節では, セカント法のクラス (3.1) あるいは (3.2) の, 局所的超–次収束性を示す定理を与える.
$D\subset R^{n}$を開学集合とし, $f(x)$ の局所最適解 を含むものとする. $f(x)$ は以下の仮定を満たすものと$x_{*}$する.

(A1) 任意の $x\in D$ に対して, 次の条件を満たす正定数(3.9)$\{\mathrm{A}2)\nabla^{2}f\}\mathrm{h}x_{*}$

$\xi$

と

$P$

が存在する.

$||\nabla^{2}f(x)-\nabla^{2}f(x*)||\leq\xi||x-x_{*}||^{p}$で正定値対称である.

また, 行列 $Q$ に対して $||Q||F$ は Frobenius ノルム, $||Q||F,M=||M^{-1}QM-1||_{F}$ とする.

このとき, 以下の結果を得る.

定理 2. 仮定 (A1) および (A2) が満たされているとし,とがこのとき, 正の定数があって,$\eta_{1}$(3.10)$\eta_{2}$$B_{k}$は (3.1) によって更新されるものとする.

$u_{k}$$||(s_{kk}^{\tau_{B}\tau}ks)(w_{kk}w-v_{k}v_{k}^{T})||F,M \leq\eta_{1}\frac{||^{\wedge}s_{k}-\hat{B}_{k^{S}k}\wedge||^{2}}{||_{S_{k}}^{\wedge}||^{2}}+\eta_{2}\sigma_{k}^{\mathrm{p}}$197を満足するものとする. 点列$\{x_{k}\}$(3.11)

は,$x_{k+1}=x_{k}+s_{k}$によって定義されるものとする.
このとき, 任意の $\nu\in(0,1)$ に対して, 正定数$B_{k}s_{k}=-\nabla f(x_{k})$と$\epsilon$$||x_{0^{-X_{*}}}||\leq\epsilon$$\delta$,.

が存在して,$x_{0}\in D$

および,$||B_{0}-\nabla^{2}f(X_{*})||_{F,M}\leq\delta$

であれば, 点列$\{x_{k}\}$は$x_{*}$に超–次収束する.

ここに,(3.12)$M=\nabla^{2}f(x_{*})2\mathrm{L}$および$\sigma_{k}=\max(||x_{k+1}-X_{*}||, ||x_{k}-x_{*}||)$ ,(3.13)
さらに$\hat{B}_{k}=M^{-1-1}B_{k}M$(3.14),$\hat{B}_{k+1}=M^{-1}B_{k+}1M-1$$\wedge s_{k}=Ms_{k}$

.

である.

証明は省略するが, Broyden-Dennis-Mor\’e の収束条件 [2] および,$\mathrm{D}\mathrm{e}\mathrm{l}\mathrm{t}1\lfloor \mathrm{i}\mathrm{s}_{-}\mathrm{M}\circ \mathrm{r}\acute{\mathrm{e}}$の超–次収束のための条件 [3] を満たすことが示される.
を持つ Broyden 公式族は, (3.1) あるいは (3.2) に含まれ, かっ定理 2 の条件
また, 非負のパラメータ$\phi_{k}$を満たす.

SSP 変換とその応用例4与えられた任意の正定値対称行列 を SSP 行列に変換する作用素ともみなすことができる. そこで我々は, 式 (2.1) を SSP 変換と呼ぶことにし, $S’SP(c, s, Z, u)$ と表すことにする. このとき,
-般形

$s,$

$\approx$$(2.\perp)$

は,

$C$

は与えられたベクトル,

以下では,

4. 1

$u$

}まパラメータである.

この変換を用いた例を 4 っ取り上げる.

$–=$ 一トン法

アルゴリズム [NL] において,$B_{k}=\nabla^{2}f(x_{k})$とおくと, ニュートン法となる.

$–\mathrm{I}-$トン法の場合,が正定値でないとき, あるいは解析的に計算が困難なときアルゴリズムの継続に支障となる. そI を正定値にを用いると,
が正定値でなくなった場合, 適当なこで, 例えばすることができる. このとき, S’SP $(C, S, z, \prime u.)$ において $C=\nabla^{2}f(x_{k})+\lambda_{k}I,$ $c=L^{\tau}L,$ $s_{k}-1=x_{k}-x_{k}-1$ ,$\nabla^{\underline{\prime r}}/f(x_{k})$$\lambda_{k}>0$$\nabla^{2}.f(x_{k})$および $yk- l=\nabla f(x_{k})-\nabla f(x_{k-1})$ とおくと,$s_{k-1}^{T}y_{k}-1>0$$\nabla^{2}f(x_{k})+\lambda_{k}$のとき, セカント条件を満たしかっ安定なア

ルゴリズムが得られる.
(4.1)$B_{k}$$=$$=$$SSP(C, S_{k-}1, yk-1, \frac{Ls_{k-1}}{S_{k-}^{T}{}_{1}Csk-1})$.

$\nabla^{2}f(X_{k})+\lambda kI-\frac{(\nabla^{2}f(x_{k})+\lambda_{k}I)S_{k}-1s_{k}T-1(\nabla 2f(Xk)+\lambda_{k}I)}{s_{k1}^{T}-(\nabla^{2}f(x_{k})+\lambda kI)sk-1}+\frac{y_{k-1}y_{k-}^{\tau}1}{s_{k-1}^{T}yk-1}$

198

また, ヘッセ行列 $\nabla^{2}f(x)$ が計算可能部分 $P(x)$ と, 解析的に計算することが困難な部分 $E(x)$ の和で与えられるとき, すなわち $\nabla^{2}f(x)=P(x)+E(X)$ と書ける場合, 適当な$\lambda_{k}\geq 0$を用いると,$P(x_{\lambda}.)+\lambda_{k}I$を正定{直にすることができる. このとき, $SSP(C, S, z, u)$ において $C=P(x_{k})+\lambda_{k}I,$ $C=L^{T}L,$ $s_{k-1}=x_{k}-Xk-1$ ,および $y_{k-1}=\nabla f(x_{k})-\nabla f(X_{k-}1)$ とおくと, $s_{k-1}^{T}yk-1>0$ のとき, セカント条件を満たしかっ安定なアルゴ ) ズムが得られる.
$\dagger$

(4.2)

4.2

$B_{k}$$=$$SSP(C, sk-1, y_{k}-1, \frac{Ls_{k-1}}{s_{k-}^{T}{}_{1}Cs_{k-}1})$$=$$P(X_{k})+ \lambda kI-\cdot\frac{(P(_{X_{k})+\lambda I)s_{k,-}}k1^{S_{k}}-1(TP(X_{k})+\lambda_{k}I)}{s_{k1}^{T}-(P(xk)+\lambda_{k}I\mathrm{I}s_{k-}1},+.\frac{y_{k-1}y_{k-}^{\tau}1}{s_{k-1}^{T}y_{k}-1}$.

スパース構造を持つ準 $–>$ 一トン法

大規模な無制約最適化問題に準ニュートン法を適用する場合,のサイズが大きくなる. このとき, 通常のセカント法の公式で得られる
は密行列であり, ある程度以上のサイズになると記憶容量がデッ ド
ロックとなる. 他方, 大規模な問題では, ヘッセ行列がスパ– ス構造を持つことが\dashv 貨的であるので,$B_{k}$$B_{k}$$B_{k}$にヘッセのスパ一ス構造を持たせるような公式が考えられた. $[9][11]$しかしながら, これらの . は正定値性が保証されない. 今のところ, スパース構造と正定値性を両立させる公式は発見されていない. そこで, SSP 変換を用いて正定値を保証するスパース準–I 一トン法の導出を試みる.
を, スパース公式によって得た行列とする. このとき, 適当な
に対して,
を正定値
と出来る. したがって, 例えば $SSP(C, S, z, u)$ において,, とおくと,$B_{k}$$\tilde{B}_{k}$$\overline{B}_{k}+\lambda_{k}I$$\lambda_{k}>0$$C’=\tilde{B}_{k}+\lambda_{k}I$(4.3)$B_{k}$$=$$SSP(c, s_{k}, y_{k}, u)$$=$$C- \frac{Cs_{k}s_{k}CT}{s_{k}^{T}C\prime S_{k}},$$+ \frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}+s_{k}^{\tau T}CS_{k}ww$

.

ただし,

が得られる.

$w$

$=$

$C$

$=$

$\frac{\Phi^{T}u}{s_{k}^{T}\Phi^{\tau_{u}}}-\frac{Cs_{k}}{s_{k}C^{\mathrm{Y}}sk}$,$\Phi^{T}\Phi$

ここで $u=\Phi s_{k}$ および\Phi Tu $=y_{k}$ とおけば,それぞれ, BFGS 型形式と DFP 型形式が得られる.

(4.3) そのものはスパースではないが, 方程式(4.4)$B_{k}d=-\nabla f(x_{k}.)$は, BFGS 型公式や DFP 型公式を適用し, SOR 法などの反復法を用いることにより,他にベクトル$s_{k}$と$y_{k}$の 2 本を用意するだけで解くことができる. ただし,$\lambda_{k}$スパ– ス行列 $C$ のをどうやって決定するかは,今後の課題である.

4.3

Limited memory 法

limited memory 法は, 大規模な無制約最適化問題を解くために Nocedal [7] らによって提案された方法をである. この考え方は, ヘッセ行列の逆行列で近似することに基づく. 本節では, この方法を SSP 変換の立場から統–的にながめてみたい.
$\nabla^{2}f(x_{k})^{-1}$$H_{k}$

199

式 (2.6) で $z=y_{k}$ とおけば, 次の–般形を得る :(4.5)$H_{k+1}$

$=$

$=$

$SSP(\tilde{\Phi}^{T}\tilde{\Phi}, yk, Sk,\tilde{u})$.

$(I- \frac{y_{k}\overline{u}_{k}^{T}\overline{\Phi}}{y_{k}^{T}\tilde{\Phi}^{\tau}\overline{u}k})^{\tau_{\tilde{\Phi}\tilde{\Phi}}}\tau(I-\frac{y_{k}\tilde{u}_{k}^{\tau}\overline{\Phi}}{y_{k}^{T}\tilde{\Phi}^{T}\tilde{u}k})+\frac{s_{k}s_{k}^{T}}{y_{k}^{T}s_{k}}$初期行列が, 次のように分解型で与えられていると仮定する.
$H_{0}=L_{0\dot{0}}^{\tau_{L}}$

このとき, あらかじめ定められた数$t$,$L_{0}\in R^{n\cross n}$

.

に対して,

(4.6)

$\mathcal{V}_{k}^{r}=I-\frac{y_{k}\overline{u}_{k}\overline{\Phi}T}{y_{k}^{T}\tilde{\Phi}^{\tau}\overline{u}k}$および$\overline{\Phi}=$$(4.l -)$$\in R^{(n+t)\cross}n$とおくと,$(4.\overline{\mathfrak{d}}\grave{)}$$H_{k+1}$$=$$(v^{r}k-tVk-l+1^{\cdot}..

V_{k-1}\mathrm{t}_{k}’/)^{\tau}H0(l\gamma_{k-}V_{k-}tt+1^{\cdot}$$+(V_{k-t+}1V_{k}-t+2 ^{\cdot}..

..

$V_{k-1}V_{k\mathrm{I}}$V_{k-1}V_{k}.)^{T} \frac{s_{k-t}s_{k}\tau-t}{s_{k-t}^{T}yk-\mathrm{e}}(V_{k-t+}1V_{k}-r+2^{\cdot}.

.

V_{k-1}V_{k})$$+ \cdots+(V_{k-1}V\lambda\cdot)T_{\frac{s_{k-2^{S}.2}k-T}{s_{k-2}^{T}y_{k-}2}}(Vk-1Vk)+VT\frac{s_{k-1}s_{k-}\tau 1}{s_{k-1}^{T}y_{k-}1}k.kV+\frac{s_{k}s_{k}^{T}}{s_{k}^{T_{?j}}k}$.

を得る. この結果から,に含まれる $2(t+1)$ 本のベクトル $s.,$$d_{k+1}=-H_{k+1}\nablaf(X_{k+1})$
けば, 探索方向はとして得られる.
ただし, $k\leq t$ の場合には, 上式は$V_{k-t},$ $\ldots.V_{k}$$\mathrm{t}_{\backslash }’4.(\mathrm{L})^{\backslash }J$$H_{k+1}$$=$$(V_{0}V_{1} ...

\iota_{}’r_{k-1}Vk)^{T}H_{0}(l/^{\tau}0^{V_{1}} ...

$+(V_{1}V_{\mathrm{Q},\wedge} ...

$y_{i},$$i=k-t,$$\ldots$

V_{k-1}V_{k})$l^{r_{\lambda\cdot-1}}/V_{k})^{\tau} \frac{s_{0}s_{0}^{\tau}}{s_{00}^{\tau_{y}}}(\mathrm{t}’1V2 ^{\cdot}..

V_{k-1}V_{k})+$$\cdot$:.

$+(V_{k-1k}V)^{\tau_{\frac{s_{k-2^{S_{k-}^{T}}}2}{s_{k-2}^{T}y_{k2}\sim-}}}(V_{k-}1V \mathrm{t}.)+Vk\frac{s_{k-1^{S}1}k-T}{s_{k-1}^{T}y_{k}-1}Vk\tau.+\frac{s_{k^{S_{k}}}\tau}{s_{k}^{T}y_{k}}$:$k$を保存してお

200

とみなす.

もし $\Phi^{T}u_{k}=s_{k}$ を満たす

$u_{k}$を選んで $t=k$ とおけば, 行列$H_{k}$と $H_{k+1}$ の関係は次のようになる$V_{k}^{T}H_{k}V_{k}\perp_{\frac{s_{k}s_{k}^{T}}{T}}$$H_{k+1}$$–\kappa\tau\perp$

$=$
$-$

$\cdot$$k–\kappa\cdot\kappa$$s_{k}^{T}y_{k}$$=$$(\prime 4.10)$$H_{k}- \frac{H_{ky_{k^{S_{k}+}}y_{k}k}\tau\tau_{H}Sk}{s_{k}^{T}y_{\lambda}}+(1+\frac{y_{k}^{T}H_{kyk}}{s_{k}^{T}y_{k}})\frac{s_{k}s_{k}^{T}}{s_{k}^{T}y_{k}}$,ただし$V_{k}=I- \frac{y_{k}s_{k}^{T}}{s_{k}^{T}y_{k}}$実は, この式は BFGS 公式である.

提案された$1\mathrm{i}_{\mathrm{I}}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{d}$

したがって,$\Phi^{T}u_{k}=s_{k}$の場合には, 以上の方法は Nocedal によってmemory BFGS 法になる. また, いろいろな

nlelnory 法が得られるてのを選べば, いろいろな種類の limited(ただし, 形式的に定式化できるという意味であって, 必ずしも計算機の記憶容量が大幅に節約できるような実用性をもっているとは限らない).
$i$$u_{k}$に対して $s_{1}^{T}y;>0$ が成り立ち,$\text{か}\prime\supset \text{行列}\overline{\Phi}$

なお, 初期行列が列フルランクならば,$(4.\overline{8})$が正定値対称で, すべおよび (4.9) で定義される$H_{0}$

行列は SSP 条件を満足することが証明できることを注意しておく.

44

非線形最小 2 乗問題に対する Gauss-Newton 法

本節では, 次の非線形最小 2 乗問題を扱う.

(4.11)$f(x)= \frac{1}{2}.\sum^{\nu}(r_{j}.(x))2\text{を最ノ}\mathrm{J}\backslash 4\mathrm{b}\text{せ}\mathrm{x}(n\leq\nu)$,$J^{=1}$

ただし,$r_{j}$:$R^{\iota}’arrow R,$$j=1,2,$$\ldots,$$\nu$は非線形関数である. 以下では, 残差ベクトルを$r\cdot(x)=(\mathit{7}1(x), \ldots, \gamma_{\nu}(_{X}))\tau$と表す. 以上の問題では, 目的関数の勾配ベクトルとヘッセ行列は特別な構造をもっていて,,$(\prime 4.12)$$\nabla f(x)=\mathit{1}(x)^{\tau_{r}}(x)$(4.13)$\nabla^{2}f(x)=J(x)^{T}J(X)+\sum r_{j}(x)\nabla 2rj(x)$$j=1$となる. ただし,$J(x)$ は残差ベクトル $r(x)$ のヤコビ行列である.

このとき, ヘッセ行列$\nabla^{2}f(x)$の第 1 項は 1 階偏導関数の情報しかもっていないのに比べて, 第 2
は 2 階偏導関数の情報を含んでいるので, 計算の手間がかかる.
そこで, ヘッセ行列の第 2 項を無視して, アルゴリズム [NL] で $B_{k}=J(x_{k})^{T}J(x_{k})$ とおいた解法が考えられる. これが Gauss-Newton 法である. この方法は, 次の線形方程式の解を探索方向 . とするもので$J(\backslash ?’)^{T}J(X)$$\text{項}\sum_{j=}^{\nu}1r_{j}(x)\nabla\gamma\sim\gamma_{j}(x)$$d_{\lambda}.$ある(4.14)$J(x_{k})^{\tau}J(x_{k})d=-J(x_{k})^{T}7^{\cdot}(Xk)$.

一般に, Gauss-Newton 法は残差がゼロもしくは非常に小さい問題に対しては効率がよいが, 大きな問題に対しては効率が悪くなることがあることが知られている. これは, ヘッセ行列の第 2 項を無視したことによる. この問題を解決する方法として, SSP 変換を Gauss-Newton 法に適用することが考えられる. このとき変換されてできあがった行列は, 正定値対称性を保存し, かっ, ヘッセ行列

報をもっている.

したがって,の第 2 項の情
こうして修正された方法は $J(x_{k})^{T}J(xk)$ よりもヘッセ行列の情報をより多$\nabla^{\gamma}\sim f(X)$201

くもっており, その結果として, Gauss-Newton 法よりも効率が上がることが期待される. 以上の目的のために,$\mathrm{D}\mathrm{e}\mathrm{n}\mathrm{r}\iota \mathrm{i}\mathrm{s}[4]$によって導出された次のセカント条件を考えよう(4.15)$B_{k^{S}k-1}=z_{k-l}$

,

ただし,

(4.16)$z_{k-l}=J(x_{k})^{T}J(x_{k})S_{k-}1+(J(x_{k})-J(x_{k1}-))^{\tau_{r(X}}k)$.

この条件はテイラー展開の 1 次近似$(J(x_{k})^{\tau}J(X_{k})+ \sum_{j=1}^{\nu}7^{\cdot}j(xk)\nabla^{2}\gamma_{j}(Xk)\mathrm{I}s_{k-1}\approx J(X_{k})^{T}J(xk)S_{k1}-+(J(x_{k})-J(x_{k1}-))^{T}r(xk)$から導かれる.

もしヤコビ行列 $J(x_{k})$ が列フルランクならば, 行列 $J(x_{k})^{\tau}J(x_{k})$ は正定値対称になるので, SSP 行列の一般形で $B_{k}=L_{k}^{T}L_{k}$ とおける. よって, (2.1) と (2.4) において
$B_{+}=B_{k}$,$N_{+}=N_{k}$,$\Phi=J(x_{k})$,$s=s_{k-1}$,$z=z_{k-1}$とおけば, 次式が得られる :$B_{k}$$(4.17_{)^{\backslash }}$

$=$

$=$

$sSP(J(x_{k})^{T}J(Xk), sk-1, \mathcal{Z}k-1, u)$,$J(X_{k})^{\tau}J(X_{k})- \frac{J(X_{k})^{\tau_{p_{k}p_{k}^{T}}}-1-1J(x_{k})}{||p_{k}-1||2}+\frac{z_{k-1^{\approx_{k-}}}T1}{s_{k-1}^{T}\mathcal{Z}_{k}-1}+||pk-1||^{2\tau}w_{k}-1w_{k-1}$$(4.1\hat{\mathfrak{d}})$$L_{k}=J(x_{k})- \frac{p_{k-1}uJ\tau(x_{k})}{p_{k-1}^{T}u}+\frac{uz_{k1}^{\tau}-}{\sqrt{s_{k-1}^{T}Z_{k}-1}||u||}$,ただし, $Pk- l=J(x_{k})sk-1$ ,$w_{k-1}= \frac{J(x_{k})^{T}u}{p_{k-1}^{T}u}-\frac{J(x_{k})\tau p_{k-}1}{||p_{k-1}||^{2}}$である.

ここで $u=pk-1$ および $J(x_{k})^{T}u=Z_{k1}-$ とおけば,それぞれ, BFGS 型形式と DFP 型形式が得られる: 上記の BFGS 型形式と DFP 型形式は, それぞれ Al-Baali and Fletcher [1] (もしくは Denltis et al.

[5] も参照) によって提案された GN-BFGS 法と GN-DFP 法に相当する.
形式族 (4.17) を用いた解法に関する好ましい性質については, $[10]$ を参照されたい.

5

おわりに
本稿では, 安定な準– $=.-$ トン法というクラスを規定し, SSP 行列の\dashv \star 形を導出することによって包括的な定義に成功した.
SSP 行列は, 多くの示唆を含む形式をしている. 例えば Broyden 公式族との密接な関係より, 準-\check $L^{-}$
トン法の基本的な性質の体系化, あるいは解明に, 上の–般形は大きな意味を持つものと期待される. 4
章で示されたいくつかの応用の内, 例えば, 大規模な非線形最適化問題に対する準– . 一トン公式の導出
が, 興味ある結果である. 大規模問題に対して今後注目されるであろう手法の–つとして, スパ– ス構造の構成が挙げられる. そのとき本稿で提案された公式は, これまで困難とされていた正定値性とを持つ
セカント条件の両立という意味で重要である. また, Limited memory 法が, このクラスの例として導出$-\ovalbox{\tt\small REJECT}$$B_{k}$

されることも, 新しい手法の導出の方法論として注目される.

今後,
あろう.

ここで示されたクラスのより統–的体系化の研究が, 準–n– トン法の発展に大きく寄与するで

202

参考文献
[1] M.Al-Baali and R.Fletcher, Variational methods for non-linear least squares, Journal of th Operational Research Society 36 (1985) 405-421.
$e$

[2]

$\mathrm{C}.\mathrm{G}$Ne[3]. Broyden,$\iota \mathrm{v}\mathrm{t}\mathrm{o}\mathrm{n}$. Dennis, Jr. and. Mor\’e , On the local and superlinear convergence of quasimethods, Journal of the Institute of Mathematics and its Applications, 12223-245.
$\mathrm{J}.\mathrm{E}$$\mathrm{J}.\mathrm{J}$$(1\subset \mathrm{J}73)$. Dennis, Jr. and. Mor\’e , A characterization of superlinear convergence and its application
to quasi-Newton methods, Mathematics of , omputation, 28 (1974) 549-560.

$\mathrm{J}.\mathrm{E}$$\mathrm{J}.\mathrm{J}$

$C$

[4]

$\mathrm{J}.\mathrm{E}$.Dennis,Jr., A brief survey of convergence results for quasi-Newton methods, SIAM-AMS’ Pro-

ceedings, 9 (1976) 185-199.

[5].Dennis,Jr., S.Sheng and.Vu, A memoryless
Gauss-Newton mcthod forleast-squares problems, Technical Report 85-1, Department of Mathematical Sciences, Rice Univer$\mathrm{J}.\mathrm{E}$$\mathrm{P}.\mathrm{A}$$1\mathrm{L}\mathrm{o}\mathrm{n}\mathrm{l}\mathrm{i}_{1}\mathrm{L}\mathrm{c}\mathrm{a}\Gamma$$\mathrm{a}\mathrm{u}\mathrm{g}\mathrm{m}\mathrm{e}\mathrm{n}\uparrow_{arrow}\mathrm{e}\mathrm{d}$sity: Texas. USA (1985).
$[\mathrm{t}_{)}]$$[\overline{(}]$

J.L.NazarctlL. The Ncwtolt and Cauchy perspectivcs olt computational lLol\downarrow lillcar optimizdtiolt.
SIAM Review. 36 (1994) 215-225.
J.Nocedal, Updating quasi-Newton matrices with limited storage, Mathematics of $C’ ompubatio’\iota,$ $35$
(1980) 773-782.

$[i^{-}>]$

J.Nocedal, Theory of algorithms for unconstrained optimization, Acta Numerica (Cambridgc Uni-

versity Press, Cambridge, 1992) 199-242.
[9] Ph.L.Toint,$\mathrm{O}_{1}\iota$

sparse and symmetric matrix updating subject to a linear equation, Mathematics$()f(’ 0\prime l\mathit{1}pututi\mathrm{o}\uparrow \mathit{1},31 (1977)$$[\perp 0]$773-782.

H.Yabe and N.Yamaki, A modification of Gauss-Newton metILod forlelns, RIMS Kokyuroku, 880 (1994) 202-210.

$\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{l}\mathrm{i}\mathrm{l}\lfloor \mathrm{e}\mathrm{a}\mathrm{r}\mathrm{l}\mathrm{c}\mathrm{a}\mathrm{S}\dagger_{\mathrm{D}}$squares prob-[11] H.Yabe , S.Takahashi and N.Yamaki, Secant updates of quasi-Newton methods for solving sparse
nonlinear equations, $TRU$ Mathematics , 19, 1 (1983) 75-87.