B.3.2 信頼領域法を用いる方法
本手法では,二つの二次計画問題を解くことで点列を生成していきます.まず,一つ目の二次計画問題は次の通りです.
ここでとは,要素が正の値であるような対角行列とします.この問題の解
は,本手法に大域的収束性を与える上で大きな役割を果たします.
この問題の解を求めたとき,効いている制約の集合をとします.すなわち
となります.このとき,もう一つの二次計画問題は次のように定められます.
ここでは元の問題のラグランジュ関数のヘッセ行列です.この問題の解
は,反復点が元の問題の解に近づいたときに速い収束をするための方向になっています.また,この問題のKKT条件は,次のように線形方程式系として表すことができます.
ここで,はこの問題の制約条件に対するラグランジュ乗数とします.一般に,問題規模が同程度であれば,線形方程式系は二次計画問題に比べ速く解くことができるので,この問題に対する計算コストは,先程の
を求める問題と比べて小さいものと考えることができます.
本手法では,と
の凸結合
を探索方向とし,定められた信頼領域の中を探索し,次の反復点を生成します.
上に戻る