非線形計画

OR事典

非線形計画

読み方：ひせんけいけいかく
【英】：nonlinear programming

概要

非線形計画問題に対する数値解法, 最適性条件, 双対性理論などを研究する分野.

詳説

　変数 がすべて連続変数で，目的関数および制約関数が線形とは限らない数理計画問題を非線形計画問題 (nonlinear programming problem) という．非線形計画問題は一般に

と表される．この問題の実行可能集合をと表す．そのとき，ある実行可能解 に対して

が成り立つならば， を最適解，あるいは大域的最適解 (global optimal solution) という．また，ある実行可能解 とその適当な近傍 に対して

が成り立つとき， を局所的最適解(local optimal solution) という．

　目的関数 と不等式制約関数 が凸関数，等式制約関数 がすべて1次関数であるような問題を凸計画問題 (convex programming problem) という．凸計画問題においては，任意の局所的最適解は必ず大域的最適解となる．しかしながら，凸計画問題ではない問題，すなわち非凸計画問題 (nonconvex programming problem)においては，一般に不特定多数の局所的最適解が存在し，大域的最適解を見つけるのは非常に困難であるため，局所的最適解を考察の対象とするのが普通である．また，非凸計画問題の大域的最適解を求める方法，いわゆる大域的最適化(global optimization) の方法も近年活発に研究されている [4]．

　非線形計画問題において，その最適解を特徴づける条件を一般に最適性条件 (optimality condition) という．特に，局所的最適解が満たすべき条件を最適性の必要条件といい，逆に局所的最適解であることを保証する条件を最適性の十分条件という．また，関数の勾配のみを用いる条件を1次の条件，ヘッセ行列を用いる条件を2次の条件という．よく知られたカルーシュ・キューン・タッカー条件は1次の必要条件である．

　双対性理論(duality theory) は線形計画のみならず非線形計画問題においても重要な役割を果たす．特に，ラグランジュの双対性やフェンシェルの双対性は，数理計画問題に対する解法の設計や解析において極めて有用である．

　パラメータ を含む非線形計画問題

において，パラメータ の値が変化したとき，最適解や目的関数の最小値が連続的に変化するための条件や，それらの変化率などの諸性質は安定性理論 (stability theory) の名のもとで研究されている．

　非線形計画問題の最適解の計算においては，適当な出発点から始めて，最適解に収束するような点列を次々に生成する反復法 (iterative method) が一般に用いられる．制約条件をもたない制約なし最適化問題 (unconstrained optimization problem) に対しては，準ニュートン法や共役勾配法などの効率的な反復法が，一般の制約付き最適化問題 (constrained optimization problem) に対しても，逐次2次計画法や内点法など様々な反復法が開発されている．現在，非線形計画において有効とされている反復法の多くはニュートン法に基づくものである．

　非線形計画においては，目的関数と制約関数が1回または2回連続的微分可能と仮定される場合が多いが，それらの仮定を満たさない問題もしばしば現れる．そのような微分不可能最適化問題に対しても最適性理論や数値解法の研究が進められている．非線形計画全般に関する比較的新しい事柄を解説した教科書に [1],[5]} などがある．

　非線形計画問題のなかで，目的関数が2次関数，制約関数がすべて1次関数であるようなものを2次計画問題 (quadratic programming problem) と呼ぶ．特に，目的関数が凸関数である凸2次計画問題に対しては，有限回の演算で最適解を見出すことが可能である．凸2次計画問題は最も基本的な非線形計画問題であり，逐次2次計画法など一般の非線形計画問題に対する反復法の部分問題としてもしばしば現れる．

　非線形計画に関連して相補性問題(complementarity problem) と呼ばれる重要な問題のクラスがある．相補性問題とは，変数 と同じ次元をもつベクトル値関数 に対して，次式を満たす を求める問題である．

特に， が1次関数のとき，線形相補性問題といい，それ以外のとき，非線形相補性問題という．2次計画問題のカルーシュ・キューン・タッカー条件は線形相補性問題として表されるので，線形相補性問題に対する効率的な方法は2次計画問題に対しても有効である [2,3]．相補性問題を含むクラスに変分不等式問題と呼ばれる問題がある．相補性問題や変分不等式問題は均衡モデルの定式化において特に有用である[3]．

　最適化問題，相補性問題などの数理計画問題において，与えられた任意の点から問題の解集合への距離を評価するために用いられる関数をエラーバウンド (error bound) という．エラーバウンドが存在するためには，一般に問題が何らかの正則条件を満たす必要がある．エラーバウンドは反復法における収束判定条件の設定や収束率の解析等において重要な役割を果たす [3]．

---

参考文献

[1] D.P. Bertsekas, Nonlinear Programming, Athena Scientific, 1995.

[2] R.W. Cottle, J.-S. Pang and R.E. Stone, The Linear Complementarity Problem, Academic Press, 1992.

[3] F.Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes 1 and 2, Springer, 2003.

[4] R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global Optimization, 2nd Edition, Kluwer Academic Publishers, 2000.

[5] J.Nocedal and S.J.Wright, Numerical Optimization, Springer, 1999.

「OR事典」の他の用語

非線形計画：	逐次2次計画法  非凸計画問題  非線形相補性問題  非線形計画  非線形計画問題  鞍点定理  高速微分法
組合せ最適化：	組合せ的爆発  計算の複雑さ  貪欲アルゴリズム  連結度  集合被覆問題  離散最適化問題  非線形計画

ウィキペディア

非線形計画法

出典: フリー百科事典『ウィキペディア（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) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ 群知能 ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア