半正定値緩和法

Author: Shun Suzuki

Date: 2024-08-13

NOTE: この手法は現在SDKでは実装されていない.

ここでは, 件の行列方程式を解く方法を述べる. ただし, 行列方程式を解くにはまず焦点の位相を決定する必要がある.

行列方程式を解いて得られた解が振動子出力の制約を満たさないのなら, 出力を一律に抑える必要がある. そのため, 一部の振動子が突出して強いパワーで駆動するような解が得られたとしたら, 上限に合わせて全体をスケールしなければならず, 弱い場が生成されてしまう. このような制約の下で, “良い“解を見つけるために, 焦点における位相を最適化する手法がこれまでにいくつか提案されている.

以下に, 井上らによる半正定値緩和法によるを紹介する^{1 2 3}.

まず, $P=\mathrm{diag}(|p_0|,\dots ,|p_{M-1}|),\mathbf{u}=[{\mathrm{e}}^{-\mathrm{i}{\psi }_0},\dots ,{\mathrm{e}}^{-\mathrm{i}{\psi }_{M-1}}]{}^{\mathsf{T}}$として, この問題を次のような最適化問題に書き換える. $$\begin{array}{r}\underset{|u_i|=1}{\min }\Vert G\mathbf{q}-P\mathbf{u}{\Vert }^2.\end{array}$$ ここで$\mathbf{u}$は位相成分を表すため$|u_i|=1$なる制約が付く.

ここで, $$\begin{array}{rl}\mathbf{q}& =G^{-1}P\mathbf{u},\\ G^{-1}G{G}^{-1}& =G^{-1},\\ (G{G}^{-1}){}^{†}& =G{G}^{-1},\end{array}$$ を満たすような$G^{-1}$が存在するとすると $$\begin{array}{rl}\underset{|u_i|=1}{\min }\Vert G\mathbf{q}-P\mathbf{u}{\Vert }^2& =\Vert (G{G}^{-1}-I)P\mathbf{u}{\Vert }^2\\ & =\mathbf{u}{}^{†}P{}^{†}(G{G}^{-1}-I){}^{†}(G{G}^{-1}-I)P\mathbf{u}\\ & =\mathbf{u}{}^{†}P(G{G}^{-1}-I)(G{G}^{-1}-I)P\mathbf{u}\\ & =\mathbf{u}{}^{†}P(G{G}^{-1}G{G}^{-1}-2G{G}^{-1}+I)P\mathbf{u}\\ & =\mathbf{u}{}^{†}P(I-G{G}^{-1})P\mathbf{u},\end{array}$$ となる. ここで, $\cdot {}^{†}$はエルミート転置をあらわす.

$M=P(I-G{G}^{-1})P$と置くと, 最適化問題は以下のように書き下せる. $$\begin{array}{r}\underset{|u_i|=1}{\min }\mathbf{u}{}^{†}M\mathbf{u}.\end{array}$$

(以下の議論は文献⁴の2.4. Complex MaxCut.による.) 上記最適化は制約条件により凸問題ではない. そこで, $U=uu{}^{†}$と置くと, $$\begin{array}{rl}\min & \mathrm{Tr}(UM),\\ \mathrm{subject}\mathrm{to}& \mathrm{diag}(U)=I,\\ & U⪰0,\mathrm{Rank}(U)=1,\end{array}$$ となる. ここで, ランク制限を落とすと半正定値問題となり, 効率的に解くことができる. $\mathrm{Rank}(U)=1$ではない場合は$U$の最大固有値に対応する固有ベクトルが$\mathbf{u}$の近似解となる.

ブロック座標降下法を用いて$U$を求めるアルゴリズムは文献⁴ Algorithm 3を参照⁵.

あとは, $$\begin{array}{rl}\mathbf{q}& =G^{-1}P\mathbf{u},\\ G^{-1}G{G}^{-1}& =G^{-1},\\ (G{G}^{-1}){}^{†}& =G{G}^{-1},\end{array}$$ を満たす$G^{-1}$を求めればいい. この$G^{-1}$はMoore-Penroseの擬似逆行列と呼ばれていて, $G$の特異値分解$G=U\Sigma V{}^{†}$から $$\begin{array}{r}{G}^{-1}=V{\Sigma }^{-1}U{}^{†},\end{array}$$ として計算できる. ただし, ${\Sigma }^{-1}$は$\Sigma =\mathrm{diag}({\sigma }_1,\dots )$に対して $$\begin{array}{r}{\Sigma }^{-1}=\mathrm{diag}\left(\frac{1}{{\sigma }_1},\dots \right),\end{array}$$ である.

井上らの方法では, ここにさらにTikhonov正則化が入る⁶. すなわち, 最小化問題に以下の正則化項を加える. $$\begin{array}{r}\underset{|{\mathbf{u}}_i|=1}{\min }\Vert G\mathbf{q}-P\mathbf{u}{\Vert }^2+\alpha \Vert \mathbf{q}{\Vert }^2.\end{array}$$ これは, 機械学習の文脈ではリッジ回帰などと呼ばれる, L2正則化である. この正則化には, 解の大きさを抑えるような効果がある. この場合の解は, 以下で与えられる $$\begin{array}{rl}\mathbf{q}& =(G{}^{†}G+\alpha I{)}^{-1}G{}^{†}P\mathbf{u}\\ & =(V\Sigma {}^{†}U{}^{†}U\Sigma V{}^{†}+\alpha VIV{}^{†}{)}^{-1}V\Sigma {}^{†}U{}^{†}P\mathbf{u}\\ & =V(\Sigma {}^{†}\Sigma +\alpha I{)}^{-1}\Sigma {}^{†}U{}^{†}P\mathbf{u}\\ & =V\mathrm{diag}\left(\frac{{\sigma }_1}{{\sigma }_1^2+\alpha },\dots \right)U{}^{†}P\mathbf{u}.\end{array}$$