制約条件のない最適化：刻み幅制御
はじめに
局所モデルが実際のヘッセ行列に基づいている「ニュートン法」を使っても，根あるいは最小値に近くない限り，モデルステップではそれ以上解に近付けないことがある．次の問題はその簡単な例である．
よい刻み幅制御アルゴリズムは，繰り返し，あるいは根や最小値付近からの逸脱を防止する．しかし，それと同時に，モデル関数に基づいたステップが適当な場合，刻み幅制御アルゴリズムはそれらを制限すべきではない．さもなければアルゴリズムの収束率は危うくされてしまう．よく使われる刻み幅制御アルゴリズムには，「直線探索法」と「信頼領域法」の2つがある．直線探索法では，モデル関数がステップの方向を与え，収束に至る適切な点を見付けるための探索がその方向に沿って行われる．信頼領域法ではモデル関数が信頼される距離が，ステップごとに更新される．モデルステップがその距離の中にあればそれが使われ，さもなければ信頼領域の境界におけるモデル関数の近似された最小値が使われる．一般に，信頼領域法の方がより強力ではあるが，こちらの方が多くの数値線形代数を必要とする．
どちらの刻み幅制御メソッドも当初は最小化を念頭に開発された．しかし，メリット関数とともに用いると，どちらも非線形方程式の根の探索にうまく適用できる．Wolfram言語では2ノルムのメリット関数 
が使われる．
直線探索法
「ニュートン」法のようなメソッドはステップを選択するが，そのステップは，関数についてのニュートンの二次モデルが，その関数を本当に反映している限りにおいてのみ妥当である．直線探索法の考えは，以下のような最小化の一次元問題を解くことにより，選ばれたステップの方向を使い長さを制御するというものである．
上記の関係が成り立つので，勾配が計算できれば事実上導関数を使った一次元の探索ができる．
一般に，有効な直線探索法は 
の方向のみを見る．妥当なメソッドは探索方向が 
で表される降下方向であることを保証すべきだからである．
探索方向が厳密に正しい方向であることは滅多にないので，
の現実な最小値を求めることは一般にそれほど努力に値するものではない．たいていは近付くだけで十分である．
進展を測る条件は候補 
についてのArmijoすなわち十分な降下条件と呼ばれる．
この条件でメソッドが収束することがよくあるが，メソッドによってはArmijoだけでは滑らかな関数の収束は保証できないこともある．以下のように曲率条件を加えるてみる．
すると，多くのメソッドが滑らかな関数について収束することが証明できる．これらの条件は文字列Wolfe条件として知られている．パラメータ 
と 
は"LineSearch"の"DecreaseFactor"->μ オプションと"CurvatureFactor"->η オプションで制御することができる．
"CurvatureFactor"->η のデフォルト値は 
である．しかし，Method->"ConjugateGradient"のときは例外で，アルゴリズムが厳密な直線探索に近いほどうまくいくので，
が使われる．
が小さいほど厳密な直線探索に近くなる．
二次元での反復探索を表すグラフを見ると，評価が直線探索の方向に沿って広がっているのに気が付く．一般に，条件を満足する点は，数回の反復で求められる．しかし，直線探索は常に条件を満足する点を見付けられる訳ではない．たいていの場合，条件が満たせるほど近くで点を計算するには，精度が不十分であるためである．また，完全には滑らかではない関数，あるいは最小値の近傍を極めてゆっくり変化する関数の場合も，条件を満足する点が見付からないことがある．
プロットからも分かるように，関数における実際の相違は，この点近くでの評価による相違に比べると無視できるほどなので，これでは問題に直面する．
関数の小さな変化がもっと重要なものとなるように，定数から引き算することも，役に立つことがある．
しかしこの場合，プロットからも分かるように，0付近で関数にかなり雑音があるので，近似はほんの少し近付くに過ぎない．
このように，正しい値のゼロに近付くほど，より正確に関数を計算するために，より高い精度が必要になる．
問題によっては，特に根または極小値から離れたところから始めた場合は，ステップを制限した方がよいかもしれない．このためには，直線探索法では"MaxRelativeStepSize"メソッドオプションを使う．そのデフォルト値は探索が制御できなくなるのを防ぎ，同時に，必要に応じて大きなステップを使った探索を妨げないようになっている．
"MaxRelativeStepSize"オプションを小さく設定し過ぎないように注意する必要がある．小さくし過ぎると，特に最小値や根がゼロ近くにある場合，収束に影響が出る．
次の表は直線探索法を制御するために使えるオプションのまとめである．
オプション名
|
デフォルト値
| |
| "Method" | Automatic | 直線探索を実行するメソッド．Automatic，"MoreThuente"，"Backtracking"，"Brent"のいずれか |
| "CurvatureFactor" | Automatic | Wolfe条件における0と1の間の因子  ． の値が小さいほど，直線探索の結果が正確になる |
| "DecreaseFactor" | 1/10000 | Wolfe条件における0と  の間の因子  |
| "MaxRelativeStepSize" | 10 | 現行探索点のノルムと相対的に取られる最大ステップ．正の数を取り，制限がない場合は を取る |
"StepControl"->"LineSearch"のメソッドオプション
以下のセクションではWolfram言語に実装されている3つの直線探索法について説明する．比較はRosenbrock関数を用いて行う．
MoreThuente法
FindMinimum，FindMaximum，FindFitで使っているデフォルトの直線探索法は[MT94]でMoreとThuenteによって説明されている．この方法は，囲い込み法と二次および三次の補間法を使って降下条件と曲率条件の両方を満足する点を探そうとする．
関数と勾配のみが評価される点は，両方の条件を満足しなかった直線探索で試みられる点である．"MaxRelativeStepSize"で制限されていない限り，直線探索は常にフルステップの長さ(
)から始まるので，フル（この場合はニュートン）ステップが直線探索の基準を満たせば，これが採用され，最小値近くにおける完全な収束率を保証する．
曲率の減少は，直線探索が厳密な最小値に近付いて終わったことを意味する．曲率が減少すると，ニュートン法で取られるステップ数が減るが，関数と勾配の合計評価回数は増える．
この例はより厳密な直線探索が必ずしもよい結果を生む訳ではないことの理由を示している．直線探索が狭い谷の底にステップを取ると，ニュートンステップは曲率を見ずに（谷の曲率は二次を超えている）谷に沿って動くので，ニュートンステップは，たとえ方向はよくとも，結果として長過ぎることになる．一方で，共役勾配法のようにメソッドによっては，収束を改善するためによりよい直線探索法が必要なものもある．
バックトラック法
これは，与えられた刻み幅で始め，刻み幅0に向けて後戻りし，十分な減少条件が見付かったところで止まる単純な直線探索である．一般的にいって，バックトラック法だけでは，たとえ洗練された関数でも曲率条件が満たせる保証はないので，メソッドの収束特性は保証されない．しかし，バックトラック直線探索法は各点で勾配を評価する必要がないので，勾配評価が相対的に高くつくのであれば，これを選ぶのがよいかもしれない．メリット関数の勾配評価には比較的コストの高いヤコビ行列の評価が含まれているので，FindRootの直線探索にはデフォルトでこのメソッドが使われている．
各バックトラックのステップは，多項式の補間を行い補間式の最小点を見付けることである．点 
はそれが 
から 
までの間にある限り使われる．ここで 
はパラメータ 
の直前の値であり
である．デフォルトにより， 
で 
だが，メソッドオプションの"BacktrackFactors"->{c1,c2}を使えばこれを制御することができる．因数に単一の値を与えると 
となり，補間は行われない．値1/2により2等分となる．
直線探索Method->"Backtracking"のメソッドオプション
ブレント法
このメソッドは直線探索に，導関数を用いない1変量のブレント法[Br02]使う．これは，減少因子や曲率には関係なく，許容範囲内で 
の最小値を求めようとする．実際のところ，これには2つの段階がある．まず，これは根を囲い込もうとする．次に「ブレント」の補間法と黄金分割法を結合したものを使って最小値を求めようとする．この直線探索の利点は，このメソッドは最小値を囲い込もうとして両方向を見るため，他の2つのメソッドとは違ってステップが降下方向ではなくてもよい点である．このため，このメソッドは導関数を用いない「主軸」法に非常に適している．この直線探索法の欠点は，一般に多くの関数評価を使う点で，他の2つのメソッドに比べて効率面で劣る．
の負の値を用いることができる．この例ではニュートンステップの数は比較的少ないが，関数評価の総数は他の直線探索法に比べてはるかに多くなっている：信頼領域法
信頼領域法は，現行の探索点付近の領域である．この領域では「極小値探索」の二次モデル
が正しいと「信頼されて」おり，この領域に収まるようにステップが選ばれる．信頼領域の大きさは，モデルが現実の関数評価とどれほど一致するかに基づいて，探索の過程で修正される．
非常に典型的な例では，信頼領域は
となるよう楕円となる．
は対角スケーリング（しばしば近似ヘッセ行列の対角線から取られる）で，
は信頼領域の半径である．この半径は各ステップごとに更新される．
二次モデルのみに基づいたステップだけが信頼領域内にあるときは，関数の値が小さくなっていくと仮定すると，そのステップが選ばれる．従って，「直線探索法」と同じように，刻み幅制御は二次モデルがよい状態である最小値近くのアルゴリズムの収束を妨げない．二次モデルに基づいたステップが信頼領域の外にある場合は，そのステップが信頼領域の境界上にある二次モデルの近似最小化になるような，信頼領域の境界までのステップのみが選ばれる．
一旦ステップ 
が選ばれると，関数は新しい点で評価され，実際の関数値と二次モデルで予測された値とが比較される．実際に計算されているのは実際の減少と予想された減少との割合である．
が1に近ければ，二次モデルの予想はきわめて正確で，領域を広げることができる．一方で，
が小さすぎると，領域は小さくなる．
が閾値
よりも小さい場合，このステップは拒絶され再計算される．この閾値はメソッドオプションの"AcceptableStepRatio"->η を使って制御できる．典型的な 
の値は，最小値に向かって進むステップが拒絶されるのを防ぐように，極めて小さくなっている．しかし，ある点における二次モデルを求めるのにかなりコストがかかるならば（例えばヘッセ行列の評価は比較的長時間かかる），
の値を大きくすることでヘッセ行列の評価回数を減らすことはできるが，関数の評価回数は増えることがある．
信頼領域アルゴリズムの開始には，初期半径
を決定しなければならない．デフォルトで，Wolfram言語は比較的ゆったりした相対刻み幅制限によって限定されたモデル(1)に基づいた刻み幅を用いる．しかし，これでは興味ある領域外に出てしまうこともある．そんなときは，オプション"StartingScaledStepSize"->Δ0を使って初期半径
を指定することができる．このオプションの名前にはScaledが含まれているが，これは信頼領域の半径は対角スケーリング 
を通して作用するもので，絶対刻み幅ではないからである．
探索範囲が広がり過ぎて関数の細かい構造がこのスケールからは読み取れなくなっているので，このプロットは極めて質が悪い．
任意のステップでΔk≤Δmax となるように，オプション"MaxScaledStepSize"->Δmax を使って，信頼領域の半径の全体的な最大範囲を設定することも可能である．
信頼領域法は，関数計算において数値的丸めを含む問題があるために滑らかではない関数を扱う際にも問題があることがある．関数が十分に滑らかでないと，信頼領域の半径がどんどん小さくなる．そして，結局のところ，半径が事実上ゼロになってしまう．
このメッセージは，信頼領域の大きさが探索点との大きさとの比較で事実上ゼロになったので，取られたステップが無視できる程度の効果しかないことを意味している．注：プラットフォームによっては機械演算における微妙な違いによりメッセージが表示されないことがある．これは数値的な不確かさによってメッセージが出るためで，この数値的不確かさはプラットフォームによって異なる．
一方向のプロットによって，何故これ以上の改善が望めないがよく分かる．Levenberg–Marquardt法がこのような状況で問題に陥った理由のひとつは，最小値で剰余が非零であるために，収束が比較的遅いということである．「ニュートン」法では収束がより速く，完全な二次モデルによってよりうまく刻み幅が見積もれるので，FindMinimumでデフォルトの許容範囲が満足されていることがより確実になる．
オプション名
|
デフォルト値
| |
| "AcceptableStepRatio" | 1/10000 | 予想に対する実際の減少が  のとき，探索が計算されたステップに移動する閾値  |
| "MaxScaledStepSize" | ∞ | すべてのステップについて信頼領域の大きさが となるような値 |
| "StartingScaledStepSize" | Automatic | 信頼領域の最初の大きさ |