信頼領域法

同義語:trust region methodtrust-region method

概要

信頼領域法(trust region method)とは、関数を今いる点のまわりで 2 次式で近似し、その近似を半径 Δ の球(信頼領域)の中だけで最小化して 1 歩を決め、実際の減少量と近似が予言した減少量の比に応じて点を受け入れるかどうかと次の半径を決める、制約なし最適化の反復法である。2 次式の行列が正定値でなくても 1 歩が決まり、Newton 法を大域的に収束するように安定させる。勾配が Lipschitz 連続で関数が下に有界、近似の行列が有界で、各回の 1 歩が勾配方向の最良の点(Cauchy 点)と同程度に近似を減らすなら、勾配のノルムの下極限は 0 になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Newton法, 勾配降下法, 正定値行列

Newton法 は、関数 $f$ を今いる点 $x$ のまわりで 2 次式 $f(x)+\nabla f(x)\cdot p+\frac12p^{\mathsf T}\nabla^2f(x)p$ で近似し、その最小点へ跳ぶ。解の近くでは速いが、遠くでは近似が当てにならず、Hesse行列 が正定値でなければ 2 次式に最小点がないこともある。Rosenbrock 関数 $f(x)=100(x_2-x_1^2)^2+(1-x_1)^2$ では、点 $(-1.2,1)$ から Newton の点へそのまま跳ぶと値が下がる保証はない。
信頼領域法 は、2 次の近似を「信頼できる半径 $\Delta$ の球」の中だけで最小化して 1 歩を決め、実際の値の減り方と近似が予言した減り方の比を見て、次の半径を広げたり縮めたりする反復法である。直線探索の方法が「向きを先に決めてから長さを決める」のに対し、信頼領域法は「長さの上限を先に決めてから向きを決める」。
この記事では、球の中の 2 次式の最小化(部分問題)の解の特徴づけと、勾配の向きだけで作れる Cauchy 点が保証する減少量を証明し、それを使って、各回の 1 歩が Cauchy 点と同じ程度に近似を減らすなら勾配が $0$ に近づく部分列があること(主定理)を証明する。

定義と使える条件

$\|\cdot\|$ は Euclid ノルム、行列 $B$ の $\|B\|$ は対応する作用素ノルム(対称行列なら固有値の絶対値の最大)とする。$f\colon\mathbb{R}^n\to\mathbb{R}$ は微分可能とし、$g_k:=\nabla f(x_k)$ と書く。

2 次モデルと部分問題

点 $x_k$、対称行列 $B_k$、半径 $\Delta_k>0$ について
$$ m_k(p):=f(x_k)+g_k\cdot p+\frac12p^{\mathsf T}B_kp $$
を 2 次モデル といい、「$\|p\|\le\Delta_k$ のもとで $m_k(p)$ を最小化する」問題を 信頼領域の部分問題 という。$\{x_k+p\mid\|p\|\le\Delta_k\}$ を 信頼領域 という。1 歩 $p_k$ について
$$ \rho_k:=\frac{f(x_k)-f(x_k+p_k)}{m_k(0)-m_k(p_k)} $$
を 一致の比 という(分母は予言した減少量、分子は実際の減少量)。

$B_k=\nabla^2f(x_k)$ とするものを信頼領域 Newton 法という。$B_k$ は 準Newton法 の更新で作ってもよい。

信頼領域法

$0<\eta<\frac14$、$\Delta_0>0$、初期点 $x_0$ をとる。$k=0,1,2,\dots$ について、$g_k\ne0$ の間、次を行う。

  1. 部分問題を(近似的に)解いて $\|p_k\|\le\Delta_k$ となる $p_k$ を求め、$\rho_k$ を計算する。
  2. 半径の更新:$\rho_k<\frac14$ なら $\Delta_{k+1}:=\frac14\Delta_k$。$\rho_k>\frac34$ かつ $\|p_k\|=\Delta_k$ なら $\Delta_{k+1}:=2\Delta_k$。それ以外は $\Delta_{k+1}:=\Delta_k$。
  3. 点の更新:$\rho_k>\eta$ なら $x_{k+1}:=x_k+p_k$(成功)、そうでなければ $x_{k+1}:=x_k$(失敗)。
    これを 信頼領域法(trust region method)という。

半径を広げるのは、近似がよく当たり、しかも半径いっぱいに進んだときだけである。半径に上限 $\Delta_{\max}$ を設けて $\Delta_{k+1}=\min\{2\Delta_k,\Delta_{\max}\}$ とすることも多いが、以下の議論は変わらない。

Cauchy 点

