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

方針（モローの分解） 閉真凸関数 $f$ について
$$v={\mathrm{prox}}_f(v)+{\mathrm{prox}}_{f^{\ast }}(v)$$
が成り立つ。$f^{\ast }$ が凸集合の指示関数なら ${\mathrm{prox}}_{f^{\ast }}$ はその集合への射影なので、${\mathrm{prox}}_f(v)=v-(\text{射影})$ として求められる。

手順 1：$f^{\ast }$ を求める $\Vert \cdot {\Vert }_{\infty }$ の双対ノルムは $\Vert \cdot {\Vert }_1$ なので、$\Vert \cdot {\Vert }_{\infty }$ の共役は ${\ell }^1$ 単位球 $\{y\mid \Vert y{\Vert }_1\le 1\}$ の指示関数である。$5$ 倍すると
$$f^{\ast }(y)=\underset{x}{\sup }(⟨x,y⟩-5\Vert x{\Vert }_{\infty })=\{\begin{array}{ll}0& (\Vert y{\Vert }_1\le 5)\\ +\infty & (\Vert y{\Vert }_1>5)\end{array}$$
となる。つまり $f^{\ast }={\iota }_C$，$C=\{y\in {\mathbb{R}}^2\mid |y_1|+|y_2|\le 5\}$ である。

手順 2：${\mathrm{prox}}_{f^{\ast }}(v)$ は $C$ への射影 指示関数の近接写像は
$${\mathrm{prox}}_{{\iota }_C}(v)=\underset{y\in C}{\mathrm{argmin}}\frac{1}{2}\Vert y-v{\Vert }_2^2=P_C(v)$$
である。$v=(6,3)$ は $|6|+|3|=9>5$ なので $C$ の外にある。${\ell }^1$ 球への射影は、ある $\tau >0$ によるソフトしきい値
$$P_C(v{)}_i=\mathrm{sign}(v_i)\max \{|v_i|-\tau ,0\}$$
で、$\tau$ は ${\sum }_i\max \{|v_i|-\tau ,0\}=5$ で決まる。両成分が正のまま残ると仮定すると
$$(6-\tau )+(3-\tau )=5⟹\tau =2$$
で、$6-2=4>0$，$3-2=1>0$ なので仮定に合う。よって
$$P_C(v)=(4,1)$$
である。

手順 3：モローの分解で引き算する
$${\mathrm{prox}}_f(v)=v-P_C(v)=(6,3)-(4,1)=(2,2).$$

確認 $x=(2,2)$ では $|x_1|=|x_2|=2$ がともに最大なので、$\partial f(x)=5\cdot \mathrm{conv}\{(1,0),(0,1)\}=\{(5t,5(1-t))\mid 0\le t\le 1\}$ である。$v-x=(4,1)$ は $t=\frac{4}{5}$ のときこの集合に入るので、最適性条件 $v-x\in \partial f(x)$ を満たす。

よって ${\mathrm{prox}}_f(v)=(2,2)$ である。

モロー分解より、${\mathrm{prox}}_{\lambda \Vert \cdot {\Vert }_{\infty }}(v)=v-{\mathrm{proj}}_{\{\Vert u{\Vert }_1\le \lambda \}}(v)$（$\Vert \cdot {\Vert }_{\infty }$ の双対ノルムは $\Vert \cdot {\Vert }_1$）。ここで $\lambda =5$、$v=(6,3)$。

$v$ の ${\ell }_1$ ノルムは $9>5$ なので、${\ell }_1$ 球 $\{\Vert u{\Vert }_1\le 5\}$ への射影は軟しきい値処理 $u_i=\mathrm{sign}(v_i)\max (|v_i|-\theta ,0)$ で、$\theta \ge 0$ は $\Vert u{\Vert }_1=5$ から決まる。$\theta \le 3$ のとき $(6-\theta )+(3-\theta )=5$ より $\theta =2$（$\theta \le 3$ をみたす）。したがって射影は $u=(4,1)$。

よって ${\mathrm{prox}}_f(v)=(6,3)-(4,1)=(2,2)$。

検算（最適性条件）：$x=(2,2)$ では $\Vert x{\Vert }_{\infty }$ の劣微分は $\mathrm{conv}\{e_1,e_2\}$（両成分が最大）。$v-x=(4,1)$ が $5\partial \Vert x{\Vert }_{\infty }=\{5(a,1-a):0\le a\le 1\}$ に入るか確かめると、$a=0.8$ で $5(0.8,0.2)=(4,1)$ となり成立。凸問題なので $x=(2,2)$ が最小点（一意）。