1 概要
逐次二次計画法は、制約付き非線形最適化を扱う反復法の一つである。元の問題を現在点の近傍で二次計画問題に置き換え、その解に基づいて次の反復点を更新する。目的は、制約を保ちながら目的関数を効率よく減少させることである。
1.1 定義
この手法では、非線形目的関数と制約条件を持つ問題を、各反復で局所的な二次近似と線形化によって小規模な最適化問題に変換する。得られた部分問題を解き、そこから探索方向と更新量を決める。
1.2 位置づけ
逐次二次計画法は、数値最適化の中でも制約処理に強い代表的手法に属する。線形計画や逐次線形計画法よりも表現力が高く、非線形性が強い問題に対しても適用しやすい。一方で、勾配や二次情報を要するため、情報が粗い場合は別手法が選ばれることもある。
1.3 適用対象
対象となるのは、等式制約や不等式制約を含む滑らかな最適化問題である。設計変数が連続で、微分可能な目的関数を持つ場合に特に有効であり、工学、制御、学習、資源配分などに広く用いられる。
2 理論的基礎
逐次二次計画法の理解には、非線形最適化、局所近似、ラグランジュ理論の三つが重要である。これらが、反復ごとに問題を簡約しながら解を改善する枠組みを支えている。
2.1 非線形最適化問題
非線形最適化問題は、非線形な目的関数や制約条件を最小化または最大化する問題である。逐次二次計画法は、この種の問題を直接解く代わりに、各点で近似問題へ置き換えて進む。
2.1.1 目的関数
目的関数は、最小化したい性能指標や損失を表す。滑らかであれば、勾配や曲率の情報を用いて局所的な変化を精密に捉えられる。
2.1.2 制約条件
制約条件は、許容される解の範囲を定める。等式制約は厳密な関係を、不等式制約は上限・下限や安全条件のような条件を表す。逐次二次計画法では、これらを線形化して扱うことが多い。
2.2 二次近似
二次近似は、現在点の近傍で目的関数を二次式として表す考え方である。これにより、非線形問題を二次計画問題として解きやすくする。
2.2.1 テイラー展開
テイラー展開では、関数を現在点の値、一次項、二次項で近似する。一次項は傾きを、二次項は曲率を表し、局所的な挙動を再現する役割を持つ。
2.2.2 局所モデル
局所モデルは、限られた近傍でのみ妥当な簡約表現である。逐次二次計画法では、このモデルが各反復の判断基盤となり、現実の問題を計算可能な規模に落とし込む。
2.3 ラグランジュ関数
ラグランジュ関数は、目的関数に制約を組み込むための補助的な関数である。乗数を用いて、制約付き問題を解析しやすい形にまとめる。
2.3.1 停留条件
停留条件は、最適点候補でラグランジュ関数の勾配が消えることを意味する。これは、制約を考慮したうえでの局所的な平衡状態を示す指標である。
2.3.2 制約最適性条件
制約最適性条件には、実行可能性、停留性、相補性などが含まれる。これらは最適解の必要条件として機能し、逐次二次計画法の収束判定にも関係する。
3 アルゴリズム
逐次二次計画法は、反復ごとに近似問題を構成し、その解を次の点へ反映する構造を持つ。実装では、探索方向、更新規則、歩幅制御が重要になる。
3.1 基本手順
基本的な流れは、初期点を選び、近似問題を作り、部分問題を解いて更新する、という順序で進む。反復は、改善が十分小さくなるか、条件を満たすまで続く。
3.1.1 初期点の設定
初期点は計算の出発点であり、収束先や効率に影響する。実行可能点から始める場合もあれば、違反を含む点から修正を重ねる場合もある。
3.1.2 部分問題の構成
部分問題では、目的関数を二次式で近似し、制約を線形化する。こうして得られる二次計画問題は、元の問題より扱いやすく、局所的な改善方向を与える。
3.1.3 解の更新
部分問題の解は、そのまま次の反復点に採用されるか、あるいは歩幅を調整して反映される。更新後は新しい点で関数値と制約違反を再評価する。
3.2 探索方向の決定
探索方向は、どの向きに進むと目的関数が改善するかを示す。制約を満たす範囲で、効率のよい方向を選ぶことが重要である。
3.2.1 勾配情報の利用
勾配は目的関数の増減方向を示す基本情報である。これを使うことで、減少が期待できる方向を見つけやすくなる。
3.2.2 ヘッセ行列の近似
ヘッセ行列は曲率を表すが、厳密計算が重い場合がある。そのため、近似行列を用いて計算負荷を抑えつつ、二次的な形状情報を取り込む。
3.3 ステップ長の決定
ステップ長は、探索方向にどれだけ進むかを決める量である。これが適切でないと、収束が遅くなったり、制約を破ったりする。
3.3.1 線形探索
線形探索は、候補となる歩幅を順に試し、改善が確認できる大きさを選ぶ方法である。比較的単純で、実装しやすい。
3.3.2 信頼領域
信頼領域では、近似が妥当とみなせる範囲内でのみ更新を行う。歩幅そのものではなく、近似の信頼できる半径を制御する点が特徴である。
4 実装上の要点
実用化では、理論だけでなく、収束判定、制約処理、数値誤差への配慮が欠かせない。計算機上では、安定性と効率の両立が求められる。
4.1 収束性
収束性は、反復を進めたときに解が最適点へ近づく性質を指す。条件が整えば、局所的に速い収束が期待できる。
4.1.1 局所収束
局所収束は、最適解の近くで解が急速に改善していく性質である。初期点が十分近いほど、この性質が生きやすい。
4.1.2 大域収束
大域収束は、遠い初期点からでも適切な条件の下で解へ近づく性質である。線形探索や信頼領域は、その実現を助ける代表的な仕組みである。
4.2 制約の扱い
制約処理は、この手法の中心的な課題の一つである。制約の種類に応じて、線形化や補助条件を使い分ける必要がある。
4.2.1 等式制約
等式制約は、厳密に満たすべき関係式である。部分問題では線形化されることが多く、ラグランジュ乗数が重要な役割を果たす。
4.2.2 不等式制約
不等式制約は、許容範囲を表す条件である。活性化する制約とそうでない制約を見分けながら、実行可能領域の内部や境界を移動する。
4.3 数値安定性
数値安定性は、丸め誤差や病的な条件によって計算が不安定にならないことを意味する。大規模計算では、特に注意が必要である。
4.3.1 ヘッセ行列の正定性
ヘッセ行列の正定性は、二次モデルが下に凸であることに関係する。これが保たれると、部分問題が解きやすくなり、更新の信頼性も高まる。
4.3.2 退化問題への対応
退化問題では、制約が重複したり、情報が十分でなかったりして計算が難しくなる。実装では、正則化や修正行列を導入して安定化を図る。
5 変種と拡張
逐次二次計画法には、基本形を補うさまざまな変種がある。問題の規模や構造に応じて、関連手法と組み合わせながら使われる。
5.1 活性制約法との関係
活性制約法は、現在境界にある制約を重点的に扱う考え方である。逐次二次計画法でも、どの制約が有効かを判定する過程でこの発想が現れる。
5.2 準ニュートン法との併用
準ニュートン法は、ヘッセ行列を効率よく近似する方法である。これを取り入れると、二次情報の計算を軽くしつつ、改善方向の質を保ちやすい。
5.3 大規模問題向け手法
大規模問題では、部分問題をそのまま解くのが難しい。そこで、疎行列計算、反復解法、近似更新などを組み合わせ、計算量を抑える工夫が行われる。
6 応用
逐次二次計画法は、制約付きで性能最適化が必要な場面に向く。現実のモデルに複数の条件が絡むほど、その利点が目立つ。
6.1 工学設計
工学設計では、重量、強度、材料費、形状条件などを同時に考える。逐次二次計画法は、こうした複数制約の下で性能を調整する際に有用である。
6.2 制御最適化
制御最適化では、システムの安定性や操作量の制限を考慮しながら制御入力を決める。逐次二次計画法は、モデル予測制御などで使われることが多い。
6.3 機械学習
機械学習では、学習の制約付き最適化や正則化付き問題に応用される。特に、学習パラメータに明確な制限がある場合に、整った解を得やすい。
6.4 経済モデル
経済モデルでは、資源配分、生産計画、効用最大化などの問題に適用される。制約条件が複雑でも、局所的な近似を通じて解を探索できる。
7 長所と短所
この手法は、制約を明示的に扱える点で強い一方、計算負荷や実装難度にも注意が必要である。適用範囲を理解して使うことが重要になる。
7.1 長所
目的関数と制約を同時に扱えるため、現実的な問題設定に適合しやすい。適切な近似が得られれば、少ない反復で高精度の解に到達できることがある。
7.2 短所
各反復で二次計画問題を解く必要があり、計算資源を要する。初期点や近似の質に結果が左右されやすく、非凸問題では局所解にとどまる場合がある。
8 歴史
逐次二次計画法は、非線形計画法の発展とともに整備されてきた。理論研究と計算技術の進歩が、実用化を後押しした。
8.1 研究の発展
初期には、制約付き最適化の理論整理の中で基礎が築かれた。のちに、コンピュータの性能向上とともに、大規模問題に対応する改良が進んだ。
8.2 代表的な文献
代表的文献には、非線形計画法の教科書や数値最適化の専門書が含まれる。これらは、理論、収束解析、実装技法を体系的にまとめている。
9 関連項目
9.1 非線形計画法
非線形計画法は、目的関数または制約が非線形である最適化分野全体を指す。逐次二次計画法は、その中の重要な解法の一つである。
9.2 数値最適化
数値最適化は、解析的に解けない問題を計算機で解く方法の総称である。逐次二次計画法は、反復計算を用いる代表例に含まれる。
9.3 逐次線形計画法
逐次線形計画法は、各反復で線形近似問題を解く手法である。逐次二次計画法と比べると簡潔だが、曲率情報を直接は利用しない。