$g_k\ne0$ のとき、$\tau_k:=1$($g_k^{\mathsf T}B_kg_k\le0$ のとき)、$\tau_k:=\min\Bigl\{\dfrac{\|g_k\|^3}{\Delta_kg_k^{\mathsf T}B_kg_k},1\Bigr\}$(それ以外)とし、
$$ p_k^{\mathrm C}:=-\tau_k\frac{\Delta_k}{\|g_k\|}g_k $$
を Cauchy 点 という。これは、$-g_k$ の向きの線分 $\{-t g_k\mid0\le t\le\Delta_k/\|g_k\|\}$ の上で $m_k$ を最小にする点である。

この記事の主定理を使う条件をまとめる。

  1. 滑らかさ:$\nabla f$ は $L$-Lipschitz 連続である(すべての $x,y$ で $\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|$)。
  2. 下に有界:$\inf f>-\infty$。
  3. モデルの行列が有界:すべての $k$ で $\|B_k\|\le\beta$。
  4. Cauchy 減少条件:ある $c_1\in(0,1]$ について、すべての $k$ で $\|p_k\|\le\Delta_k$ かつ
    $$ m_k(0)-m_k(p_k)\ge c_1\|g_k\|\min\Bigl\{\Delta_k,\frac{\|g_k\|}{\|B_k\|}\Bigr\} $$
    ($B_k=0$ のときは最小を $\Delta_k$ と読む)。
    条件 4 は、部分問題を厳密に解かなくても、Cauchy 点と同程度に減らせば十分であることを言う。Cauchy 点($c_1=\frac12$、lem-tr-cauchy)、部分問題の厳密解、dogleg の点(prop-tr-dogleg)はどれも条件 4 を満たす。

公式の表

量式条件根拠
Cauchy 点の減少量$m(0)-m(p^{\mathrm C})\ge\frac12\|g\|\min\{\Delta,\|g\|/\|B\|\}$$g\ne0$lem-tr-cauchy
部分問題の厳密解$(B+\lambda I)p^*=-g$、$\lambda(\Delta-\|p^*\|)=0$、$B+\lambda I\succeq0$、$\lambda\ge0$必要十分thm-tr-subproblem
内部の解$p^*=-B^{-1}g$$B$ が正定値で $\|B^{-1}g\|\le\Delta$thm-tr-subproblem($\lambda=0$)
最急降下の点$p^{\mathrm U}=-\dfrac{\|g\|^2}{g^{\mathsf T}Bg}g$$g^{\mathsf T}Bg>0$1 変数の 2 次式の最小
dogleg の点折れ線 $0\to p^{\mathrm U}\to p^{\mathrm B}=-B^{-1}g$ と球面の交点($\|p^{\mathrm B}\|\le\Delta$ なら $p^{\mathrm B}$)$B$ が正定値prop-tr-dogleg
大域収束$\liminf_{k}\|g_k\|=0$条件 1〜4thm-tr-global

主定理と証明

まず、Cauchy 点がどれだけモデルを減らすかを測る。主定理の証明で使うのはこの評価だけである。

Cauchy 点の減少量

$g\ne0$、$B$ を対称行列、$\Delta>0$ とし、$m(p)=f_0+g\cdot p+\frac12p^{\mathsf T}Bp$ の Cauchy 点を $p^{\mathrm C}$ とする。このとき
$$ m(0)-m(p^{\mathrm C})\ge\frac12\|g\|\min\Bigl\{\Delta,\frac{\|g\|}{\|B\|}\Bigr\} $$
($B=0$ のときは右辺の最小を $\Delta$ と読む)。

$u:=g/\|g\|$、$\gamma:=u^{\mathsf T}Bu$ とおく。$\gamma\le\|B\|$ である。$0\le t\le\Delta$ について
$$ \varphi(t):=m(0)-m(-tu)=t\|g\|-\frac12\gamma t^2 $$
とおく。def-tr-cauchy の $\tau$ は $\tau\Delta=\min\{\|g\|/\gamma,\Delta\}$($\gamma\le0$ のときは $\tau\Delta=\Delta$)を満たすので、$p^{\mathrm C}=-t^*u$、$t^*:=\tau\Delta$ であり、$m(0)-m(p^{\mathrm C})=\varphi(t^*)$ である。3 つの場合に分ける。

  1. $\gamma\le0$ のとき:$t^*=\Delta$ で、$\varphi(\Delta)\ge\Delta\|g\|\ge\frac12\|g\|\Delta$。
  2. $\gamma>0$ かつ $\|g\|/\gamma\le\Delta$ のとき:$t^*=\|g\|/\gamma$ で、$\varphi(t^*)=\dfrac{\|g\|^2}{2\gamma}\ge\dfrac{\|g\|^2}{2\|B\|}$。
  3. $\gamma>0$ かつ $\|g\|/\gamma>\Delta$ のとき:$t^*=\Delta$ で、$\gamma\Delta< \|g\|$ より $\varphi(\Delta)=\Delta\|g\|-\frac12\gamma\Delta^2\ge\Delta\|g\|-\frac12\Delta\|g\|=\frac12\|g\|\Delta$。
    どの場合も右辺 $\frac12\|g\|\min\{\Delta,\|g\|/\|B\|\}$ 以上である。また $\varphi$ は $[0,\Delta]$ の上で $t^*$ で最大になる($\gamma\le0$ なら増加、$\gamma>0$ なら頂点 $\|g\|/\gamma$ の放物線)ので、$p^{\mathrm C}$ は線分の上の $m$ の最小点である。
