非線形計画法

目的関数か制約のどちらかが非線形な最適化問題。Nonlinear Programming、NLP。

$$\underset{x}{\min }f(x)\text{s.t.}{g}_i(x)\le 0,h_j(x)=0$$

最適性の条件#

制約付きの点が最適である条件は KKT 条件で与えられる。 凸問題なら必要十分、非凸なら必要条件にとどまる。

主な解法#

手法	考え方
逐次二次計画法 (SQP)	各反復で二次計画に近似して解く
内点法	制約を対数バリアで目的関数に取り込み、内部から近づく
拡張ラグランジュ法	ペナルティと乗数を併用
有効制約法	いま効いている制約だけを等式として扱う

大規模で滑らかな問題では内点法、中規模で高精度が要るなら SQP、 という使い分けがおおよその目安。

何が保証されるのか#

非凸の NLP で得られるのは、原則として 局所最適解（正確には KKT 点）。 大域最適性を主張するには凸性か、大域最適化専用の手法が要る。

参考文献#

• Jorge Nocedal, Stephen J. Wright. Numerical Optimization, 2nd ed. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/