*注意)この「べじぱみゅの学習メモ」のカテゴリー記事は、ワタクシ自身がこれまでに勉強したいろいろな項目について、テキストにあんまり書いてない内容などを勝手に妄想したメモです。
ワタクシ自身の備忘録のために書いており「初学者にわかりやすく説明する」というものではございません。
導入なしに唐突に話が始まり、おそらく意味不明な文章かもしれません。
しかし、せっかく考えたことなので、記事の内容がもし誰か1人でもお役に立てれば幸いです。

ひたすらゼロ化!


前回、1つのx成分をゼロ化しましたが、あとは基本的には同じノリです。この調子でいくつかの x をゼロにし続けて
k 回目に達したとします。このとき、等式縛りの行列「A」を

等式制約行列Ak

こうします。この*の部分は「ゼロにした x に対応する「-E」の列となります。例えば n 個の変数のうち 105 番、128 番、224 番目の x をゼロ化した後なら 

Akの具体例

という、n 行 m+3 列の行列になります。各
ei は n 行ベクトルで、i 行目だけが 1 で(よってそのマイナスなので行列では-1)、他がすべてゼロです。つまり「すでにゼロ化した変数は、その後ずっとゼロに縛る」ということです。ちなみにこの後説明しますが「ゼロ化した成分が 3つなら k=3」というわけではありません。この k は純粋なループ回数なのですが、更新によってゼロ化 x が増えたり増えなかったりします。
 
この新しい Ak に対して前回の記事と同じ計算をして、また新たな xs をゼロにしに行くことを考えます。

k回目のループにおけるAINVとH

と同じ計算をして、「探索方向」は

xとλの探索方向
こうなります。もとの y がλに代わっています
が、λは m 行の y に、すでにゼロ化した x に対応するラグランジュ乗数を加えたものです。Akと同じくこのベクトルも増えていきます。さっきの例だと 

λkの例

という m+3 行ベクトルになります。しつこく言いますがk=3 とは限りません。そしてすべての成分は更新によって値が変わります。
 
あとはステップ幅です。前回の計算と同様に

k回目のステップ幅

(ターゲットの s 成分も、これまでの度重なる更新によって初期から値が変わっています)としたいところなのでづが、実はそうもいきません。

「zの非負縛り」が効く!

初回はこれでよかったのですが、2 回目以降は更新するラグランジュ乗数ベクトルに「z」の成分が入ってきます。zは非負縛りがあるので、ステップ幅 t で

λの更新
と更新したときにz部分が負にならない範囲に限定する必要があります。具体的には t をゼロから大きくしていったときに最初にゼロになる「z」の成分 z_l に対して 
zが非負であるための条件
を求めます。zの成分がもともと「ギリギリ正」か、更新ベクトル Δλが他の成分よりメチャクチャ大きくなった成分がこの対象になります。このt_MINとz_sの大小関係により2通りに分かれます。 

ハッピーなケース: zs<t_MIN
 
先ほどの zs がたまたまその範囲に入っていれば、新たな x は無事ゼロ化されます
。例えば今新たに 283 番目の x をゼロ化しようとしていると仮定すると、このときは 

xとλの更新

と、xおよびλをまず更新します。そしてλに、新しくゼロ化した成分を足します。

λベクトルの成分を増やす


さらに行列 Ak にも対応する成分を足します。

Akの成分も増やす


このλおよびAを用いて、次のゼロ化ターゲットを探しにいきます。
 
不幸なケース: zs>t_MIN

そして、不幸にも zs が範囲をはみ出る(非負制約のほうが厳しい)場合があります。そのときはzsをゼロにはできません。そこでまず 

xとλの更新(非負縛りがきつい場合)

と、行ける所までλを更新します。そして、最も非負縛りのキツかった成分 l を「ゼロ化グループから排除」します。つまり

最も縛りのキツい xl のせいで新たな xs がゼログループに入れなかったんだから、xl はここから出ていけ!

ということです。例えばすでにゼロ化した中で 128 番の非負縛りが最もキツい場合、 


犯人を追い出す

と、もとの行列 Ak およびλから 128 番目のラグランジュ乗数を排除して新たなものを構成します。この、ちょっと減らしたλとAを用いてもう一度ループを回します。ただこのとき、追加する s は自由に選ぶのではなく、直前でゼロ化に失敗した s(この場合は 283番)にする必要があります。 

この「犯人排除」は理論的には z の数がゼロになるまで続く可能性はありますが、実際には多くても数回程度続いて終わることが多いです。非負縛りのキツいものから順に排除しているので、それなりの回数「仲間外し」を繰り返せば、縛りが zs より緩くなる時が来るわけです。
 
なんともジャイアン的な解法ですが、このアルゴリズムによりいつの日か(
有限回!)すべての不等式制約を満たす最適解が得られる、ということが証明されています。証明の詳細は割愛しますが、

不等式制約以外のKKT条件をキープしながら負成分のゼロ化を進めていくので、負成分が無くなったときには全てのKKT条件が満たされている

と理解すればいいでしょう。なんかスマートすぎて騙されている感が抜けないのですが、実際にうまく行きます。

次回、今回の題材であるARXPSデータ解析に対して実際に適用し、挙動を見てみましょう! 


はっぴぃ理系らいふ、いぇい
ヽ(・ε・)人(・ε・)ノ キミモナカマニナロウゼ
   

【文責 べじぱみゅ