Nonlinear programming — 非線形計画法

非線形計画法（ひせんけいけいかくほう; 英語: Nonlinear Programming, NLP）は、数理計画法およびオペレーションズ・リサーチの一分野であり、目的関数および/または制約の少なくとも1つが決定変数の非線形関数である最適化問題を扱う。

NLPは線形計画法の一般化であり、変数間の依存関係が厳密に比例関係にない（つまり、直線ではなく曲線で記述される）より広範な現実のシステムやプロセスをモデル化することができる。

対象と目的

非線形計画法は、次のような状況で最適解を見つけるために使用される。

• 目的指標（利益、コスト、効率など）の制御可能なパラメータへの依存性が非線形である場合（例：規模に対する収穫逓減、二乗コスト）。
• 資源や技術プロセスに関する制約が非線形な関係で記述される場合（例：化学反応、物理法則、経済的依存関係）。

NLPの問題は多くの分野で発生する：

• 技術設計（構造、プロセスの最適化）。
• 経済学・金融（リスクを考慮したポートフォリオ最適化、市場モデリング）。
• 化学工学（反応器の運転モード最適化）。
• 機械学習（ニューラルネットワークの学習、サポートベクターマシン）。
• 生産プロセス管理。
• ロジスティクス（非線形コストを考慮）。

NLP問題の数式表現

一般的な非線形計画問題は、次のように定式化される。

決定変数の値の組を見つけ出すことが求められる。この値の組は、非線形目的関数を最大化または最小化するものでなければならない。その際、変数の値は、不等式（例：「量AはB以下でなければならない」）または等式（例：「量Cは正確にDと等しくなければならない」）の形で表現される制約の系を満たす必要がある。目的または制約を記述する関数のうち、少なくとも1つが非線形であることが重要である。多くの場合、変数の値がゼロ以上であることを要求する非負条件が追加される。

制約を満たすすべての変数値の組の集合は、実行可能領域を形成する。

線形計画法との違い

非線形計画法は、線形計画法（LP）とは大きく異なる。

• 非線形性：目的関数または制約（あるいはその両方）が非線形な依存関係を含んでいる。
• 実行可能領域の特性：LPでは実行可能領域が常に凸多面体であるのに対し、NLPでは非凸である場合がある。
• 最適性の特性：NLPにおける最適解は必ずしも実行可能領域の頂点にあるとは限らず、領域の境界または内部に存在することがある。NLPでは、大域的最適解ではない局所的最適解が存在する可能性がある。
• 解法の複雑さ：NLP問題は一般的にLP問題よりも解くのがはるかに困難である。シンプレックス法のような、すべてのNLP問題に適用できる単一の万能なアルゴリズムは存在しない。

NLPの主な困難と課題

非線形計画問題の解決には、多くの困難が伴う。

• 局所的極値の存在：ほとんどのNLP手法は、局所的最適解（ある近傍で最良の解）を見つけることしか保証しない。大域的最適解（実行可能領域全体で最良の解）を見つけることは、特に非凸問題においては困難な課題である。
• 非凸性：問題が非凸である場合（目的関数または実行可能領域が非凸）、多数の局所的最適解が存在する可能性があり、標準的な勾配法はそれらの1つに「陥る」ことがある。
• 計算の複雑さ：NLPを解くためのアルゴリズムは、LPと比較してしばしば大幅に多くの計算資源を必要とする。

NLP問題の重要なクラス

全体的な複雑さにもかかわらず、効率的な解法が開発されているNLP問題の重要なサブクラスが存在する。

• 凸計画法：凸集合上の凸関数の最小化問題（または凹関数の最大化問題）。重要な特性：任意の局所的最小解は、大域的最小解でもある。これにより、最適解の探索が大幅に簡素化される。
• 二次計画法：目的関数が二次関数であり、すべての制約が線形である問題。
• 分離可能計画法：目的関数と制約が、それぞれ単一の変数にのみ依存する関数の和として表現できる問題。

NLP問題の解法

I. 無制約最適化手法（制約なしの最適化）

• 勾配法（最急降下法、共役勾配法）
• ニュートン法および準ニュートン法（例：BFGS）
• ヘッセ行列の近似を利用する手法

II. 制約付き最適化手法（制約ありの最適化）

• 変換法：
  • ペナルティ関数法（penalty methods）
  • バリア関数法（barrier methods）
• 方向探索法：
  • 実行可能方向法
• 最適性条件に基づく手法：
  • カルシュ・キューン・タッカー条件（KKT条件）に基づく手法
  • ラグランジュの未定乗数法
• 反復法：
  • 逐次二次計画法（SQP）
  • 内点法

III. 大域的最適化手法

• ヒューリスティックおよびメタヒューリスティック手法：
  • 遺伝的アルゴリズム
  • 焼きなまし法
  • タブーサーチ（tabu search）
• 決定論的手法：
  • 分枝限定法（branch and bound）
  • 特殊な構造を持つ問題のための大域的最適化アルゴリズム

参考文献

• バザラ M. S., シェティ C. M. 非線形計画法：理論とアルゴリズム. 1982.
• フィアッコ A. V., マコーミック G. P. 非線形計画法：逐次無制約最小化法. 1972.
• ヒンメルブラウ D. M. 応用非線形計画法. 1975.
• Nocedal, J., Wright, S. J. Numerical Optimization. 2nd ed. Springer, 2006.