信頼領域法の大域収束

使える条件 1〜4 のもとで、def-tr-method の反復は、有限回で $g_k=0$ に達して止まるか、そうでなければ
$$ \liminf_{k\to\infty}\|\nabla f(x_k)\|=0 $$
を満たす。

有限回で止まらないとし、結論が成り立たないと仮定する。すると $\varepsilon>0$ と $K$ があって、$k\ge K$ ならつねに $\|g_k\|\ge\varepsilon$ となる。$\beta>0$ としてよい($\beta$ を大きくしても条件 3 は保たれる)。
段階 1(モデルの誤差) $\|p\|\le\Delta_k$ なら
$$ \bigl|f(x_k+p)-m_k(p)\bigr|\le\frac{L+\beta}2\|p\|^2. $$
実際、$f(x_k+p)-f(x_k)-g_k\cdot p=\int_0^1\bigl(\nabla f(x_k+tp)-\nabla f(x_k)\bigr)\cdot p\,dt$ の絶対値は $\int_0^1Lt\|p\|^2dt=\frac L2\|p\|^2$ 以下であり、$\bigl|\frac12p^{\mathsf T}B_kp\bigr|\le\frac\beta2\|p\|^2$ である。
段階 2(半径が小さければ必ず成功する) $k\ge K$ とし、
$$ \bar\Delta:=\min\Bigl\{\frac\varepsilon\beta,\ \frac{c_1\varepsilon}{2(L+\beta)}\Bigr\} $$
とおく。$\Delta_k\le\bar\Delta$ なら、条件 4 と $\|B_k\|\le\beta$ から、予言した減少量は
$$ m_k(0)-m_k(p_k)\ge c_1\varepsilon\min\Bigl\{\Delta_k,\frac\varepsilon\beta\Bigr\}=c_1\varepsilon\Delta_k $$
以上で、とくに正である。段階 1 と $\|p_k\|\le\Delta_k$ より
$$ |\rho_k-1|=\frac{|f(x_k+p_k)-m_k(p_k)|}{m_k(0)-m_k(p_k)}\le\frac{(L+\beta)\Delta_k^2/2}{c_1\varepsilon\Delta_k}=\frac{(L+\beta)\Delta_k}{2c_1\varepsilon}\le\frac14. $$
よって $\rho_k\ge\frac34$ で、この回は成功し、半径は縮まない。
段階 3(半径は下に有界) $\Delta_{\mathrm{low}}:=\min\{\Delta_K,\bar\Delta/4\}$ とおくと、$k\ge K$ でつねに $\Delta_k\ge\Delta_{\mathrm{low}}$ である。$k$ についての帰納法による。$\Delta_k\ge\Delta_{\mathrm{low}}$ とする。半径が縮むのは $\rho_k< \frac14$ のときだけで、段階 2 よりそのとき $\Delta_k>\bar\Delta$ だから、$\Delta_{k+1}=\frac14\Delta_k>\bar\Delta/4\ge\Delta_{\mathrm{low}}$ である。縮まないときは $\Delta_{k+1}\ge\Delta_k\ge\Delta_{\mathrm{low}}$ である。
段階 4(矛盾) 成功の回は無限にある。もし有限なら、ある回から先はすべて $\rho_k\le\eta< \frac14$ で、半径は毎回 $\frac14$ 倍になって $0$ に近づき、段階 3 に反する。$k\ge K$ が成功の回なら、条件 4 と段階 3 より
$$ f(x_k)-f(x_{k+1})=\rho_k\bigl(m_k(0)-m_k(p_k)\bigr)>\eta c_1\varepsilon\min\Bigl\{\Delta_{\mathrm{low}},\frac\varepsilon\beta\Bigr\}=:\delta>0. $$
失敗の回は $x_{k+1}=x_k$ だから $f$ の値は変わらない。成功の回が無限にあるので $f(x_k)\to-\infty$ となり、条件 2 に反する。したがって $\liminf_k\|g_k\|=0$ である。

