非線形計画法

非線形計画法（ひせんけいけいかくほう、英: nonlinear programming, NLP）は、制約条件群と未知の実変数群から成る一連の等式と不等式で、制約条件または目的関数の一部が非線形なものについて、目的関数を最小化または最大化するような解を求めるプロセスである。また、非線形計画法の対象となる問題を非線形計画問題と呼ぶ。

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

問題は次のように単純化して定式化できる。

\max _{x\in X}f(x)

または

\min _{x\in X}f(x)

ここで

f:R^{n}\to R

X\subseteq R^{n}

解法

目的関数 f が線形で、制約空間がポリトープの場合、その問題は線形計画問題であり、線形計画法で解くことができる。

目的関数が凹関数（最大化問題）または凸関数（最小化）で制約集合が凸集合の場合、その問題は凸計画問題と呼ばれ、凸最適化の手法を用いることができる。

非凸計画問題にはいくつかの解法がある。1つは、線形計画問題の特殊な定式化を使う解法である。もう1つは分枝限定法を使う解法であり、問題を凸計画問題や線形計画問題に分割して解く。分割していくと、ある時点で元の問題の解ともなる解が得られ、それらの最小（または最大）が近似解法での解に一致する。この解は最適だが、必ずしも唯一ではない。このアルゴリズムは、近似解とのある許容差内の解が得られたときに停止させることもでき、そのような解を「ε最適 (ε-optimal)」と呼ぶ。ε最適で停止させることは、一般に有限時間内で停止することを保証するのに必要となる。大規模で難しい問題や不確実さを適切な信頼性推定で概算できるコストや値が不明確な問題で特に有効である。

可微分で制約が示されたとき、Karush-Kuhn-Tucker (KKT) 条件は最適解の必要条件を提供する。凸性がある場合、この条件は十分条件にもなる。

例

2次元の例

制約空間（水色）と目的関数（直線）の接点が解である。

単純な問題の例として、以下の制約条件群があり、

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

次の目的関数を最大化する問題を示す。

f(x) = x₁ + x₂

ここで x = (x₁, x₂) である。

3次元の例

制約空間（中央）と目的関数（面）の接点が解である。

次の問題の例として、以下の制約条件群があり、

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

次の目的関数を最大化する問題を示す。

f(x) = x₁x₂ + x₂x₃

ここで x = (x₁, x₂, x₃) である。

参考文献

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

外部リンク

ソフトウェア

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