逐次線形二次計画法

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "逐次線形二次計画法" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2017年11月)

逐次線形二次計画法（ちくじせんけいにじけいかくほう、英: Sequential linear-quadratic programming、略称：SLQP）とは、目的関数および制約条件を二種類の微分可能関数への近似を行う非線形計画問題に対する反復法の一種である。逐次二次計画法（SQP）に類似した解法であるが、逐次線形二次計画法では一連の最適化部分問題を解く手続きを行っている。両者の違いとしては:

• 逐次二次計画法では、各反復において解かれる部分問題が目的関数が二次関数であり、制約条件が線形の式で表される二次計画問題として記述される。
• 逐次線形二次計画法では、各反復において解かれる部分問題が有効制約を求めるための線形計画問題および各反復のステップを決定するための等式制約付き二次計画問題（EQP）の二種類の問題によって記述される。

部分問題の線形計画問題（LP）および等式制約付き二次計画問題（EQP）はこれらの問題を解くソルバーによって効率よく解くことができるため、この分解を用いた逐次線形二次計画法は大規模な最適化問題に対して逐次二次計画法より扱いやすい解法である。

逐次線形二次計画法は準ニュートン法と関連した解法であるとみなされることがあるが、異なった解法である。

ここでは以下の非線形計画問題を考える:

${\displaystyle {\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{s.t.}}&b(x)\geq 0\\&c(x)=0.\end{array}}}$

この問題に対するラグランジュ関数は^[1]、

${\displaystyle {\mathcal {L}}(x,\lambda ,\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(x),}$

と表される。ただし、${\displaystyle \lambda \geq 0}$ であり、${\displaystyle \sigma }$ はラグランジュ乗数を表す。

逐次線形二次計画法の線形計画（LP）フェーズでは、以下の線形計画問題を解く:

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d\\\mathrm {s.t.} &b(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}}$

ここで、${\displaystyle {\cal {A}}_{k}}$ をこの問題の最適解 ${\displaystyle d_{\text{LP}}^{*}}$ に対する（制約条件の各式において ${\displaystyle d_{\text{LP}}^{*}}$ 上でゼロとなる式の集合を表す）有効制約とする。そして、${\displaystyle b_{{\cal {A}}_{k}}}$、${\displaystyle c_{{\cal {A}}_{k}}}$ をそれぞれ ${\displaystyle {\cal {A}}_{k}}$ の要素に対応するベクトル ${\displaystyle b}$、${\displaystyle c}$ とする。

逐次線形二次計画法の等式制約付き二次計画（EQP）フェーズでは、反復における探索方向 ${\displaystyle d_{k}}$ を決定するために以下の等式制約付き二次計画問題を解く:

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d+{\tfrac {1}{2}}d^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\\mathrm {s.t.} &b_{{\cal {A}}_{k}}(x_{k})+\nabla b_{{\cal {A}}_{k}}(x_{k})^{T}d=0\\&c_{{\cal {A}}_{k}}(x_{k})+\nabla c_{{\cal {A}}_{k}}(x_{k})^{T}d=0.\end{array}}}$

なお、目的関数における ${\displaystyle f(x_{k})}$ は定数の項であるため、この最小化問題において省略されることがある。

• Jorge Nocedal; Stephen J. Wright (2006). Numerical Optimization. Springer. doi:10.1007/978-0-387-40065-5. ISBN 9780387303031. NCID BA78604474. LCCN 2006-923897. OCLC 209918411. http://www.ece.northwestern.edu/~nocedal/book/num-opt.html 

• ニュートン法
• セカント法
• 逐次線形計画法
• 逐次二次計画法

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

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

• 表示
• 編集