凸最適化・組合せ最適化の問題

目的関数 $F(x)=f(x)+\frac{1}{2}\Vert x-v{\Vert }_2^2$ は強凸なので最小点はただ 1 つ存在し、${\mathrm{prox}}_f(v)$ は well-defined である。

変数変換. $u_1=\frac{x_1+x_2}{\sqrt{2}},u_2=\frac{x_1-x_2}{\sqrt{2}}$ は直交変換なので $\Vert x-v{\Vert }_2^2=(u_1-w_1{)}^2+(u_2-w_2{)}^2$（$w$ は $v$ を同じく変換したもの）が成り立つ。$v=(7,-3)$ なら
$$w_1=\frac{7+(-3)}{\sqrt{2}}=\frac{4}{\sqrt{2}}=2\sqrt{2},w_2=\frac{7-(-3)}{\sqrt{2}}=\frac{10}{\sqrt{2}}=5\sqrt{2}.$$
また $f(x)=3\sqrt{2}|u_2|+\sqrt{2}|u_1|$ である。よって問題は $u_1,u_2$ について分離し、
$$\underset{u_1}{\min }\left(\sqrt{2}|u_1|+\frac{1}{2}(u_1-w_1{)}^2\right),\underset{u_2}{\min }\left(3\sqrt{2}|u_2|+\frac{1}{2}(u_2-w_2{)}^2\right)$$
をそれぞれ解けばよい。1 変数関数 $\lambda |t|$（$\lambda >0$）の近接写像はソフトしきい値関数
$$S_{\lambda }(w)=\mathrm{sign}(w)\max \{|w|-\lambda ,0\}$$
である（$t\ne 0$ で最適性条件 $w-t=\lambda \mathrm{sign}(t)$、$t=0$ で $w\in [-\lambda ,\lambda ]$ から得られる）。したがって
$$u_1=S_{\sqrt{2}}(2\sqrt{2})=\sqrt{2},u_2=S_{3\sqrt{2}}(5\sqrt{2})=2\sqrt{2}.$$
元に戻すと $x_1+x_2=\sqrt{2}{u}_1=2$、$x_1-x_2=\sqrt{2}{u}_2=4$ より
$$x_1=3,x_2=-1.$$

劣勾配による確認. $p=(3,-1)$ が最小点であるための必要十分条件は $v-p\in \partial f(p)$ である。$p_1-p_2=4>0$、$p_1+p_2=2>0$ なので $f$ は $p$ の近くで $3(x_1-x_2)+(x_1+x_2)=4x_1-2x_2$ と一致し微分可能で、$\partial f(p)=\{(4,-2)\}$。一方 $v-p=(7-3,-3-(-1))=(4,-2)$ なので条件を満たす。

よって $(p_1,p_2)=(3,-1)$。

直交座標変換 $u=\frac{x_1-x_2}{\sqrt{2}},w=\frac{x_1+x_2}{\sqrt{2}}$ を行うと（直交変換なのでユークリッドノルムは保たれる）、$f=3\sqrt{2}|u|+\sqrt{2}|w|$ となり、近接問題は $u,w$ について分離する。各成分は絶対値の近接写像（ソフト閾値）${\mathrm{prox}}_{\lambda |\cdot |}(s)=\mathrm{sign}(s)\max (|s|-\lambda ,0)$ で解ける。
$v=(7,-3)$ について $u_v=\frac{7-(-3)}{\sqrt{2}}=5\sqrt{2}$、$w_v=\frac{7+(-3)}{\sqrt{2}}=2\sqrt{2}$。
- $u$: 閾値 $3\sqrt{2}$ より $u^{\ast }=5\sqrt{2}-3\sqrt{2}=2\sqrt{2}$。
- $w$: 閾値 $\sqrt{2}$ より $w^{\ast }=2\sqrt{2}-\sqrt{2}=\sqrt{2}$。
元の座標に戻すと $p_1=\frac{u^{\ast }+w^{\ast }}{\sqrt{2}}=\frac{3\sqrt{2}}{\sqrt{2}}=3$、$p_2=\frac{w^{\ast }-u^{\ast }}{\sqrt{2}}=\frac{-\sqrt{2}}{\sqrt{2}}=-1$。
検算（最適性条件 $v-p\in \partial f(p)$）: $v-p=(4,-2)$。$p_1-p_2=4>0$、$p_1+p_2=2>0$ なので $f$ は $p$ で微分可能で $\nabla f(p)=3(1,-1)+(1,1)=(4,-2)$。一致するので $p=(3,-1)$。