非線形計画法

非線形計画法（ひせんけいけいかくほう、）は、制約条件群と未知の実変数群から成る一連の等式と不等式で、制約条件または目的関数の一部が非線形なものについて、目的関数を最小化または最大化するような解を求めるプロセスである。また、非線形計画法の対象となる問題を非線形計画問題と呼ぶ。
非線形計画問題の数学的定式化.
問題は次のように単純化して定式化できる。
または
ここで
解法.
目的関数 "f" が線形で、制約空間がポリトープの場合、その問題は線形計画問題であり、線形計画法で解くことができる。
目的関数が凹関数（最大化問題）または凸関数（最小化）で制約集合が凸集合の場合、その問題は凸計画問題と呼ばれ、凸最適化の手法を用いることができる。
非凸計画問題にはいくつかの解法がある。1つは、線形計画問題の特殊な定式化を使う解法である。もう1つは分枝限定法を使う解法であり、問題を凸計画問題や線形計画問題に分割して解く。分割していくと、ある時点で元の問題の解ともなる解が得られ、それらの最小（または最大）が近似解法での解に一致する。この解は最適だが、必ずしも唯一ではない。このアルゴリズムは、近似解とのある許容差内の解が得られたときに停止させることもでき、そのような解を「ε最適 (ε-optimal)」と呼ぶ。ε最適で停止させることは、一般に有限時間内で停止することを保証するのに必要となる。大規模で難しい問題や不確実さを適切な信頼性推定で概算できるコストや値が不明確な問題で特に有効である。
可微分で制約が示されたとき、Karush-Kuhn-Tucker (KKT) 条件は最適解の必要条件を提供する。凸性がある場合、この条件は十分条件にもなる。
例.
2次元の例.
単純な問題の例として、以下の制約条件群があり、
次の目的関数を最大化する問題を示す。
ここで x = ("x"1, "x"2) である。
3次元の例.
次の問題の例として、以下の制約条件群があり、
次の目的関数を最大化する問題を示す。
ここで x = ("x"1, "x"2, "x"3) である。