コンパクトな準ニュートン表現
Matrix decomposition

準ニュートン法のコンパクト表現は行列分解であり、勾配に基づく最適化アルゴリズムや非線形システムの解法に典型的に用いられます。この分解では、非線形システムの直接ヘッセ行列および／または逆ヘッセ行列、あるいはヤコビ行列に対して低ランク表現が用いられます。そのため、コンパクト表現は大規模な問題や制約付き最適化によく用いられます。

密なヘッセ近似のコンパクト行列分解
稠密ヘッセ近似（左）のコンパクト表現（右）は、初期行列（通常は対角行列）と低ランク分解を組み合わせたものである。メモリ使用量（網掛け部分）が小さく、効率的な行列計算を可能にする。

意味

非線形目的関数の逆ヘッセ行列または直接ヘッセ行列に対する準ニュートン行列のコンパクト表現は、階数1または階数2の再帰的な行列更新のシーケンスを、初期行列の階数または階数更新として表現する。 [1] [2] これは準ニュートン更新から導出されるため、定義において 反復回数と勾配の差を用いる。特に、またはに対して、長方形行列 と正方対称システムはのに依存し、準ニュートン表現を定義する。 H k {\displaystyle H_{k}} B k {\displaystyle B_{k}} f ( x ) : R n → R {\displaystyle f(x):\mathbb {R} ^{n}\to \mathbb {R} } k {\displaystyle k} 2 k {\displaystyle 2k} ∇ f ( x k ) = g k {\displaystyle \nabla f(x_{k})=g_{k}} { s i − 1 = x i − x i − 1 , y i − 1 = g i − g i − 1 } i = 1 k {\displaystyle \{s_{i-1}=x_{i}-x_{i-1},y_{i-1}=g_{i}-g_{i-1}\}_{i=1}^{k}} r = k {\displaystyle r=k} r = 2 k {\displaystyle r=2k} n × r {\displaystyle n\times r} U k , J k {\displaystyle U_{k},J_{k}} r × r {\displaystyle r\times r} M k , N k {\displaystyle M_{k},N_{k}} s i , y i {\displaystyle s_{i},y_{i}}

H k = H 0 + U k M k − 1 U k T ,  and  B k = B 0 + J k N k − 1 J k T {\displaystyle H_{k}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},\quad {\text{ and }}\quad B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T}}

アプリケーション

特殊な行列分解のため、このコンパクトな表現は最先端の最適化ソフトウェアに実装されています。[3] [4] [5] [6] メモリ制限技術と組み合わせると、勾配を伴う制約付き最適化の一般的な手法となります。[7]行列ベクトル積、求解、固有値分解などの線形代数演算を 効率的に実行できます。直線探索法や信頼領域法と組み合わせることができ、この表現は多くの準ニュートン更新のために開発されています。たとえば、直接準ニュートンヘッセ行列と任意のベクトルとの行列ベクトル積は次のようになります。 g ∈ R n {\displaystyle g\in \mathbb {R} ^{n}}

p k ( 0 ) = J k T g solve N k p k ( 1 ) = p k ( 0 ) ( N k  is small) p k ( 2 ) = J k p k ( 1 ) p k ( 3 ) = H 0 g p k ( 4 ) = p k ( 2 ) + p k ( 3 ) {\displaystyle {\begin{aligned}p_{k}^{(0)}&=J_{k}^{T}g\\{\text{solve}}\quad N_{k}p_{k}^{(1)}&=p_{k}^{(0)}\quad \quad {\text{(}}N_{k}{\text{ is small)}}\\p_{k}^{(2)}&=J_{k}p_{k}^{(1)}\\p_{k}^{(3)}&=H_{0}g\\p_{k}^{\phantom {(4)}}&=p_{k}^{(2)}+p_{k}^{(3)}\end{aligned}}}

背景

