逐次線形計画法

ウィキペディア

逐次線形計画法

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

逐次線形計画法（ちくじせんけいけいかくほう、英: Successive Linear Programming, Sequential Linear Programming、略称：SLP）とは非線形計画問題に対して線形計画問題に近似して解く反復的解法である^[1]。準ニュートン法に類似しているが異なる解法である。

逐次線形計画法は最適解の推定値から開始し、テイラー展開によって一次近似（すなわち線形化）を行った問題を逐次解くことを繰り返している。線形化によって問題は線形計画問題となり、効率的に解くことができる。しかし線形化による問題には収束性が保証されないため、収束を保証するためには信頼領域法などの解法を適用する必要がある^[2]。

逐次線形計画法は1970年代から石油化学産業で広く使用されてきた^[3]。しかし、その後逐次線形計画法の代わりに逐次二次計画法が使用されるようになった。二次計画の子問題を解くのにかかる計算時間は線形計画の子問題よりも長いことがほとんどであるが、収束性が良さから近似の反復回数は減少するため、結果として総計算時間が逐次二次計画法の方が短いことが多い。

脚注

[脚注の使い方]

1. ^ (Nocedal & Wright 2006, p. 551)
2. ^ (Bazaraa, Sherali & Shetty 1993, p. 432)
3. ^ (Palacios-Gomez, Lasdon & Enquist 1982)

参考文献

• Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-30303-1 
• Bazaraa, Mokhtar S.; Sherali, Hanif D.; Shetty, C.M. (1993). Nonlinear Programming, Theory and Applications (2nd ed.). John Wiley & Sons. ISBN 0-471-55793-5 
• Palacios-Gomez, F.; Lasdon, L.; Enquist, M. (October 1982). “Nonlinear Optimization by Successive Linear Programming”. Management Science 28 (10): 1106–1120. doi:10.1287/mnsc.28.10.1106. 

関連項目

• 逐次二次計画法
• 逐次線形二次計画法（英語版）
• 拡張ラグランジュ法

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

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集