NAGの最適化アルゴリズムは、線形計画法と二次計画法のような特殊な問題カテゴリーを除き、極限で解\(x^*\)に収束する反復列\(\{x^{(k)}\}\)を生成します。この計算過程を終了するため、現在の解の推定値が十分に近似しているかを判断する収束テストが行われます。収束テストの詳細はセクション7で説明します。
大半の手法は、以下の式を満たす列\(\{x^{(k)}\}\)を構築します：
\(x^{(k+1)} = x^{(k)} + \alpha^{(k)} p^{(k)}\)
ここで、ベクトル\(p^{(k)}\)は探索方向と呼ばれ、\(\alpha^{(k)}\)はステップ長を表します。ステップ長\(\alpha^{(k)}\)は\(f(x^{(k+1)}) < f(x^{(k)})\)となるように選択され、セクション5.1で述べる1次元最適化技術のいずれかを用いて計算されます。
5.1 1次元最適化
NAGライブラリには、単一変数関数を最小化するための2つの特殊なソルバーが含まれています。どちらも安全策が組み込まれた多項式近似に基づいています。1つは関数評価のみを必要とし、2次多項式を適合させます。もう1つは関数と勾配の評価を必要とし、3次多項式を適合させます。詳細はGill et al. (1981)のセクション4.1を参照してください。
5.2 無制約最適化の手法
無制約最適化問題に対しては、様々な手法が開発されています。これらの手法の主な違いは、探索方向を定義する際に\(f(x)\)の導関数についてどの程度の情報を使用するかによって生じます。ここでは、無制約問題に対する3つの基本的なアプローチを説明します。これらは他の問題カテゴリーにも拡張可能です。
手法の完全な説明には膨大な量の記述が必要となるため、ここでは関連するプロセスの概要を示すにとどめ、詳細な説明については他の文献を参照するよう促します。
- ニュートン型手法（修正ニュートン法）
ニュートン型手法は、ヘッシアン行列\(\nabla^2 f(x^{(k)})\)またはその有限差分近似を用いて探索方向を定義します。ライブラリのソルバーは、ヘッシアンの要素を直接計算するサブルーチンを使用するか、有限差分でそれらを近似します。
ニュートン型手法は一般的な問題に対して最も強力な手法であり、2次関数の最小値を1回の反復で見つけることができます。詳細はGill et al. (1981)のセクション4.4および4.5.1を参照してください。
- 準ニュートン法
準ニュートン法は、ヘッシアン\(\nabla^2 f(x^{(k)})\)を行列\(B^{(k)}\)で近似します。この行列は各反復で更新され、現在の探索方向\(p^{(k)}\)に沿った\(f\)の曲率に関する情報を取り込みます。ニュートン型手法ほど堅牢ではありませんが、ヘッシアンを直接計算したり有限差分で近似したりしないため、準ニュートン法はより効率的な場合があります。準ニュートン法は、変数の数を\(n\)とすると、\(n\)回の反復で2次関数を最小化します。詳細はGill et al. (1981)のセクション4.5.2を参照してください。
- 共役勾配法
ニュートン型手法や準ニュートン法と異なり、共役勾配法は\(n \times n\)行列の保存を必要としないため、大規模な問題を解くのに適しています。
5.3 非線形最小二乗問題の手法
非線形最小二乗問題は、データフィッティングなど多くの応用分野で重要です。これらの問題を解くための手法は、一般的な非線形最適化手法と類似していますが、ヘッシアン行列の特殊な構造を活用して計算効率を高めています。
目的関数が次の形式で表される場合：
\(f(x) = \sum_{i=1}^m r_i^2(x)\)
ヘッシアン行列は以下のように表現されます：
\[ \nabla^2 f(x) = 2(J(x)^T J(x) + \sum_{i=1}^m r_i(x) \nabla^2 r_i(x)) \]
ここで、\(J(x)\)は\(r(x)\)のヤコビアン行列です。
解の近傍では、\(\|r(x)\|\)が\(\|J(x)^T J(x)\|\)に比べて小さくなることがよくあります（例えば、\(r(x)\)が観測データに対する非線形モデルの適合度を表す場合）。このような状況では、\(2J(x)^T J(x)\)が\(\nabla^2 f(x)\)の適切な近似となり、\(\{r_i(x)\}\)の2階導関数の計算や近似を避けることができます。詳細はGill et al. (1981)のセクション4.7を参照してください。
5.4 制約を扱う手法
最適化アルゴリズムで制約を扱う主な2つのアプローチがあります - アクティブセット逐次2次計画法（SQP）と内点法（IPM）です。これらのアルゴリズムは大きく異なる特徴を持つため、その理解が重要です。両アルゴリズムは互いに補完的な役割を果たします。比較する最も簡単な方法は、不等式制約の扱い方と、ソルバーが最適解にどのようにアプローチするか（KKT最適性測度の進行：最適性、実行可能性、相補性）を見ることです。
不等式制約は、その「二重の性質」のため、最適化の難しい部分です。最適解が不等式を厳密に満たす場合、つまり最適点が制約の内部にある場合、その不等式制約は結果に影響を与えず、モデルから削除できます。一方、不等式が等式として満たされる（解でアクティブである）場合、その制約は存在しなければならず、最初から等式として扱うことができます。これはKKT条件の相補性で表現されます。
アクティブセット法に基づくソルバーは、各反復で元の問題の2次近似を解きます。どの制約を保持（アクティブ）する必要があり、どれを無視できるかを推定しようとします。結果として、アルゴリズムは実行可能領域の「境界に沿って進む」ことになります。そのため、反復の早い段階ですべての線形制約（および非線形制約の局所線形化）に関して実行可能となり、これが反復を通じて維持されます。相補性はデフォルトで満たされ、アクティブセットが正しく決定され、最適性が許容範囲内にあれば、ソルバーは終了します。反復回数は多くなる可能性がありますが、各反復は比較的低コストです。詳細については、Gill et al. (1981)の第6章を参照してください。
一方、内点法は不等式制約によって定義される境界を避ける反復を生成します。ソルバーが進行するにつれて、反復は境界にますます近づくことが許され、最終的に境界上にある可能性のある最適解に収束します。実践的には、IPMは通常、数十回の反復しか必要としません。各反復はすべての変数と制約を考慮に入れた大規模な線形方程式系を解くことで構成され、各反復はかなり高コストです。3つの最適性測度はすべて同時に減少します。
多くの場合、特定の問題に対してどちらのアルゴリズムがより適しているかを予測することは難しいですが、以下の表でいくつかの初期的なガイダンスを提供できます：
| IPMの利点 | SQPの利点 |
|---|---|
| 2階導関数とその構造を利用可能 | ほとんどの反復で線形制約に関して実行可能性を保持 |
| 無制約または緩い制約のある問題に効率的 | 高度に制約のある問題に非常に効率的 |
| （凸および非凸の両方の）2次問題（QP）にも効率的 | 我々の経験では、病的な問題でより良い結果 |
| マルチコアアーキテクチャをより良く利用（マルチスレッド実装で） | 一般的に関数評価の回数が少ない（高コストな関数評価を持つ問題に効率的） |
| 新しいインターフェース、使いやすい | 1階導関数を必要とするが、関数値のみでも動作可能 |
| 良好な初期点を活用可能 | |
| ウォームスタートを許可（類似の問題のシーケンスに適している） | |
| 実行不可能性の検出 |
特定のアルゴリズムのみが提供する機能が必要でない限り、初期の選択は問題の導関数の利用可能性と制約の数（変数の数に対する線形および非線形制約の合計数の比率）に基づくべきです。
正確な2階導関数が利用可能な場合、制約の数が変数の数に近くない限り、IPMの方がうまく機能する可能性が高いです。同様に、大規模な問題で制約が比較的少ない場合（例えば、40%未満）、特に問題規模が大きくなるにつれて、IPMの方が成功する可能性が高いです。
一方、導関数が利用できない場合、SQPまたはライブラリの専門的なアルゴリズム（導関数フリー最適化、セクション2.5参照）を使用する必要があります。制約の数が増えるにつれて、SQPの方が速くなる可能性があります。
どちらのカテゴリーにも明確に当てはまらない問題については、どちらのソルバーがより効果的かを予測するのは難しく、いくつかの実験が必要かもしれません。
5.5 多目的最適化を扱う手法
多目的最適化問題は、単一目的の問題とは異なるアプローチが必要です。複数の目的関数\(f_i(x)\)（\(i > 1\)）を同時に最小化する必要がある場合、主に2つのアプローチがあります。ここでは、多目的最適化問題を解決するための主要な手法について説明します。
個々の目的を1つの複合目的にまとめる方法： 典型的には、目的の重み付け和を用います。例えば、 \(w_1 f_1(x) + w_2 f_2(x) + \cdots + w_n f_n(x)\) ここで、重みは対応する目的の相対的重要性を表現します。理想的には、各\(f_i(x)\)が解においてほぼ同じ大きさになるべきです。
目的を重要性順に並べる方法： \(f_i\)が\(f_{i+1}(x)\)より重要であるように順序付けられていると仮定します（\(i = 1, 2, \ldots, n-1\)）。多目的最適化の辞書的アプローチでは、一連の部分問題を解きます。まず、目的関数\(f_1(x)\)に対する問題を解き、その最小値を\(r_1\)とします。\((i-1)\)個の部分問題が結果\(r_{i-1}\)で解かれた後、部分問題\(i\)は\(\min(f_i(x))\)となります。ただし、\(r_k \leq f_k(x) \leq r_k\)（\(k = 1, 2, \ldots, i-1\)）および他の制約が条件となります。 \(f_k\)の境界は必要に応じて緩和できます。
一般に、E04章のNAGの数理最適化ソルバーを使用する場合、局所最小値のみが見つかります。これは、他の目的の最適解を悪化させずに、個々の目的のより良い解が存在する可能性があることを意味します。理想的には、パレート解を求めます。これは、1つの目的の改善が他の目的の悪化によってのみ達成できる解です。
パレート解を得るには、E05章のソルバーを使用するか、大域最小値を導出するための実用的な試み（e05ucfを参照）を行うことができます。このアプローチでは、様々な初期点から始めて、各部分問題に対して複数の異なる最小値を計算します。得られた最良の解が大域最小値とみなされます。選択する初期点が多いほど、計算された大域最小値の信頼度が高くなります。