段階 2 が信頼領域法の要である。半径が小さいと 2 次モデルの誤差は $\Delta_k^2$ の程度なのに、Cauchy 減少条件で保証される予言の減少量は $\Delta_k$ の程度なので、比 $\rho_k$ は $1$ に近づく。半径を縮め続けると、いつか必ず成功する。直線探索の方法で降下方向の条件と Armijo 条件が果たす役割を、信頼領域法では条件 4 と半径の更新が果たしている。
主定理は Cauchy 点さえ計算できれば使えるが、Cauchy 点だけでは実質的に 最急降下法 であり遅い(ex-tr-rosenbrock)。実用では部分問題を厳密に、またはそれに近く解く。次の定理は厳密解の形を決める。

部分問題の解の特徴づけ

$B$ を対称行列、$\Delta>0$ とする。$p^*$($\|p^*\|\le\Delta$)が $q(p):=g\cdot p+\frac12p^{\mathsf T}Bp$ の $\|p\|\le\Delta$ での最小点であるための必要十分条件は、次を満たす $\lambda\ge0$ が存在することである。
$$ (B+\lambda I)p^*=-g,\qquad\lambda(\Delta-\|p^*\|)=0,\qquad B+\lambda I\text{ は半正定値}. $$

証明を開く

$M:=B+\lambda I$ とおく。$g=-Mp^*$ が成り立つ実数 $\lambda$ について、展開して整理すると、すべての $p$ で$$q(p)-q(p^*)=\frac12(p-p^*)^{\mathsf T}M(p-p^*)-\frac\lambda2\bigl(\|p\|^2-\|p^*\|^2\bigr)\qquad(\star)$$が成り立つ。 【十分性】条件を満たす $\lambda\ge0$ があれば、$\|p\|\le\Delta$ のとき $(\star)$ の第 1 項は $M$ の半正定値性から $0$ 以上である。第 2 項は、$\lambda=0$ なら $0$、$\lambda>0$ なら $\|p^*\|=\Delta$ なので $-\frac\lambda2(\|p\|^2-\Delta^2)\ge0$ である。よって $q(p)\ge q(p^*)$。 【必要性】$p^*$ が最小点とする。$\|p^*\|< \Delta$ なら $p^*$ は内部の極小点なので $g+Bp^*=0$ かつ $B$ は半正定値であり(2 次の必要条件)、$\lambda=0$ が条件を満たす。$\|p^*\|=\Delta$ とする。 (a) $\lambda$ の存在:$w\perp p^*$ について、球面 $\|p\|=\Delta$ の上の曲線 $c(t):=\Delta(p^*+tw)/\|p^*+tw\|$ は $c(0)=p^*$、$c'(0)=w$ を満たす。$q(c(t))$ は $t=0$ で最小だから $\nabla q(p^*)\cdot w=0$。これがすべての $w\perp p^*$ で成り立つので、$\nabla q(p^*)=g+Bp^*$ は $p^*$ の実数倍であり、$g+Bp^*=-\lambda p^*$ と書ける。 (b) $M$ の半正定値性:$\|p\|=\Delta$ なら $(\star)$ の第 2 項は $0$ なので $(p-p^*)^{\mathsf T}M(p-p^*)\ge0$。$p^*\cdot w\ne0$ となる $w$ に対し $s:=-2p^*\cdot w/\|w\|^2$ とおくと $\|p^*+sw\|=\Delta$ なので、$s^2w^{\mathsf T}Mw\ge0$、すなわち $w^{\mathsf T}Mw\ge0$。$p^*\cdot w=0$ の $w$ はそうした $w$ の極限だから、連続性より $w^{\mathsf T}Mw\ge0$。 (c) $\lambda\ge0$:$0< s\le1$ について $p=(1-s)p^*$ は球の中にあり、$(\star)$ より$$q\bigl((1-s)p^*\bigr)-q(p^*)=\frac{s^2}2p^{*\mathsf T}Mp^*+\frac\lambda2(2s-s^2)\Delta^2.$$$\lambda< 0$ なら $s\to+0$ で右辺は $\lambda s\Delta^2$ の程度で負になり、$p^*$ の最小性に反する。

