非線型計画問題

ウィキペディア

非線形計画法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/12 03:48 UTC 版)

この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2023年10月）

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

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

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

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

制約空間（水色）と目的関数（直線）の接点が解である。

単純な問題の例として、以下の制約条件群があり、

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 – 学生向けは無料
• MIDACO-SOLVER – 4変数まで無料（Matlab, C/C++, Python, R, C#, Fortran：日本語あり）

表 話 編 歴 主要な最適化問題の分類（最適化）
凸最適化 線形計画問題 分数計画問題（英語版） 整数計画問題 二次計画問題 非線形計画問題 確率最適化法（英語版） ロバスト最適化（英語版） 組合せ最適化 半無限計画問題（英語版） 二次錐計画問題 半正定値計画問題 メタヒューリスティクス 制約充足性（英語版） 多目的最適化（英語版） 均衡制約付き数理計画問題 錐最適化（英語版） 二次制約付き二次計画問題（英語版）

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法	Optimization computes maxima and minima.
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア

ウィキペディア小見出し辞書

非線型計画問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/05/28 18:23 UTC 版)

「双対問題」の記事における「非線型計画問題」の解説

非線型計画問題では、制約条件が線型である必要はない。それ以外は線型計画問題とほぼ同じ原則が適用される。 非線型問題が一意な広域最適解を持つかどうかを確認するには、凸性（convexity）などに単純化する方法が便利である。制約条件や目的関数の曲率が適当な領域で常に凸なら、一意な広域最適解があるといえる。 ここでカルーシュ・クーン・タッカー条件 (KKT条件) が重要となる。これは、非線型計画問題が一意な大域最適解を持つかどうかを判定するのに、凸性に基づいた十分条件を提供する。最適解の方向を定義できるようにするために必要な追加の条件が存在する。最適解は局所解であって、大域最適解ではない可能性もある。