非線形ひせんけい計画けいかく法ほう

非線形ひせんけい計画けいかく法ほう（ひせんけいけいかくほう、英えい: 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 – 学生がくせい向むけは無料むりょう