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