$B$ が正定値で $\|B^{-1}g\|\le\Delta$ なら $\lambda=0$、$p^*=-B^{-1}g$(Newton の 1 歩)である。そうでなければ、$B$ の固有分解 $B=Q\,\mathrm{diag}(\mu_i)Q^{\mathsf T}$ と $a:=Q^{\mathsf T}g$ を使うと、$\lambda>\max\{0,-\mu_{\min}\}$ で $p(\lambda):=-(B+\lambda I)^{-1}g$ のノルム $\|p(\lambda)\|^2=\sum_ia_i^2/(\mu_i+\lambda)^2$ は $\lambda$ について減少するので、1 変数の方程式 $\|p(\lambda)\|=\Delta$ を解けばよい。$g$ が最小固有値の固有空間に直交すると、この方程式に解がなく $\lambda=-\mu_{\min}$ となる場合(hard case と呼ばれる)があり、そのときは最小固有値の固有ベクトルの方向を足して球面に届かせる。この記事では hard case の数値的な扱いには立ち入らない。
部分問題は凸とは限らないが、球の条件 1 つの 2 次の問題なので強双対性が成り立ち、thm-tr-subproblem はその言い換えにもなっている(BV04 Appendix B.1, pp. 653–654)。
$B$ が正定値のとき、厳密解の代わりによく使う折れ線の近似が dogleg である。

dogleg の折れ線の単調性

$B$ を正定値、$g\ne0$ とし、$p^{\mathrm U}:=-\dfrac{g^{\mathsf T}g}{g^{\mathsf T}Bg}g$、$p^{\mathrm B}:=-B^{-1}g$ とする。折れ線
$$ \tilde p(\alpha):=\begin{cases}\alpha p^{\mathrm U}&(0\le\alpha\le1),\\ p^{\mathrm U}+(\alpha-1)(p^{\mathrm B}-p^{\mathrm U})&(1\le\alpha\le2)\end{cases} $$
に沿って、$\|\tilde p(\alpha)\|$ は広義に増加し、$q(\tilde p(\alpha))$ は広義に減少する。したがって、$\|p^{\mathrm B}\|\le\Delta$ なら $p^{\mathrm B}$、そうでなければ折れ線と球面 $\|p\|=\Delta$ のただ 1 つの交点を dogleg の点 とすると、そのモデルの値は Cauchy 点の値以下であり、条件 4 を $c_1=\frac12$ で満たす。

証明を開く

$a:=g^{\mathsf T}g$、$b:=g^{\mathsf T}Bg$、$c:=g^{\mathsf T}B^{-1}g$ とおく。$a=(B^{1/2}g)\cdot(B^{-1/2}g)$ に Cauchy–Schwarz の不等式を使うと $a^2\le bc$。 前半の線分では $\|\alpha p^{\mathrm U}\|$ は増加し、$p^{\mathrm U}$ は直線 $\{-tg\}$ の上の $q$ の最小点なので $q(\alpha p^{\mathrm U})$ は $[0,1]$ で減少する。 後半では $d:=p^{\mathrm B}-p^{\mathrm U}$、$s:=\alpha-1\in[0,1]$ とおく。$p^{\mathrm U}\cdot p^{\mathrm B}=\frac{ac}b$、$\|p^{\mathrm U}\|^2=\frac{a^3}{b^2}$ より$$p^{\mathrm U}\cdot d=\frac a{b^2}(bc-a^2)\ge0$$なので、$\frac{d}{ds}\frac12\|p^{\mathrm U}+sd\|^2=p^{\mathrm U}\cdot d+s\|d\|^2\ge0$。また $g+Bp^{\mathrm B}=0$ より$$\frac{d}{ds}q(p^{\mathrm U}+sd)=\bigl(g+Bp^{\mathrm U}+sBd\bigr)\cdot d=-(1-s)\,d^{\mathsf T}Bd\le0.$$ノルムが増加するので、$\|p^{\mathrm B}\|>\Delta$ なら球面との交点はただ 1 つで、折れ線のうち球の中にある部分はその交点までの始めの部分である。Cauchy 点は前半の線分の上にあって球の中にあるから、$q$ の減少性より dogleg の点のモデルの値は Cauchy 点の値以下であり、lem-tr-cauchy から条件 4 が $c_1=\frac12$ で成り立つ。

主定理の結論は $\liminf$ であり、点列そのものの収束や $\lim_k\|g_k\|=0$ は言っていない。一方、$B_k=\nabla^2f(x_k)$ とし、ある回から先、内部の解 $p_k=-\nabla^2f(x_k)^{-1}g_k$ がずっと受け入れられるなら、その先の反復は写像 $\nabla f$ に対する Newton 法そのものである。そこで $\nabla f$ が $C^2$ 級で、$\nabla f(x^*)=0$ かつ $\nabla^2f(x^*)$ が正則な点 $x^*$ の十分近くに $x_k$ が入れば、Newton法 の定理「多変数のNewton法の局所2次収束」を写像 $\nabla f$ に当てて 2 次収束が分かる。ex-tr-rosenbrock の終盤はこの状態になっている。

