モローの分解と凸集合への射影

モローの分解。 $x={\mathrm{prox}}_f(v)$ とし、$u=v-x$ とおきます。最適性条件から $u\in \partial f(x)$、つまりすべての $z$ で $f(z)\ge f(x)+⟨u,z-x⟩$ です。これは $⟨z,u⟩-f(z)\le ⟨x,u⟩-f(x)$ と同じなので、$f^{\ast }(u)=⟨x,u⟩-f(x)$（上限が $z=x$ で達成される）です。すると任意の $y$ について、共役の定義で $z=x$ とおいて $$f^{\ast }(y)\ge ⟨x,y⟩-f(x)=f^{\ast }(u)+⟨x,y-u⟩$$ が成り立ちます。また 2 次関数の凸性から $\frac{1}{2}\Vert y-v{\Vert }_2^2\ge \frac{1}{2}\Vert u-v{\Vert }_2^2+⟨u-v,y-u⟩$ です。2 式を足すと、$x+(u-v)=0$ より $$f^{\ast }(y)+\frac{1}{2}\Vert y-v{\Vert }_2^2\ge f^{\ast }(u)+\frac{1}{2}\Vert u-v{\Vert }_2^2$$ となり、$u$ は $f^{\ast }(y)+\frac{1}{2}\Vert y-v{\Vert }_2^2$ の最小点、すなわち $u={\mathrm{prox}}_{f^{\ast }}(v)$ です（この関数は強凸なので最小点はただ 1 つ）。よって $v=x+u={\mathrm{prox}}_f(v)+{\mathrm{prox}}_{f^{\ast }}(v)$ です。特に $f^{\ast }={\iota }_C$ なら、${\mathrm{prox}}_{{\iota }_C}(v)=\arg {\min }_{y\in C}\frac{1}{2}\Vert y-v{\Vert }_2^2$ は $v$ に最も近い $C$ の点、つまり射影 $P_C(v)$ です。

共役が指示関数になる例（$\lambda >0$）。 ノルムの共役は双対ノルムの球の指示関数なので、$(\lambda \Vert \cdot {\Vert }_{\infty }{)}^{\ast }={\iota }_C$, $C=\{y:\Vert y{\Vert }_1\le \lambda \}$ です。$f(x)=\lambda {\max }_i{x}_i$ では $f^{\ast }(y)={\sup }_x(⟨x,y⟩-\lambda {\max }_i{x}_i)$ を 3 つの場合に分けます。(a) ある $y_i<0$ なら、$x=-t{e}_i$（$e_i$ は第 $i$ 単位ベクトル, $t>0$）で値は $-t{y}_i-\lambda \max (0,-t)=-t{y}_i\to +\infty$。(b) ${\sum }_i{y}_i\ne \lambda$ なら、$x=t(1,\dots ,1)$ で値は $t({\sum }_i{y}_i-\lambda )$ となり、$t\to \pm \infty$ の一方で $+\infty$。(c) $y\ge 0$ かつ ${\sum }_i{y}_i=\lambda$ なら、$⟨x,y⟩={\sum }_i{y}_i{x}_i\le ({\sum }_i{y}_i){\max }_i{x}_i=\lambda {\max }_i{x}_i$ なので値は $0$ 以下で、$x=0$ で $0$ が達成されます。よって $f^{\ast }={\iota }_C$, $C=\{y\ge 0,{\sum }_i{y}_i=\lambda \}$（半径 $\lambda$ の単体）です。$\lambda \le 0$ では共役の形が変わる（例えば $\lambda <0$ の $\lambda \Vert x{\Vert }_{\infty }$ は凸でない）ので、この方法は $\lambda >0$ のときに使います。

射影の公式。 ${\ell }^1$ 球で $\Vert v{\Vert }_1>\lambda$ のとき、$g(\tau )={\sum }_i(|v_i|-\tau {)}_{+}$ は連続で、$0\le \tau \le {\max }_i|v_i|$ で狭義減少、$g(0)=\Vert v{\Vert }_1>\lambda$, $g({\max }_i|v_i|)=0$ なので、$g(\tau )=\lambda$ となる $\tau >0$ がただ 1 つあります。$\hat{y}={\mathrm{prox}}_{\tau \Vert \cdot {\Vert }_1}(v)$（ソフトしきい値 ${\hat{y}}_i=\mathrm{sign}(v_i)(|v_i|-\tau {)}_{+}$）とすると $\Vert \hat{y}{\Vert }_1=\lambda$ で、任意の $y\in C$ に対し $\frac{1}{2}\Vert y-v{\Vert }_2^2+\tau \lambda \ge \frac{1}{2}\Vert y-v{\Vert }_2^2+\tau \Vert y{\Vert }_1\ge \frac{1}{2}\Vert \hat{y}-v{\Vert }_2^2+\tau \Vert \hat{y}{\Vert }_1=\frac{1}{2}\Vert \hat{y}-v{\Vert }_2^2+\tau \lambda$ なので、$\hat{y}=P_C(v)$ です。単体でも同様で、$h(\tau )={\sum }_i(v_i-\tau {)}_{+}$ は連続・非増加で、正の値をとる範囲では狭義減少、$\tau \to -\infty$ で $+\infty$、$\tau \ge {\max }_i{v}_i$ で $0$ なので、$h(\tau )=\lambda$ となる $\tau$ がただ 1 つあります（負のこともあります）。$y\ge 0$ の範囲で $\frac{1}{2}(y_i-v_i{)}^2+\tau y_i$ を成分ごとに最小化すると、頂点 $v_i-\tau$ を $0$ で切った ${\hat{y}}_i=(v_i-\tau {)}_{+}$ になり、${\sum }_i{\hat{y}}_i=\lambda$ です。任意の $y\in C$ では $\tau {\sum }_i{y}_i=\tau \lambda$ が共通なので、$\frac{1}{2}\Vert y-v{\Vert }_2^2\ge \frac{1}{2}\Vert \hat{y}-v{\Vert }_2^2$、すなわち $\hat{y}=P_C(v)$ です。