高次オーダー法

高次オーダー法#

  • 読み: こうじおーだーほう

  • 英名: Higher Order Method

数理計画法を解く内点法の文脈では,KKT 条件に現れる相補性条件の非線形性(これは線形/凸な二次計画問題においては唯一の非線形制約となる)を活かした形に式を変形,相補性条件に二次の情報を入れて,Newton 法の収束を加速する手法のことを言う.

二次の情報の取得と反映には,行列の分解をし直す必要はなく,オーダーの低い演算である前進消去・後退代入が一回余計に必要になるのみであるので,この手法の導入によって計算コストが過大に増大することはない.

Merohtra が最初に提案し,現在,線形/凸な二次計画問題を解く手法としては標準的な地位を確立した.Nuorium Optimizer においても線形計画問題を解く場合のデフォルトである.一部非線形計画問題に適用する試みがあるが,明確な効果は観測されていない.

同様な手法で内点法の収束を早める方法はもう一つ Gonzio が提唱した,Multiple Centrality Corrections と呼ばれる方法があり,こちらも標準的な手法として知られている.こちらはバリアパラメータの値の調整をコンポーネント毎に動的に行って,ステップサイズを増大させる方法である.これもバリアパラメータが Newton 方向の右辺にしか現れないことを利用している.前進消去・後退代入の負荷の増大のみで実装可能なので,計算負荷が少ない.