GMRES法の文脈において、ウォーカー[8]はハウスホルダー変換（恒等行列と階数1） の積がコンパクトな行列式として表現できることを示した。これにより、恒等行列と階数1の積の明示的な行列式が導出された。[7] 具体的には、 および のとき 、階数1 の更新の積から恒等行列への積はである。BFGS 更新は、の積で表現でき、コンパクトな行列式を持つ。したがって、 BFGS再帰はこれらのブロック行列表現を利用できる。 k {\displaystyle k} S k = [ s 0 s 1 … s k − 1 ] , {\textstyle S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots s_{k-1}\end{bmatrix}},}   Y k = [ y 0 y 1 … y k − 1 ] , {\displaystyle ~Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots y_{k-1}\end{bmatrix}},}   ( R k ) i j = s i − 1 T y j − 1 , {\displaystyle ~(R_{k})_{ij}=s_{i-1}^{T}y_{j-1},}   ρ i − 1 = 1 / s i − 1 T y i − 1 {\displaystyle ~\rho _{i-1}=1/s_{i-1}^{T}y_{i-1}}   V i = I − ρ i − 1 y i − 1 s i − 1 T {\textstyle ~V_{i}=I-\rho _{i-1}y_{i-1}s_{i-1}^{T}} 1 ≤ i ≤ j ≤ k {\displaystyle 1\leq i\leq j\leq k} k {\displaystyle k} ∏ i = 1 k V i − 1 = ( I − ρ 0 y 0 s 0 T ) ⋯ ( I − ρ k − 1 y k − 1 s k − 1 T ) = I − Y k R k − 1 S k T {\displaystyle \prod _{i=1}^{k}V_{i-1}=\left(I-\rho _{0}y_{0}s_{0}^{T}\right)\cdots \left(I-\rho _{k-1}y_{k-1}s_{k-1}^{T}\right)=I-Y_{k}R_{k}^{-1}S_{k}^{T}} V i {\displaystyle V_{i}}

再帰的準ニュートン更新

準ニュートン更新のパラメトリック族には、最もよく知られている公式の多くが含まれています。[ 9 ]任意のベクトルとに対して、逆ヘッセ推定値と 直接ヘッセ推定値に対する一般的な再帰更新公式は、 v k {\displaystyle v_{k}} c k {\displaystyle c_{k}} v k T y k ≠ 0 {\displaystyle v_{k}^{T}y_{k}\neq 0} c k T s k ≠ 0 {\displaystyle c_{k}^{T}s_{k}\neq 0}

パラメータベクトルとよく知られた方法の特定の選択を行うことで回復される v k {\displaystyle v_{k}} c k {\displaystyle c_{k}}

表1: ベクトルと v k {\displaystyle v_{k}} c k {\displaystyle c_{k}}
v k {\displaystyle v_{k}} method {\displaystyle {\text{method}}} c k {\displaystyle c_{k}} method {\displaystyle {\text{method}}}
s k {\displaystyle s_{k}} BFGS s k {\displaystyle s_{k}} PSB（パウエル対称ブロイデン）
y k {\displaystyle y_{k}} Greenstadt's {\displaystyle {\text{Greenstadt's}}} y k {\displaystyle y_{k}} DFP
s k − H k y k {\displaystyle s_{k}-H_{k}y_{k}} SR1 y k − B k s k {\displaystyle y_{k}-B_{k}s_{k}} SR1
P k S s k {\displaystyle P_{k}^{\text{S}}s_{k}} [10] MSS（多点対称セカント）


コンパクトな表現

再帰式の更新ベクトルを行列に集めて定義する。

S k = [ s 0 s 1 … s k − 1 ] , {\displaystyle S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots &s_{k-1}\end{bmatrix}},} Y k = [ y 0 y 1 … y k − 1 ] , {\displaystyle Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots &y_{k-1}\end{bmatrix}},} V k = [ v 0 v 1 … v k − 1 ] , {\displaystyle V_{k}={\begin{bmatrix}v_{0}&v_{1}&\ldots &v_{k-1}\end{bmatrix}},} C k = [ c 0 c 1 … c k − 1 ] , {\displaystyle C_{k}={\begin{bmatrix}c_{0}&c_{1}&\ldots &c_{k-1}\end{bmatrix}},}

上三角

