Jan Fiala & Benjamin Marteau (Numerical Algorithms Group)
はじめに
非線形プログラミングは、数学モデリング実務者にとって主要なツールの1つです。その応用は多くの産業と学術分野に及びます:
- 金融（ポートフォリオ最適化、モデルキャリブレーション）
- マルチフィジックスモデリング（石油・ガス貯留層モデリング、気象学、気候シミュレーション、工学）
- 統計学（機械学習、データフィッティング）
このようなモデルは以下のように定式化できます：
\[ \begin{aligned} \min_{x\in\mathbb{R}^n} & \quad f(x) \\ \text{制約条件} & \quad h(x) = 0 \\ & \quad g(x) \geq 0 \end{aligned} \]
ここで、目的関数 \(f\) と制約 \(h\) および \(g\) は十分に滑らかな非線形関数です。現代の大規模アプリケーションでは、変数の数 \(n\) は \(10^4\) 以上のオーダーになることがあります。
ソルバーは一般に、カルーシュ・クーン・タッカー（KKT）最適性条件を満たす局所解（ある近傍内で最良の解）を見つけます。2つの主要な競合アプローチがあります：
- アクティブセット逐次二次計画法（SQP）
- 内点法（IPM）
両アプローチとも、制約を扱う根本的に異なる方法のため、実践において重要な役割を果たしています。
このドキュメントの残りの部分では、nAGライブラリにおけるこれらの方法の2つの実装を比較します：
内点法（IPM）
最適化問題では、制約条件を満たしながら最適解を見つける必要があります。特に、不等式制約（例：x ≥ 0）の扱いが難しいです。なぜなら、各制約が「効いている」か「効いていない」かの2つの状態しかないからです。
この状況は数学的に次のように表現されます：
\[\mu_k g_k(x) = 0 \text{ 各制約 } k \text{ について} \qquad (1)\]
ここで、\(g_k(x)\) は制約条件、\(\mu_k\) はその制約の重要度を表す値（ラグランジュ乗数と呼ばれます）です。式(1)は次の2つの状況のいずれかを表しています：
- 制約がアクティブ：\(g_k(x) = 0\)（制約の境界上にある）
- 制約が非アクティブ：\(\mu_k = 0\)（制約が余裕を持って満たされている）
内点法（IPM）は、この「アクティブかそうでないか」の二者択一を避けるため、問題を次のように変形します：
\(\mu_k g_k(x) = \nu\) （ここで \(\nu\) は小さな正の数）
この変形により、全ての制約を常に「少しアクティブである」状態で扱えるようになり、計算が安定します。これは、制約の状態が急激に変化することがなくなり、解の探索過程がより滑らかになるからです。
内点法の各ステップ
- 変形された問題の解を1回だけ改善します（ニュートン法を使用）。
- 得られた結果を使って、解の推定値を更新し、\(\nu\) を少し小さくします。
- これを繰り返し、最終的に \(\nu\) をほぼ0にすることで、元の問題の解に近づきます。
このアプローチにより、内点法は不等式制約を効率的に扱うことができ、大規模な最適化問題でも安定した解法を提供します。
内点法（IPM）の特性
- 計算量の多い反復を少ない回数で実行します。各反復で問題全体を考慮するため、1回の計算に時間がかかります。
- 効率的な行列計算に依存しています。大規模な行列演算を高速に行うことが重要です。
IPMソルバーは、制約の少ない大規模な非線形問題に特に適しています。制約が少ないほど、各反復の計算量が減少するためです。
逐次二次計画法（SQP）
逐次二次計画法（SQP）は、どの不等式制約 \(g_k\) が実際に影響しているかを推測し、その推測を徐々に改善していきます。影響のない制約は無視できるので、残りの制約だけを考慮すればよくなります。これにより、問題の複雑さを大幅に減らすことができます。
1. 初期化
- 問題を簡略化した二次関数モデルを作ります。これは元の問題の局所的な近似です。
- どの制約が重要かについて、最初の推測を行います。この推測は後の反復で改善されます。
2. 各反復
- 簡略化したモデルを解きます。前回の結果を利用して効率的に計算します。これを「ウォームスタート」と呼びます。
- 新しい解 \(x_{k+1}\) と重要な制約の推測を更新します。これにより、より良い近似解が得られます。
- \(x_{k+1}\) を使って新しい簡略化モデルを作ります。このモデルは新しい解の周りでより正確になります。
逐次二次計画法（SQP）の特性
- 計算量の少ない反復を多数回実行します。各反復は比較的高速ですが、収束までに多くの反復が必要な場合があります。
- 重要な制約のみを考慮して効率的に計算します。これにより、問題の次元を効果的に減らすことができます。
⇒ 重要な制約が多いほど、各反復の計算量が減ります。なぜなら、考慮すべき自由度が減少するからです。
SQPソルバーは、制約の多い大規模な非線形問題に特に適しています。制約が多いほど、SQPの利点が発揮されます。
CUTEstテストセットからの選択された問題での実証
高度に制約された問題
| 名前 | 変数数 | 制約数 | SQP時間 (秒) | IPM時間 (秒) |
|---|---|---|---|---|
| MINC44 | 1113 | 1033 | 0.28 | 7.60 |
| READING8 | 2002 | 1000 | 9.78 | 251.12 |
| NCVXQP6 | 10000 | 7500 | 3.60 | 613.38 |
| MADSSCHJ | 201 | 398 | 0.34 | 5.51 |
緩やかに制約された問題
| 名前 | 変数数 | 制約数 | SQP時間 (秒) | IPM時間 (秒) |
|---|---|---|---|---|
| JIMACK | 3549 | 0 | 542.42 | 8.12 |
| OSORIO | 10201 | 202 | 303.00 | 0.78 |
| TABLE8 | 1271 | 72 | 3.80 | 0.04 |
| OBSTCLBL | 10000 | 1 | 40.84 | 0.50 |
これらの結果は、SQPとIPMの性能特性を明確に示しています。高度に制約された問題では、SQPが一貫して優れたパフォーマンスを示しており、特に大規模な問題（NCVXQP6）で顕著です。これは、SQPが制約の多い問題で効率的に動作するという理論的予測と一致しています。
一方、緩やかに制約された問題では、IPMが優位性を発揮しています。特に、無制約問題（JIMACK）や制約の少ない大規模問題（OSORIO、OBSTCLBL）でIPMの効率が際立っています。これは、IPMが制約の少ない問題や大規模な問題に適しているという特性を裏付けています。
使用の推奨
制約の数はソルバーの収束に影響を与える唯一の要因ではありません：
IPM (e04st) の利点
- 無制約または緩やかに制約された問題に効率的
- 2次導関数を利用可能
- 二次問題に効率的
- マルチコアアーキテクチャの活用が優れている
- 新しく、よりシンプルなインターフェース
SQP (e04vh) の利点
- 高度に制約された問題に効率的
- 良好な初期点を活用可能
- 最適化全体を通じて線形制約に関して実行可能性を維持
- 病的な問題で通常より良い結果
- 通常、より少ない関数評価を必要とする
- 実行不可能性の検出
- ウォームスタートを許可
この記事の原文（英語ポスター）はこちらからご参照いただけます。