B.2.2 QP 単体法
単体法は，線形計画問題（Linear Programming，LP）の解法として確立された手法ですが，その後，二次計画問題（Quadratic Programming，QP）にも適用できるように拡張されました．このような QP に対する単体法は QP 単体法と呼ばれます．
QP 単体法では，基底解の概念を拡張し，凸多面体の頂点だけでなく，多面体内部の点も表現可能な基底を扱います．これに伴い，解が頂点からどの程度「内部に入り込んでいるか」を表す指標が定義され，これを freedom (自由度) と呼びます．この拡張された基底を用いながら，LP 単体法と同様に，基底間の遷移を通じて最適解を探索します．
QP 単体法の歴史も古く，1950～1960 年代にはすでに複数の手法が提案されています [22][23][24][25][26]．特に Dantzig [23]，および van de Panne と Whinston [24][25] の手法では，二次項がゼロの場合，通常の LP 単体法と同一の解軌跡を辿ることが示されており，LP 単体法の自然な拡張と見なすことができます．日本語による解説としては，竹内・真鍋による文献 [27] が詳しいです．
QP 単体法の概要
QP 単体法は，制約行列に対してピボット操作を行う通常の LP 単体法とは異なり，KKT 条件を行列として捉え，その KKT 行列に対してピボット操作を行うアルゴリズムです．ただし，主要操作の概念自体は LP 単体法と非常によく似ています．たとえば LP 単体法で行われるプライシング（pricing），比率判定（ratio test），ピボット操作（pivot）といった処理は，QP 単体法においても基本的に同じ意味で用いられます．
操作の対象となる行列が LP では制約行列，QP では KKT 行列と異なるため，主要操作の内容自体は LP と QP で異なりますが，QP 単体法の各操作が果たす役割や直感的な意味は LP 単体法のそれを自然に一般化したものとして理解できます．
QP 単体法の具体的な手続きについては文献 [23][24][25] などをご参照ください．
上に戻る