( R k ) i j := ( R k SY ) i j = s i − 1 T y j − 1 , ( R k VY ) i j = v i − 1 T y j − 1 , ( R k CS ) i j = c i − 1 T s j − 1 ,  for  1 ≤ i ≤ j ≤ k {\displaystyle {\big (}R_{k}{\big )}_{ij}:={\big (}R_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{VY}}{\big )}_{ij}=v_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{CS}}{\big )}_{ij}=c_{i-1}^{T}s_{j-1},\quad \quad {\text{ for }}1\leq i\leq j\leq k}

下三角

( L k ) i j := ( L k SY ) i j = s i − 1 T y j − 1 , ( L k VY ) i j = v i − 1 T y j − 1 , ( L k CS ) i j = c i − 1 T s j − 1 ,  for  1 ≤ j < i ≤ k {\displaystyle {\big (}L_{k}{\big )}_{ij}:={\big (}L_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}L_{k}^{\text{VY}}{\big )}_{ij}=v_{i-1}^{T}y_{j-1},\quad {\big (}L_{k}^{\text{CS}}{\big )}_{ij}=c_{i-1}^{T}s_{j-1},\quad \quad {\text{ for }}1\leq j<i\leq k}

対角線

( D k ) i j := ( D k SY ) i j = s i − 1 T y j − 1 ,  for  1 ≤ i = j ≤ k {\displaystyle (D_{k})_{ij}:={\big (}D_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad \quad {\text{ for }}1\leq i=j\leq k}

これらの定義を用いて、（ ２）と（３ ）の一般的なランク２更新（表１のよく知られた準ニュートン更新を含む）のコンパクトな表現がBrustで開発された：[11]

U k = [ V k S k − H 0 Y k ] {\displaystyle U_{k}={\begin{bmatrix}V_{k}&S_{k}-H_{0}Y_{k}\end{bmatrix}}}

M k = [ 0 k × k R k VY ( R k VY ) T R k + R k T − ( D k + Y k T H 0 Y k ) ] {\displaystyle M_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{VY}}\\{\big (}R_{k}^{\text{VY}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+Y_{k}^{T}H_{0}Y_{k})\end{bmatrix}}}

そして直接ヘッセ行列の式は

J k = [ C k Y k − B 0 S k ] {\displaystyle J_{k}={\begin{bmatrix}C_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}}}

N k = [ 0 k × k R k CS ( R k CS ) T R k + R k T − ( D k + S k T B 0 S k ) ] {\displaystyle N_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{CS}}\\{\big (}R_{k}^{\text{CS}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{bmatrix}}}

例えば、 （ ４ ）の表現が（ １ ）のBFGS再帰の簡潔な式である場合。 V k = S k {\displaystyle V_{k}=S_{k}}

具体的な表現

（ ２）と（３ ）のコンパクトな表現が開発される前に、ほとんどの既知の更新に対して同等の表現が発見されていた（表１参照）。

BFGS

SR1表現とともに、BFGS（ブロイデン・フレッチャー・ゴールドファーブ・シャノ）コンパクト表現は、最初に知られたコンパクト式であった。[7]特に、逆表現は次のように与えられる。

H k = H 0 + U k M k − 1 U k T , U k = [ S k H 0 Y k ] , M k − 1 = [ R k − T ( D k + Y k T H 0 Y k ) R k − 1 − R k − T − R k − 1 0 ] {\displaystyle H_{k}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},\quad U_{k}={\begin{bmatrix}S_{k}&H_{0}Y_{k}\end{bmatrix}},\quad M_{k}^{-1}=\left[{\begin{smallmatrix}R_{k}^{-T}(D_{k}+Y_{k}^{T}H_{0}Y_{k})R_{k}^{-1}&-R_{k}^{-T}\\-R_{k}^{-1}&0\end{smallmatrix}}\right]} 直接ヘッセ行列の近似は、逆ヘッセ行列に シャーマン・モリソン・ウッドベリー恒等式を適用することによって求めることができます。