計算の手順

  1. 初期点 $x_0$、初期半径 $\Delta_0$(変数の目盛りで 1 程度)、$\eta$($0.1$ など)、許容誤差 $\epsilon$ を決める。
  2. $g_k=\nabla f(x_k)$ を計算し、$\|g_k\|\le\epsilon$ なら止める。
  3. $B_k$ を決める(Hesse行列 $\nabla^2f(x_k)$、または 準Newton法 の更新)。
  4. 部分問題を解く。$B_k$ が正定値で $\|B_k^{-1}g_k\|\le\Delta_k$ なら $p_k=-B_k^{-1}g_k$。そうでなければ、方程式 $\|(B_k+\lambda I)^{-1}g_k\|=\Delta_k$ を $\lambda$ について解く(thm-tr-subproblem)か、$B_k$ が正定値なら dogleg の点、最低でも Cauchy 点をとる。
  5. 予言 $m_k(0)-m_k(p_k)$ と実際 $f(x_k)-f(x_k+p_k)$ を計算し、比 $\rho_k$ を出す。
  6. def-tr-method の規則で半径と点を更新し、2 に戻る。
    予言の減少量は $-g_k\cdot p_k-\frac12p_k^{\mathsf T}B_kp_k$ で、$f(x_k)$ を引き算で打ち消さずに直接計算すると桁落ちしにくい。

例題

Cauchy 点・dogleg・厳密解

$g=(2,1)$、$B=\mathrm{diag}(4,2)$ のモデル $q(p)=g\cdot p+\frac12p^{\mathsf T}Bp$ について、半径 $\Delta=1,\ 0.65,\ 0.4$ のそれぞれで Cauchy 点、dogleg の点、厳密解を求め、モデルの値を比べよ。
使う公式:def-tr-cauchy、prop-tr-dogleg、thm-tr-subproblem。
答え:$a=g^{\mathsf T}g=5$、$b=g^{\mathsf T}Bg=18$ より $p^{\mathrm U}=-\frac5{18}(2,1)\approx(-0.555556,-0.277778)$、$\|p^{\mathrm U}\|\approx0.621130$、$q(p^{\mathrm U})=-\frac{a^2}{2b}=-\frac{25}{36}\approx-0.694444$。$p^{\mathrm B}=-B^{-1}g=(-0.5,-0.5)$、$\|p^{\mathrm B}\|\approx0.707107$、$q(p^{\mathrm B})=-\frac12g^{\mathsf T}B^{-1}g=-0.75$。

$\Delta$Cauchy 点($q$)dogleg の点($q$)厳密解($\lambda$、$q$)
$1$$p^{\mathrm U}$($-0.694444$)$p^{\mathrm B}$($-0.75$)$p^{\mathrm B}$($\lambda=0$、$-0.75$)
$0.65$$p^{\mathrm U}$($-0.694444$)$(-0.531432,-0.374273)$($-0.732217$)$(-0.471974,-0.446923)$($\lambda\approx0.237520$、$-0.745612$)
$0.4$$(-0.357771,-0.178885)$($-0.606427$)Cauchy 点と同じ$(-0.321937,-0.237395)$($\lambda\approx2.212389$、$-0.617626$)

どの半径でも、モデルの値は Cauchy 点、dogleg の点、厳密解の順に小さくなる(等しい場合を含む)。

途中の計算
途中の計算を開く

$\Delta=1$:$\tau=\min\{5\sqrt5/18,1\}\approx0.621$ なので $p^{\mathrm C}=p^{\mathrm U}$。lem-tr-cauchy の下界は $\frac12\sqrt5\min\{1,\sqrt5/4\}=0.625$ で、実際の減少 $0.694444$ はそれ以上である。$\|p^{\mathrm B}\|\le1$ なので dogleg の点も厳密解も $p^{\mathrm B}$。 $\Delta=0.65$:$\|p^{\mathrm U}\|< 0.65< \|p^{\mathrm B}\|$ なので dogleg の点は後半の線分の上にある。$d=p^{\mathrm B}-p^{\mathrm U}=(\frac1{18},-\frac2{9})$ として $\|p^{\mathrm U}+sd\|=0.65$ を解くと $s\approx0.4342$。厳密解は $p(\lambda)=-\bigl(\frac2{4+\lambda},\frac1{2+\lambda}\bigr)$ の長さが $0.65$ になる $\lambda$ を求める。 $\Delta=0.4$:$\|p^{\mathrm U}\|>0.4$ なので Cauchy 点は $-0.4\,g/\|g\|$ で、dogleg の点もこれに一致する。厳密解は $\bigl(\frac2{4+\lambda}\bigr)^2+\bigl(\frac1{2+\lambda}\bigr)^2=0.16$ を解いて得る。

