非線形計画法

非線形計画法とは

非線形計画法（Nonlinear Programming, NLP）は、制約条件や目的関数に非線形性を含む最適化問題を解くための数学的な手法です。具体的には、与えられた制約条件の下で、ある目的関数を最大化または最小化するような変数の値を求めるプロセスを指します。線形計画法が線形の関係のみを扱うのに対し、非線形計画法はより複雑で現実的な問題を扱うことができます。

非線形計画問題の数学的定式化

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

最大化問題:


max f(x)
x ∈ X


最小化問題:


min f(x)
x ∈ X


ここで、

`f(x)` は目的関数（最大化または最小化したい関数）であり、`R^n` から `R` への写像です。
`x` は変数ベクトルであり、`R^n` に含まれます。
`X` は制約集合であり、`R^n` の部分集合です。

これらの定式化において、目的関数 `f(x)` または制約集合 `X` のいずれか、あるいは両方が非線形である場合に、非線形計画問題となります。

解法

非線形計画問題を解くための手法は、問題の特性によって異なります。以下に代表的な解法をいくつか紹介します。

1. 線形計画法: 目的関数が線形で、制約条件が線形の不等式で表される場合、線形計画法が適用可能です。しかし、非線形問題の場合は直接的には適用できません。
2. 凸計画法: 目的関数が凹関数（最大化問題の場合）または凸関数（最小化問題の場合）であり、制約集合が凸集合である場合、凸計画問題となり、凸最適化の手法が利用できます。凸計画問題は、局所最適解が必ず大域最適解となるという特徴があります。
3. 非凸計画問題の解法: 一般的な非凸計画問題には、以下のようないくつかの解法があります。
線形計画問題への変換: 問題を特殊な線形計画問題として定式化し、解く方法です。近似解を求める際に有効です。
分枝限定法: 問題をより単純な凸計画問題や線形計画問題に分割して解き、その解を基に元の問題の近似解を求める方法です。分割を繰り返すことで、最適解に近づけます。この方法では、近似解との許容誤差範囲内の解が得られた時点で計算を終了することが一般的であり、その解を「ε最適解」と呼びます。特に、大規模な問題や、コストや値が不明確で信頼性評価が必要となる問題に対して有効です。
4. Karush-Kuhn-Tucker (KKT)条件: 制約条件が与えられ、かつ微分可能な関数に対して、最適解の必要条件を与える理論です。問題が凸性を持つ場合には、十分条件にもなります。

例

2次元の例

以下の制約条件の下で、

x1 ≥ 0
x2 ≥ 0
x1² + x2² ≥ 1
x1² + x2² ≤ 2

目的関数 `f(x) = x1 + x2` を最大化する問題を考えます。ここで `x = (x1, x2)` です。この問題は、円環状の領域内での最適化問題を表現しています。

3次元の例

以下の制約条件の下で、

x1² − x2² + x3² ≤ 2
x1² + x2² + x3² ≤ 10

目的関数 `f(x) = x1x2 + x2x3` を最大化する問題を考えます。ここで `x = (x1, x2, x3)` です。この問題は、より複雑な3次元空間での最適化問題を表現しています。

関連分野

非線形計画法は、さまざまな分野と密接に関わっています。

曲線あてはめ: データに最もよく当てはまる曲線を求める問題に利用されます。
最小二乗法: 誤差の二乗和を最小化する手法で、非線形計画法の問題として定式化されることがあります。
線形計画問題: 非線形計画法の特殊なケースであり、より単純な最適化問題を扱います。
最適化問題: 非線形計画法は、一般的な最適化問題の一部です。

まとめ

非線形計画法は、現実世界の複雑な問題を解決するための強力なツールです。その応用範囲は非常に広く、工学、経済学、機械学習など、様々な分野で活用されています。非線形計画法の理解は、現代社会における様々な課題解決に貢献します。

参考文献

Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing.
Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons.
Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific.
Jalaluddin Abdullah, Optimization by the Fixed-Point Method, Version 1.97.
Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer.
矢部博、八巻直一：「非線形計画法」，朝倉書店，（1999年6月10日）.
茨木俊秀，福島雅夫：「最適化の手法」（第4章'非線形最適化'），共立出版，（1993年7月20日）．
茨木俊秀：「最適化の数学」（第3章'非線形計画問題のアルゴリズム'），共立出版、（2011年6月25日）．
矢部 博:「工学基礎 最適化とその応用」（第4章，第5章），数理工学社、（2006年4月）．
田村 明久, 村松 正和：「最適化法」（第3章'非線形計画'），共立出版、（2002年4月1日）．

外部リンク

Nonlinear programming FAQ
Mathematical Programming Glossary
Nonlinear Programming Survey OR/MS Today

ソフトウェア

AIMMS Optimization Modeling
AMPL solver software - 学生向けは無料
GAMS General Algebraic Modeling System – 学生向けは無料
MIDACO-SOLVER – 4変数まで無料（Matlab, C/C++, Python, R, C#, Fortran：日本語あり）

もう一度検索