B k = B 0 + J k N k − 1 J k T , J k = [ B 0 S k Y k ] , N k = [ S T B 0 S k L k L k T − D k ] {\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}={\begin{bmatrix}B_{0}S_{k}&Y_{k}\end{bmatrix}},\quad N_{k}=\left[{\begin{smallmatrix}S^{T}B_{0}S_{k}&L_{k}\\L_{k}^{T}&-D_{k}\end{smallmatrix}}\right]}

SR1

SR1（対称ランク1）コンパクト表現は[7]で初めて提案されました。上記の定義とを用いると 、逆ヘッセ行列式は次のように表されます。 D k , L k {\displaystyle D_{k},L_{k}} R k {\displaystyle R_{k}}

H k = H 0 + U k M k − 1 U k T , U k = S k − H 0 Y k , M k = R k + R k T − D k − Y k T H 0 Y k {\displaystyle H_{k}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},\quad U_{k}=S_{k}-H_{0}Y_{k},\quad M_{k}=R_{k}+R_{k}^{T}-D_{k}-Y_{k}^{T}H_{0}Y_{k}}

直接ヘッセ行列はシャーマン・モリソン・ウッドベリー恒等式によって得られ、次の形をとる。

B k = B 0 + J k N k − 1 J k T , J k = Y k − B 0 S k , N k = D k + L k + L k T − S k T B 0 S k {\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}=Y_{k}-B_{0}S_{k},\quad N_{k}=D_{k}+L_{k}+L_{k}^{T}-S_{k}^{T}B_{0}S_{k}}

写本

多点対称正割法（MSS法）は、複数の正割方程式を満たすことを目的とする手法である。再帰更新式は、もともとブルダコフによって開発された。[12]直接ヘッセ行列のコンパクト表現は[13]で導出された。

B k = B 0 + J k N k − 1 J k T , J k = [ S k Y k − B 0 S k ] , N k = [ W k ( S k T B 0 S k − ( R k − D k + R k T ) ) W k W k W k 0 ] − 1 , W k = ( S k T S k ) − 1 {\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}={\begin{bmatrix}S_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}},\quad N_{k}=\left[{\begin{smallmatrix}W_{k}(S_{k}^{T}B_{0}S_{k}-(R_{k}-D_{k}+R_{k}^{T}))W_{k}&W_{k}\\W_{k}&0\end{smallmatrix}}\right]^{-1},\quad W_{k}=(S_{k}^{T}S_{k})^{-1}}

MSS行列の別の同等なコンパクト表現は、 を 用いて書き直すことによって導出される。[14] 逆表現は、シャーマン・モリソン・ウッドベリー恒等式を適用することによって得られる。 J k {\displaystyle J_{k}} J k = [ S k B 0 Y k ] {\displaystyle J_{k}={\begin{bmatrix}S_{k}&B_{0}Y_{k}\end{bmatrix}}}

DFP

DFP（Davidon Fletcher Powell）更新はBFGS式の双対（つまり、 BFGS更新で、とを入れ替えたもの）であるため、DFPのコンパクトな表現はBFGSの表現からすぐに得ることができる。[15] H k ↔ B k {\displaystyle H_{k}\leftrightarrow B_{k}} H 0 ↔ B 0 {\displaystyle H_{0}\leftrightarrow B_{0}} y k ↔ s k {\displaystyle y_{k}\leftrightarrow s_{k}}

PSB

PSB（Powell-Symmetric-Broyden）コンパクト表現は、直接ヘッセ行列近似のために開発された。[16]これは、 （5） に代入することと等価である。 C k = S k {\displaystyle C_{k}=S_{k}}

B k = B 0 + J k N k − 1 J k T , J k = [ S k Y k − B 0 S k ] , N k = [ 0 R k SS ( R k SS ) T R k + R k T − ( D k + S k T B 0 S k ) ] {\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}={\begin{bmatrix}S_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}},\quad N_{k}=\left[{\begin{smallmatrix}0&R_{k}^{\text{SS}}\\(R_{k}^{\text{SS}})^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{smallmatrix}}\right]}

構造化BFGS