不定なモデルの部分問題

$g=(1,1)$、$B=\mathrm{diag}(-2,1)$、$\Delta=1$ のとき、部分問題の解と、Cauchy 点、Newton の点 $-B^{-1}g$ のモデルの値を比べよ。
使う公式:thm-tr-subproblem。
答え:$B+\lambda I$ が半正定値であるには $\lambda\ge2$ が必要なので、$\lambda>0$ で解は球面上にある。$p(\lambda)=-\bigl(\frac1{\lambda-2},\frac1{\lambda+1}\bigr)$ について $\|p(\lambda)\|=1$ を解くと $\lambda\approx3.032248$、$p^*\approx(-0.968760,-0.248001)$、$q(p^*)\approx-2.124504$。Cauchy 点は $g^{\mathsf T}Bg=-1\le0$ より $\tau=1$ で $-\frac1{\sqrt2}(1,1)$、$q\approx-1.664214$。Newton の点 $(0.5,-1)$ は $q$ の鞍点で $q=-0.25$ にすぎず、しかも $\|(0.5,-1)\|>1$ である。

$B$ が正定値でなくても部分問題は球の上の連続関数の最小化として必ず解をもつ。この例では、負の曲率の方向 $x_1$ へ大きく進む解が選ばれている。Newton 法では、鞍点の方へ跳んでしまう。

Rosenbrock 関数

$f(x)=100(x_2-x_1^2)^2+(1-x_1)^2$ を $x_0=(-1.2,1)$ から、$B_k=\nabla^2f(x_k)$、部分問題は厳密に解き、$\Delta_0=1$、$\eta=0.1$、半径の上限 $100$ の信頼領域法で最小化せよ($\|g_k\|\le10^{-8}$ で止める)。部分問題の代わりに Cauchy 点を使うとどうなるか。
答え:$f(x_0)=24.2$、$g_0=(-215.6,-88)$ で、$\nabla^2f(x_0)$ の固有値は約 $23.63$ と $1506.37$ である。厳密解を使うと 25 回(うち受け入れ 22 回、失敗 3 回)で最小点 $(1,1)$ に達する。最初の 1 歩は内部の Newton の 1 歩で、$x_1=(-1.175281,1.380674)$ が受け入れられるが、次の回は半径 $1$ の球面上の解が $\rho_1\approx-0.43$ で退けられ、半径が $0.25$ に縮む。$k=21$ 以降は $\lambda=0$ の内部の解(Newton の 1 歩)が受け入れられ続け、$\|g_k\|$ は $0.374,\ 0.363,\ 9.5\times10^{-3},\ 3.0\times10^{-4}$ と減ったあと $10^{-8}$ 以下になる。Cauchy 点だけを使うと 19,490 回かかる。

Rosenbrock 関数の等高線と、信頼領域法の受け入れた点の列。最初の 4 回の信頼領域を点線の円で示す。 Rosenbrock 関数の等高線と、信頼領域法の受け入れた点の列。最初の 4 回の信頼領域を点線の円で示す。
谷底が曲がった Rosenbrock 関数では、半径の伸び縮みが谷の曲がり方に合わせて歩幅を調整している。Cauchy 点だけの方法は主定理の条件を満たすので理論上は収束するが、最急降下法と同じく谷の中でジグザグに進み、実用にならない。

使える条件と反例

条件 1〜4 は主定理の証明でそれぞれ使った。条件 2〜4 は 1 つずつ外すと結論が成り立たない(条件 1 だけを外した例は挙げない)。1・2 行目は $f(x)=\frac12x^2$、3 行目は $f(x)=-x$(どれも $n=1$)を使い、$B_k$ と $p_k$ を決めて反復を直接計算する。

外す条件反例成り立たなくなること
4. Cauchy 減少条件$f=\frac12x^2$、$x_0=1$、$B_k=1$、$\Delta_0=10$、$p_k=-2^{-(k+1)}g_k$$\rho_k=1$ で毎回成功するが、$x_k=\prod_{j=1}^{k}(1-2^{-j})\to0.288788\dots$ で、$\|g_k\|\to0.288788\ne0$
3. $\|B_k\|$ が有界$f=\frac12x^2$、$x_0=1$、$B_k=4^{k+1}$、$\Delta_0=10$、Cauchy 点$\rho_k=2-4^{-(k+1)}$ で毎回成功し半径は保たれるが、$x_k\to\prod_{j\ge1}(1-4^{-j})=0.688538\dots$ で、$\|g_k\|\to0.688538\ne0$
2. 下に有界$f(x)=-x$、$x_0=0$、$\Delta_0=1$、$B_k=0$、Cauchy 点$\rho_k=1$ で半径が倍々になり、$x_k\to+\infty$、$\|g_k\|=1$ のまま

