非線形計画法のソースを表示

{{脚注の不足|date=2023年10月}}
'''非線形計画法'''（ひせんけいけいかくほう、{{lang-en-short|nonlinear programming, NLP}}）は、制約条件群と未知の実変数群から成る一連の[[方程式|等式]]と[[不等式]]で、制約条件または目的[[関数 (数学)|関数]]の一部が[[非線形]]なものについて、目的関数を最小化または最大化するような解を求めるプロセスである。また、非線形計画法の対象となる問題を'''非線形計画問題'''と呼ぶ。

== 非線形計画問題の数学的定式化 ==
問題は次のように単純化して定式化できる。
:<math>\max_{x \in X}f(x)</math>
または
:<math>\min_{x \in X}f(x)</math>
ここで
:<math>f: R^n \to R</math>
:<math>X \subseteq R^n</math>

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

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

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

可微分で制約が示されたとき、[[カルーシュ・クーン・タッカー条件|Karush-Kuhn-Tucker]] (KKT) 条件は最適解の必要条件を提供する。凸性がある場合、この条件は十分条件にもなる。

== 実装 ==
非線形計画ソルバーは以下のようにいくつか知られている:
* [[ALGLIB]]（C++, C#, Java, Python API）一次のあるいは導関数不要な非線形計画ソルバー
* [https://nlopt.readthedocs.io/en/latest/ NLopt]（C/C++ での実装、Julia, Python, R, MATLAB/Octave から利用可能）、非線形計画ソルバーが組み込まれている。
* [[SciPy]]（Pythonの科学的分野におけるデファクトスタンダード）scipy.optimize でソルバーが利用可能。（zero-order、first order、second orderによる）いくつかの非線形計画ソルバーが利用できる。
* [[IPOPT]]（C++ での実装、C, Fortran, Java, AMPL, R, Pythonなどで利用可能）（zero-order, and optionally first order and second order derivativesによる）[[内点法]]が実装されたソルバー。

== 例 ==
=== 2次元の例 ===
[[画像:Nonlinear programming jaredwf.png|thumb|right|制約空間（水色）と目的関数（直線）の接点が解である。]]
単純な問題の例として、以下の制約条件群があり、
:''x''<sub>1</sub> &ge; 0
:''x''<sub>2</sub> &ge; 0
:''x''<sub>1</sub><sup>2</sup> + ''x''<sub>2</sub><sup>2</sup> &ge; 1
:''x''<sub>1</sub><sup>2</sup> + ''x''<sub>2</sub><sup>2</sup> &le; 2
次の目的関数を最大化する問題を示す。
:''f''('''x''') = ''x''<sub>1</sub> + ''x''<sub>2</sub>
ここで '''x''' = (''x''<sub>1</sub>, ''x''<sub>2</sub>) である。

=== 3次元の例 ===
[[画像:Nonlinear programming 3D jaredwf.png|thumb|right|制約空間（中央）と目的関数（面）の接点が解である。]]
次の問題の例として、以下の制約条件群があり、
:''x''<sub>1</sub><sup>2</sup> &minus; ''x''<sub>2</sub><sup>2</sup> + ''x''<sub>3</sub><sup>2</sup> &le; 2  
:''x''<sub>1</sub><sup>2</sup> + ''x''<sub>2</sub><sup>2</sup> + ''x''<sub>3</sub><sup>2</sup> &le; 10
次の目的関数を最大化する問題を示す。
:''f''('''x''') = ''x''<sub>1</sub>''x''<sub>2</sub> + ''x''<sub>2</sub>''x''<sub>3</sub>
ここで '''x''' = (''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>) である。

== 参考文献 ==
* 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''. [http://www.optimization-online.org/DB_HTML/2007/09/1775.html].
* 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日）．

== 関連項目 ==
* [[曲線あてはめ]]
* [[最小二乗法]]
* [[線形計画問題]]
* [[最適化問題]]

== 外部リンク ==
*[http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html Nonlinear programming FAQ]
*[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary]
*[http://www.lionhrtpub.com/orms/surveys/nlp/nlp.html Nonlinear Programming Survey OR/MS Today]

;ソフトウェア
*[http://www.aimms.com/operations-research/mathematical-programming/nonlinear-programming AIMMS Optimization Modeling] AIMMS
*[http://www.ampl.com/ AMPL solver software] - 学生向けは無料
*[http://www.gams.com/ GAMS] General Algebraic Modeling System – 学生向けは無料
*[https://midaco-solver.jp/ MIDACO-SOLVER] – 4変数まで無料（Matlab, C/C++, Python, R, C#, Fortran：日本語あり）

{{主要な最適化問題の分類}}
{{最適化アルゴリズム}}

{{DEFAULTSORT:ひせんけいけいかくほう}}
[[Category:最適化]]
[[Category:オペレーションズリサーチ]]
[[Category:数学に関する記事]]