非線形計画法

非線形計画法（ひせんけいけいかくほう、英: nonlinear programming, NLP）は、制約条件群と未知の実変数群から成る一連の等式と不等式で、制約条件または目的関数の一部が非線形なものについて、目的関数を最小化または最大化するような解を求めるプロセスである。また、非線形計画法の対象となる問題を非線形計画問題と呼ぶ。

非線形計画問題の数学的定式化

問題は次のように単純化して定式化できる。

${\displaystyle \max _{x\in X}f(x)}$

または

${\displaystyle \min _{x\in X}f(x)}$

ここで

${\displaystyle f:R^{n}\to R}$

${\displaystyle 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日）．

外部リンク

• Nonlinear programming FAQ
• Mathematical Programming Glossary
• Nonlinear Programming Survey OR/MS Today

ソフトウェア

• AIMMS Optimization Modeling AIMMS
• AMPL solver software - 学生向けは無料
• GAMS General Algebraic Modeling System – 学生向けは無料

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）