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

騙された気になるが


2次計画法のエレガントな解法「
有効制約法」を紹介します。先のニュートン法ベースの手法に比べてエレガントすぎて不安になるのですが、実に素晴らしい方法です。ニュートン法ベースの方法と異なり「対象が凸2次関数かつ制約が線形関数」という縛りはあるのですが、今回の問題はもともとその範疇だし、対象関数が凸2次関数でなくても「遂次 2 次近似」などの近似法によって割と容易にその状況に持っていけるので、実は汎用性の高い手法です。
 
何が素晴らしいって、
有限回の演算で解が得られます。 これってとんでもない話です。普通こういう非線形方程式を解く手法って「解に漸近する収束計算」をするのが普通です。理論上「無限回」の計算が必要なところを、解が変化しなくなるところで打ち切る、という(実用上問題ない)「妥協」で済ませるわけです。

というわけでこの「有効制約法」では、通常非線形方程式を解く際に必ず設定する「収束の基準」(たとえば 10の-10 乗、とか)が存在しません
 
この方法を詳しく見ていきましょう。「有効制約法」の名前の通り
「有効な制約」をうまく使いながら解を求める手法です。「有効な制約」とは不等式制約(今回の ARXPS のケースだと「非負」縛り)のことです。基本的な発想としては、非負縛りのもとで最適なパラメータを求めたら、そのいくらかはゼロだろう、というものです。能書きだけ言っててもイメージ沸かないので、具体的に進めてみます。
 
まずは不等式を無視

まずは不等式制約を無視し、等式制約だけを考慮します。
 
2次計画法の対象関数

等式制約


こういう問題を考えます。すると問題は一気に簡単になり「解析的に」解けちゃいます(なおこのときの行列 A を、実はあとで更新して同じ計算をするので「A0」としておきます)。「解析的な解」は

等式制約のみの2次計画問題の解析解

こう表現できます。(不等式制約を無視しているので、不等式制約のラグランジュ乗数「z」は登場しません)。なお式中の行列は

行列AINVとH

こういうものです。A_INV は行列 A の「一般化逆行列」と呼ばれたりします。これで決まる。このベクトル x, y を初期値として計算を進めます。

ここで注目すべきは、この「初期値」は問題が定まれば一意に定まる、ということです。通常の非線形方程式を解く手法では初期値を何らかの方法で定めるのですが、一意ではなくこちらの主観が大いに入ります。そして初期値の選び方によって最終的な解がガラっと変わってしまうこともしばしばです。そういう意味でいうとこの手法は(恣意的に決める)「初期値フリー」な手法と言えます。
 
不等式制約はどうなった?

さて、この解は等式制約だけを考慮して決めたもので、当然ながら不等式制約を満たしている保証はありません。後で例をお見せしますが、今回の ARXPS のデータ解析においても、この初期値ではいくつかの濃度がマイナスになります(深さごとにトータル 1、の等式縛りは満たしている)。
 
この状態からスタートし、負になってしまったパラメータのグループについて
不等式制約(今回の場合は非負縛り)をひとつずつ満たしていくことを考えます。「非負を満たす」といっても「正」にするつもりはサラサラ無く、それらを「ゼロ」に持っていくことを考えます。これは自然といえば自然な話で、非負縛り無しで解いたときに負になってしまうパラメータのほとんどは、非負縛り有りで解いたらゼロでしょう、ということです。
 
先ほど決めた初期パラメータベクトル x のなかで、
不等式制約を満たしていない(つまり負の)変数をひとつ選び、そいつを xs とします。その xs をゼロにします。といってもそいつだけを勝手にゼロにするわけにはいかず、ベクトル x のその他の成分は、すでに満たしている KKT条件(等式制約など)をキープしたままにするというのがミソです。具体的には

xsをゼロ化するための問題

こういう問題を解きます。ベクトル x の成分を全部変化させるんだけども、すでに満たした等式制約などはちゃんと満たしながら変化させ、うまいこと xs がゼロになるように持っていく、ということです。この新たな問題の KKT 条件より、「探索方向」は

xsをゼロ化するための問題の探索方向
こうなります。ベクトル
es は s 成分だけが 1 で他がゼロ、つまり単位行列「E」の第 s 列だけを抜き出したもの、と考えればよいです。

「方向」が決まったらあとは「ステップ幅」を決めるのですが、これは 3 つ目の条件(xs をゼロにする)から決めます。これは s に対応するラグランジュ乗数 zs に対応し
xsをゼロ化するための問題のステップ幅

となります。ここでは割愛しますが、これは必ず正になることが示されています。この結果として

ベクトルxyの更新

とすれば
非負縛り以外の KKT 条件をキープしたまま xs=0 とすることができます。 このノリで進めていきます。続く!



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

【文責 べじぱみゅ