1 行目では、1 歩の大きさ $2^{-(k+1)}|x_k|$ の和が有限なので、点は途中で止まる。予言の減少量 $(2^{-(k+1)}-\frac12 4^{-(k+1)})x_k^2$ は Cauchy 点の減少量 $\frac12x_k^2$ に比べて $0$ に近づき、条件 4 を満たす $c_1$ がない。2 行目では各回の 1 歩は Cauchy 点 $-x_k/4^{k+1}$ で、条件 4 の形の不等式 $m_k(0)-m_k(p_k)=\frac12\|g_k\|\cdot\|g_k\|/\|B_k\|$ は成り立つが、右辺の $\|B_k\|$ が際限なく大きくなるので減少量の和が有限に収まる。

反例の計算

上の表の $\rho_k$ と極限を確かめよ。
答え:1 行目は $\rho_k=1$、2 行目は $\rho_k=2-4^{-(k+1)}$($1.75$、$1.9375$、…)、3 行目は $\rho_k=1$。

途中の計算
途中の計算を開く

$f=\frac12x^2$、$B_k=b$、$p=-tx$($g=x$)とすると、予言 $=tx^2-\frac12bt^2x^2$、実際 $=\frac12x^2-\frac12(1-t)^2x^2=(t-\frac12t^2)x^2$。 1 行目は $b=1$ なので予言と実際が一致し $\rho_k=1$。$|p_k|< \Delta_k$ なので半径は変わらず $10$ のまま、$x_{k+1}=(1-2^{-(k+1)})x_k$。 2 行目は $b=4^{k+1}$、$t=1/b$(Cauchy 点:$\tau=|g|/(\Delta b)< 1$)なので予言 $=\frac{x^2}{2b}$、実際 $=\frac{x^2}b(1-\frac1{2b})$、$\rho_k=2-\frac1b$。 3 行目は $g_k=-1$、$B_k=0$ なので Cauchy 点は $p_k=\Delta_k$、モデルは $f$ と一致して $\rho_k=1$、$\|p_k\|=\Delta_k$ なので半径は倍になる。

条件 1(Lipschitz 連続)は段階 1 の誤差評価にだけ使う。

よくある誤り

誤り正しくは
部分問題の解は $-B^{-1}g$ を半径に縮めたもの半径に当たるときは $(B+\lambda I)p=-g$ で向きも変わる(ex-tr-dogleg の $\Delta=0.65$、$0.4$)
$B$ が正定値でないと部分問題は解けない球の上で必ず解があり、thm-tr-subproblem で特徴づけられる(ex-tr-indefinite)
$\rho_k$ が負なら計算の誤りモデルが外れて $f$ が増えただけで、その回を失敗として半径を縮めればよい
予言の減少量を $m_k(0)-m_k(p_k)$ の差で計算する値が近いと桁落ちする。$-g_k\cdot p_k-\frac12p_k^{\mathsf T}B_kp_k$ を直接計算する
主定理から点列が極小点へ収束する結論は $\liminf\|g_k\|=0$ だけで、極小点でなく鞍点の近くにとどまる可能性も否定していない
半径は大きいほど速い大きすぎると失敗が続いて縮むだけになる。成功して境界に当たったときだけ広げる

補足

Levenberg–Marquardt 法との関係 thm-tr-subproblem より、部分問題の解は $(B+\lambda I)p=-g$ の形をしている。半径の代わりに $\lambda$ を直接調整するのが Levenberg–Marquardt 法で、非線形の 最小二乗法 で $B=J^{\mathsf T}J$($J$ は残差のヤコビ行列)とするものがよく使われる。$\lambda$ が大きいと $p\approx-g/\lambda$ で最急降下に近く、$\lambda\to0$ で Newton 型の 1 歩になる。
直線探索との比較 直線探索の方法では、$B_k$ が正定値でないと $-B_k^{-1}g_k$ が降下方向にならず、$B_k$ を修正する必要がある。信頼領域法は $B_k$ が不定でも部分問題がそのまま意味をもち、負の曲率の方向を利用できる(ex-tr-indefinite)。その代わり、1 回ごとに部分問題を解く手間がかかる。
大きな問題 変数が多いと固有分解が重いので、共役勾配法を球の中で打ち切る方法(Steihaug の方法)などで部分問題を近似的に解く。この記事ではその詳細には立ち入らない。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する