目的関数が2つの部分に分解できる構造化最適化問題において 、 の勾配とヘッセ行列は 既知であるが の勾配のみが既知である場合、構造化BFGS式が存在する。これらの手法の簡潔な表現は、( 5 )の一般形を持ち、具体的な値はおよびである。[17] f ( x ) = k ^ ( x ) + u ^ ( x ) {\displaystyle f(x)={\widehat {k}}(x)+{\widehat {u}}(x)} k ^ ( x ) {\displaystyle {\widehat {k}}(x)} u ^ ( x ) {\displaystyle {\widehat {u}}(x)} J k {\displaystyle J_{k}} N k {\displaystyle N_{k}}

BFGSの減少

BFGSの縮約コンパクト表現（RCR）は、線形等式制約最適化のためのもので 、は劣決定 である。RCRは行列に加えて、 の零空間への射影も格納する。  minimize  f ( x )  subject to:  A x = b {\displaystyle {\text{ minimize }}f(x){\text{ subject to: }}Ax=b} A {\displaystyle A} S k , Y k {\displaystyle S_{k},Y_{k}} y i {\displaystyle y_{i}} A {\displaystyle A}

Z k = [ z 0 z 1 ⋯ z k − 1 ] , z i = P y i , P = I − A ( A T A ) − 1 A T , 0 ≤ i ≤ k − 1 {\displaystyle Z_{k}={\begin{bmatrix}z_{0}&z_{1}&\cdots z_{k-1}\end{bmatrix}},\quad z_{i}=Py_{i},\quad P=I-A(A^{T}A)^{-1}A^{T},\quad 0\leq i\leq k-1}

BFGS行列のコンパクト表現（単位行列の倍数）に対して、逆KKT行列の（1,1）ブロックはコンパクト表現を持つ[18] B k {\displaystyle B_{k}} B 0 {\displaystyle B_{0}}

K k = [ B k A T A 0 ] , B 0 = 1 γ k I , H 0 = γ k I , γ k > 0 {\displaystyle K_{k}={\begin{bmatrix}B_{k}&A^{T}\\A&0\end{bmatrix}},\quad B_{0}={\frac {1}{\gamma _{k}}}I,\quad H_{0}=\gamma _{k}I,\quad \gamma _{k}>0}

( K k − 1 ) 11 = H 0 + U k M k − 1 U k T , U k = [ A T S k Z k ] , M k = [ − A A T / γ k G k ] , G k = [ R k − T ( D k + Y k T H 0 Y k ) R k − 1 − H 0 R k − T − H 0 R k − 1 0 ] − 1 {\displaystyle {\big (}K_{k}^{-1}{\big )}_{11}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},\quad U_{k}={\begin{bmatrix}A^{T}&S_{k}&Z_{k}\end{bmatrix}},\quad M_{k}=\left[{\begin{smallmatrix}-AA^{T}/\gamma _{k}&\\&G_{k}\end{smallmatrix}}\right],\quad G_{k}=\left[{\begin{smallmatrix}R_{k}^{-T}(D_{k}+Y_{k}^{T}H_{0}Y_{k})R_{k}^{-1}&-H_{0}R_{k}^{-T}\\-H_{0}R_{k}^{-1}&0\end{smallmatrix}}\right]^{-1}}

限られたメモリ

メモリ制限更新戦略におけるパターン。メモリパラメータが の場合、最初の反復処理で行列が埋められます（例えば、コンパクト表現の場合は上三角行列）。メモリ制限手法では、最も古い情報を破棄し、最後に新しい列を追加します。 m = 7 {\displaystyle m=7} k ≤ m {\displaystyle k\leq m} R k = triu ( S k T Y k ) {\displaystyle R_{k}={\text{triu}}(S_{k}^{T}Y_{k})} k > m {\displaystyle k>m}


