Skip to content
検索結果に戻る

非線形計画法

提唱者
Jorge Nocedal & Stephen Wright
年
2006
種類
Continuous mathematical optimization
系統
Mathematical programming

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

非線形計画法(NLP)は、目的関数または少なくとも1つの制約が非線形である問題を取り扱う数理最適化の一分野である。Jorge NocedalとStephen Wrightが2006年の画期的な著書で包括的に体系化したNLPは、工学、経済学、物理科学にわたって生じる連続的な意思決定問題に対する局所的または大域的に最適な解を見つけるための、逐次二次計画法(SQP)、内点法、準ニュートン法を含む勾配ベースのアルゴリズムを網羅している。

手法の背後にある直感

霧に覆われた丘陵地帯を、柵で囲まれた領域内に留まりながら下っていく状況を想像してみよう。地形全体を見ることはできないため、足元の傾斜(勾配)を感じ、下り坂に進むように歩行方向を調整し、各移動で柵を越えていないか(制約)を確認する。もし柵が曲がっていたり、丘が重なっていたりする場合、単純な直線経路ではうまくいかない。経路を曲げる必要がある。非線形計画法は、このプロセスを正確に定式化し、直感的な丘歩きを数学的に厳密なステップサイズと方向の規則に置き換える。

歴史学

非線形計画法の理論的基礎は、Karush (1939) および Kuhn と Tucker (1951) によって導出されたKKT条件に遡る。実用的なアルゴリズムは、SQP法、拡張ラグランジュ法、およびBFGS (1970) を含む準ニュートン更新の開発により、1960年代から1980年代にかけて加速した。NocedalとWrightの2006年の『Numerical Optimization』第2版は、収束理論、直線探索および信頼領域の枠組み、内点法を首尾一貫した現代的な扱いに統合した決定的な参考文献となった。

使うべき場面

目的関数または制約を精度を著しく損なうことなく線形化できない場合、かつ決定変数が連続である場合に非線形計画法を使用する。典型的な設定には、物理法則の制約を伴う工学設計、非線形リスク尺度を伴うポートフォリオ最適化、非線形モデル形式を伴う回帰などが含まれる。主要な仮定は、fとcが少なくとも2回連続的に微分可能であること(勾配ベースのソルバーの場合)、および制約資格条件が成立することである。変数が整数値である場合は、混合整数非線形計画法(MINLP)の拡張が適用される。凸問題の場合、内点法は大域的最適性を保証する。非凸問題の場合、局所的な保証のみが存在する。

限界と注意点

  • 非凸問題は局所最適性の保証しか提供しない。大域的解には追加の大域的探索戦略が必要となる。
  • 目的関数と制約が滑らかであること(少なくとも微分可能であること)を要求する。非滑らかな問題には、特殊な劣微分法が必要となる。
  • 厳密なヘッセ行列の評価が必要な場合、計算コストは問題サイズとともに大幅に増加する。
  • 制約資格条件が成立しない場合(例:縮退した実行可能点において)、KKT条件はその理論的根拠を失う。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 線形近似または二次近似では不十分な、幅広い種類の現実世界の問題を扱える。
  • 凸インスタンスに対しては、収束保証が十分に研究された成熟したアルゴリズム理論。
  • 効率的な勾配ベースのソルバー(SQP、内点法)は、実際には数千の変数にスケール可能。
  • 統一されたラグランジュの枠組みは、混合された等式および不等式制約を自然に扱う。

応用

  • 構造工学および航空宇宙工学:応力およびたわみ制約の下での重量最小化。
  • ポートフォリオ管理:非線形分散(リスク)予算の下での期待収益最大化。
  • 化学プロセス設計:熱力学的および安全制約の下での反応器収率最適化。
  • 機械学習:制約なしまたは制約付きNLPソルバーによるニューラルネットワークおよびカーネルモデルの学習。
  • エネルギーシステム:非線形物理制約を伴う電力網配電における最適潮流問題。

使い方

使い方

1

分析者は、R^nの決定変数xに対して最小化または最大化するスカラー目的関数f(x)を、等式制約c_i(x) = 0および不等式制約c_j(x) >= 0とともに定義する。候補解においてどの制約がアクティブであるか、および正則性条件(制約資格条件)が成立するかどうかを特定することは、この段階で極めて重要であり、どの最適性理論が適用されるかを決定する。

数式
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}
2

Karush-Kuhn-Tucker(KKT)条件は、局所最適解に対する一次の必要条件を提供する。これらは、ラグランジュ関数の定常性、不等式乗数に対する相補的スラックネス(lambda_j c_j = 0)、双対実行可能性(lambda_j >= 0)、および主実行可能性を要求する。アルゴリズムは、これらの条件を漸進的により厳密に満たす反復解を繰り返し構築し、二次十分条件によって定常点が実際に局所最小解であることを確認する。

数式
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}
3

各反復kにおいて、アルゴリズムは探索方向p_k(通常、ヘッセ行列の準ニュートン近似B_k(例:BFGS)または厳密な二次導関数システムを介して)と、Wolfe条件またはArmijo条件を満たすステップ長alpha_kを計算する。SQP法はp_kに対して二次部分問題を解く一方、内点法は不等式制約を処理し、反復解を実行可能領域の内部へ導くためにバリア項を追加する。

数式
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)
4

終了は、ラグランジュ関数の勾配ノルムと最大制約違反の両方が所定の許容誤差(epsilonおよびdelta)を下回ったときに発生する。NLPは一般に非凸であるため、アルゴリズムは局所最適解に収束する可能性がある。大域的最適解が必要な場合は、異なる開始点からの複数回の再起動や大域的探索戦略(分枝限定法、マルチスタート)が推奨される。

数式
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \delta

よくある落とし穴

  • 制約資格条件を無視し、縮退した点や実行不可能な点にKKT条件を盲目的に適用すると、誤った解が生じる。
  • スケーリングが不適切な変数を使用すると、ヘッセ行列の近似が悪条件になり、収束が遅くなったり失敗したりする。
  • 非凸設定で複数回の再起動を行わずに最初に見つかった局所最小解を受け入れると、大域的最適解を大幅に見逃す可能性がある。
  • 有限差分勾配近似は数値誤差を導入する。解析的微分または自動微分が強く推奨される。

よくある質問

すべての線形計画法は非線形計画法でもありますか?

はい。線形計画法は、目的関数とすべての制約がアフィンであるNLPの特殊なケースです。しかし、LPは線形性を利用するシンプレックス法や内点法を許容し、これらは一般的なNLPソルバーよりもはるかに効率的です。LPに一般的なNLPソルバーを使用することは無駄ですが、数学的には有効です。

KKT点が大域的最小解であるといつ信頼できますか?

NLPが凸である場合、つまりfが凸であり、実行可能集合が凸集合である場合、任意のKKT点は大域的最小解です。非凸問題の場合、この保証は成立せず、KKT点は(二次十分条件の下で)局所最小解にすぎません。それ以外の場合は、分枝限定法や凸緩和などの大域的最適化手法が必要です。

SQPと内点法の違いは何ですか?

SQPは、NLPを局所的に近似する二次計画部分問題を繰り返し解き、多くのアクティブ制約を持つ中小規模の問題によく用いられます。内点(バリア)法は、実行可能領域の厳密な内部に留まり、大規模な疎な問題に対してより良くスケールする傾向があります。どちらも適切な正則性条件下で超線形収束します。

関連する手法

参考文献

  1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

    ISBN:978-0-387-30303-1
    コピーしました。