NP完全な問題を行列で表現する
$ A\bm v=\bm 1
$ A_{i,j}には$ i番目の節に$ j番目の変数が含まれる場合$ 1が入る
そうでない場合は$ 0が入る
1行に入る$ 1は丁度$ 3つ
右辺の$ \bm 1は要素が全部$ 1のベクトル
全ての節が$ {\rm True}であることを表す
十分に条件を縛ると変数に対して式が少なくなるのでこれは劣決定問題 解全体を$ \bm v=A^-\bm 1+{\rm Ker}(A)\bm tのように書ける
$ \bm y = \bm b+W\bm xと書き直す
この $ \bm yが 0-1 ベクトルになって欲しい
ならないこともある (unsatisfied)
この線形方程式、図的にはどういう感じなんだろう
解$ \bm vはスパースなのか？
$ \min_\bm x \{-y_i\log y_i-(1-y_i)\log(1-y_i)\}を求めたい
ただし$ \bm y=\bm b+W\bm x
最小値は定義域の端 $ \{0,1\}で、傾きが 0 ではない
勾配法を使う場合定義域外にはみ出した値を域内に戻す処理が必要
逆にそれさえできれば最小値にすぐに落ちていきそうな気はしている
最小値に向けて勾配がどんどん急になるから
初期値が最大値だった場合は勾配が 0 なので動き出さない問題がある
この要件を満たしてほしいだけなら$ \min\{-(y_i-\frac{1}{2})^2\}\qquad y_i\in[0,1] でいいじゃん
局所解が有りそうだけど、どんな形をしているのだろうか
$ \min_\bm x (y_i)^2(1-y_i)^2でもいい
もっと別の関数でも良い
$ y_i=0\ {\rm or}\ 1で最小値を取る関数の$ y_iに線形関数を入れたときの挙動を知りたい
ベクトル微分を詳しく勉強する必要があるな
$ y_i\in\{0,1\}がよくわからなかったtakker.icon
離散函数？
連続関数なんだけど最小を取ると$ \ y_i\in\{0,1\}になるようにしたい
とりあえず$ \frac{\partial}{\partial x_i}(y_i)^2(1-y_i)^2=0を探すしか無いかなあtakker.icon
当たり前だけど
非凸関数でも「極小値が全て最小値かつその時のパラメータはどれを選んでも良い」条件だったらうまく最適化できないもんかなぁ
$ y_i=\{0,1\}になればOKなので、0 でも 1 でもいい
上に凸の部分が最小化に悪影響を及ぼす可能性？
ある関数$ fの最小値が存在するなら必ずその最小値に収束することを示す論法について調べる必要があるな