コンパクト表現の最も一般的な用途は、メモリ制限の設定です。ここで、 はメモリパラメータを表し、典型的な値は 付近です（例、[18] [7]を参照）。次に、すべてのベクトルの履歴を保存する代わりに、これを最新のベクトルと、場合によってはまたはに制限します。さらに、通常、初期化は、および として、恒等式 の適応倍数として選択されます。メモリ制限法は、多くの変数（つまり、が大きくなる可能性がある）を伴う大規模な問題でよく使用されます。このような大規模問題では、メモリ制限行列 および（場合によっては）が高くて非常に細いものになり ます。 m ≪ n {\displaystyle m\ll n} m ∈ [ 5 , 12 ] {\displaystyle m\in [5,12]} m {\displaystyle m} { ( s i , y i } i = k − m k − 1 {\displaystyle \{(s_{i},y_{i}\}_{i=k-m}^{k-1}} { v i } i = k − m k − 1 {\displaystyle \{v_{i}\}_{i=k-m}^{k-1}} { c i } i = k − m k − 1 {\displaystyle \{c_{i}\}_{i=k-m}^{k-1}} H k ( 0 ) = γ k I {\displaystyle H_{k}^{(0)}=\gamma _{k}I} γ k = y k − 1 T s k − 1 / y k − 1 T y k − 1 {\displaystyle \gamma _{k}=y_{k-1}^{T}s_{k-1}/y_{k-1}^{T}y_{k-1}} B k ( 0 ) = 1 γ k I {\displaystyle B_{k}^{(0)}={\frac {1}{\gamma _{k}}}I} n {\displaystyle n} S k ∈ R n × m {\displaystyle S_{k}\in \mathbb {R} ^{n\times m}} Y k ∈ R n × m {\displaystyle Y_{k}\in \mathbb {R} ^{n\times m}} V k , C k {\displaystyle V_{k},C_{k}} S k = [ s k − l − 1 … s k − 1 ] {\displaystyle S_{k}={\begin{bmatrix}s_{k-l-1}&\ldots &s_{k-1}\end{bmatrix}}} Y k = [ y k − l − 1 … y k − 1 ] {\displaystyle Y_{k}={\begin{bmatrix}y_{k-l-1}&\ldots &y_{k-1}\end{bmatrix}}}

実装

オープンソース実装には以下が含まれます。

  • ACM TOMSアルゴリズム1030はL-SR1ソルバーを実装している[19] [20]
  • Rのoptim汎用最適化ルーチンは L-BFGS-B メソッドを使用します。
  • SciPyの最適化モジュールの minimize メソッドには、L-BFGS-B を使用するオプションも含まれています。
  • 一次情報付きIPOPT

非オープンソース実装には以下が含まれます。

引用文献

  1. ^ Nocedal, J.; Wright, SJ (2006). 数値最適化. Springer Series in Operations Research and Financial Engineering. Springer New York, NY. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1。
  2. ^ Brust, JJ (2018). 大規模準ニュートン信頼領域法：高精度ソルバー、稠密初期化、および拡張（博士論文）. カリフォルニア大学マーセド校.
  3. ^ ab Byrd, RH; Nocedal, J; Waltz, RA (2006). 「KNITRO: 非線形最適化のための統合パッケージ」.大規模非線形最適化. 非凸最適化とその応用. 第83巻. Di Pillo, G., Roma, M. (編) 大規模非線形最適化. 非凸最適化とその応用. 第83巻. Springer, Boston, MA. pp.  35– 59. doi :10.1007/0-387-30065-1_4. ISBN 978-0-387-30063-4。{{cite book}}: CS1 maint: location (link)
  4. ^ Zhu, C.; Byrd, RH; Lu, P.; Nocedal, J. (1997). 「アルゴリズム778: L-BFGS-B: 大規模境界制約最適化のためのFortranサブルーチン」. ACM Transactions on Mathematical Software . 23 (4): 550– 560. doi :10.1145/279232.279236.
  5. ^ Brust, J.; Burdakov, O.; Erway, J.; Marcia, R. (2022). 「アルゴリズム1030: SC-SR1: メモリ制限SR1信頼領域法のためのMATLABソフトウェア」. ACM Transactions on Mathematical Software . 48 (4): 1– 33. doi :10.1145/3550269.
  6. ^ Wächter, A.; Biegler, LT (2006). 「大規模非線形計画法のための内点フィルタ直線探索アルゴリズムの実装について」.数学プログラミング. 106 : 25–57 . doi :10.1007/s10107-004-0559-y.
  7. ^ abcde Byrd, RH; Nocedal, J.; Schnabel, RB (1994). 「準ニュートン行列の表現と限定メモリ法におけるその利用」.数理計画. 63 (4): 129– 156. doi :10.1007/BF01582063. S2CID  5581219.
  8. ^ Walker, HF (1988). 「ハウスホルダー変換を用いたGMRES法の実装」. SIAM Journal on Scientific and Statistical Computing . 9 (1): 152– 163. doi :10.1137/0909010.
  9. ^ Dennis, Jr, JE; Moré, JJ (1977). 「準ニュートン法、その動機と理論」(PDF) . SIAM Review . 19 (1): 46– 89. doi :10.1137/1019005. hdl : 1813/6056 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
  10. ^ S k + 1 = [ s 0 … s k ] ,   P k S = I − S k + 1 ( S k + 1 T S k + 1 ) − 1 S k + 1 T {\displaystyle S_{k+1}={\begin{bmatrix}s_{0}&\ldots &s_{k}\end{bmatrix}},~P_{k}^{\text{S}}=I-S_{k+1}(S_{k+1}^{T}S_{k+1})^{-1}S_{k+1}^{T}}
  11. ^ Brust, JJ (2024). 「データフィッティングのための有用なコンパクト表現」. arXiv : 2403.12206 [math.OC].
  12. ^ Burdakov, OP (1983). 「対称ヤコビ行列を持つ方程式系に対するセカント型法」.数値関数解析と最適化. 6 (2): 1– 18. doi :10.1080/01630568308816160.
  13. ^ Burdakov, OP; Martínez, JM; Pilotta, EA (2002). 「境界制約付き最適化のためのメモリ制限型マルチポイント対称セカント法」Annals of Operations Research . 117 ( 1–4 ): 51–70 . doi :10.1023/A:1021561204463.
  14. ^ Brust, JJ; Erway, JB; Marcia, RF (2024). 「多点対称正割行列を用いた形状変化信頼領域法」.最適化手法とソフトウェア. 39 (5​​): 990– 1007. arXiv : 2209.12057 . doi :10.1080/10556788.2023.2296441.
  15. ^ Erway, JB; Jain, V.; Marcia, RF (2013).シフト型メモリ制限DFPシステム. 2013年Asilomar Conference on Signals, Systems and Computers. IEEE. pp.  1033– 1037.
  16. ^ Kanzow, C.; Steck, D. (2023). 「大規模非凸最小化のための限定メモリ準ニュートン法の正則化」.数理計画計算. 15 (3): 417– 444. arXiv : 1911.04584 . doi : 10.1007/s12532-023-00238-4 .
  17. ^ Brust, J. J; Di, Z.; Leyffer, S.; Petra, CG (2021). 「構造化BFGS行列のコンパクト表現」.計算最適化とその応用. 80 (1): 55– 88. arXiv : 2208.00057 . doi :10.1007/s10589-021-00297-0.
  18. ^ ab Brust, J. J; Marcia, RF; Petra, CG; Saunders, MA (2022). 「縮小コンパクト表現を用いた線形等式制約による大規模最適化」. SIAM Journal on Scientific Computing . 44 (1): A103 – A127 . arXiv : 2101.11048 . Bibcode :2022SJSC...44A.103B. doi :10.1137/21M1393819.
  19. ^ 「ACMアルゴリズム集」calgo.acm.org。
  20. ^ "TOMS Alg. 1030". calgo.acm.org/1030.zip .
  21. ^ Zhu, C.; Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge (1997). 「L-BFGS-B: アルゴリズム778: L-BFGS-B, FORTRANルーチンによる大規模境界制約最適化」. ACM Transactions on Mathematical Software . 23 (4): 550– 560. doi : 10.1145/279232.279236 . S2CID  207228122.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Compact_quasi-Newton_representation&oldid=1317246544"