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

$g(x)=\frac{1}{3}\Vert x{\Vert }_2^3$, $h(x)=2\Vert x{\Vert }_1$ とおくと $f=g+h$ である。

$g^{\ast }$ の計算. $⟨x,y⟩\le \Vert x{\Vert }_2\Vert y{\Vert }_2$ で、等号は $x$ が $y$ と同じ向きのとき成り立つので、$r=\Vert x{\Vert }_2\ge 0$, $s=\Vert y{\Vert }_2$ として
$$g^{\ast }(y)=\underset{r\ge 0}{\sup }(rs-\frac{r^3}{3}).$$
$r\mapsto rs-r^3/3$ は $r=\sqrt{s}$ で最大となり、値は $s^{3/2}-\frac{1}{3}{s}^{3/2}=\frac{2}{3}{s}^{3/2}$。よって $g^{\ast }(y)=\frac{2}{3}\Vert y{\Vert }_2^{3/2}$。

$h^{\ast }$ の計算. $\Vert \cdot {\Vert }_1$ の双対ノルムは $\Vert \cdot {\Vert }_{\infty }$ なので、$h^{\ast }$ は $C=\{z:\Vert z{\Vert }_{\infty }\le 2\}=[-2,2{]}^2$ の指示関数 ${\delta }_C$ である。

和の共役. $g,h$ はともに ${\mathbb{R}}^2$ 全体で有限な凸関数（したがって連続）なので、和の共役は共役の下限たたみ込みに等しく、下限は達成される:
$$f^{\ast }(y)=\underset{z}{\min }(g^{\ast }(y-z)+h^{\ast }(z))=\underset{z\in C}{\min }\frac{2}{3}\Vert y-z{\Vert }_2^{3/2}=\frac{2}{3}\mathrm{dist}(y,C{)}^{3/2}.$$

$y=(5,6)$ の $C=[-2,2{]}^2$ への射影は $(2,2)$ なので
$$\mathrm{dist}(y,C)=\sqrt{(5-2{)}^2+(6-2{)}^2}=\sqrt{9+16}=5.$$
したがって
$$f^{\ast }(5,6)=\frac{2}{3}\cdot 5^{3/2}=\frac{10\sqrt{5}}{3}.$$

検算（直接計算）. $y$ の成分は正なので $x\ge 0$ で考えれば十分で、そのとき $⟨x,y⟩-2\Vert x{\Vert }_1=3x_1+4x_2$。よって $f^{\ast }(5,6)={\sup }_x(⟨x,(3,4)⟩-\frac{1}{3}\Vert x{\Vert }_2^3)=g^{\ast }(3,4)=\frac{2}{3}\cdot 5^{3/2}$（最大点 $x=\frac{\sqrt{5}}{5}(3,4)$ は成分が正）で一致する。

$g(x)=\frac{1}{3}\Vert x{\Vert }_2^3$、$h(x)=2\Vert x{\Vert }_1$ とおくと $f=g+h$、ともに有限値の凸関数なので $f^{\ast }=g^{\ast }\square h^{\ast }$（下限畳み込み）が成り立つ（和の共役は共役の下限畳み込み、$g$ が全域で連続なので等号と下限の達成も保証される）。

$g^{\ast }(w)={\sup }_x(⟨x,w⟩-\frac{1}{3}\Vert x{\Vert }^3)$。$\Vert x\Vert =r$ として $x$ を $w$ と同じ向きにとると ${\sup }_r(r\Vert w\Vert -\frac{1}{3}{r}^3)$。$r=\Vert w{\Vert }^{1/2}$ で最大となり $g^{\ast }(w)=\frac{2}{3}\Vert w{\Vert }_2^{3/2}$。

$h^{\ast }(z)={\sup }_x(⟨x,z⟩-2\Vert x{\Vert }_1)$ は $\Vert z{\Vert }_{\infty }\le 2$ のとき $0$、それ以外は $+\infty$。

よって $f^{\ast }(y)={\min }_{z\in [-2,2{]}^2}\frac{2}{3}\Vert y-z{\Vert }_2^{3/2}$。これは $\Vert y-z{\Vert }_2$ について単調増加なので、$y=(5,6)$ から正方形 $[-2,2{]}^2$ への最短距離を求める。最近点は $z=(2,2)$ で $y-z=(3,4)$、距離 $5$。

$f^{\ast }(5,6)=\frac{2}{3}\cdot 5^{3/2}=\frac{10\sqrt{5}}{3}$。

検算: 最適な $x$ は劣勾配条件 $y\in \partial f(x)$ から、$x=(x_1,x_2)$（$x_i>0$）で $\Vert x\Vert x_1+2=5$, $\Vert x\Vert x_2+2=6$ より $\Vert x\Vert x=(3,4)$、$\Vert x{\Vert }^2\cdot \Vert x\Vert =5$ なので $\Vert x{\Vert }^2=5$、$\Vert x\Vert =\sqrt{5}$。$⟨x,y⟩-f(x)$ は $x=(3,4)/\sqrt{5}$ で $\frac{15+24}{\sqrt{5}}-\frac{1}{3}5\sqrt{5}-2\cdot \frac{7}{\sqrt{5}}=\frac{25}{\sqrt{5}}-\frac{5\sqrt{5}}{3}=5\sqrt{5}-\frac{5\sqrt{5}}{3}=\frac{10\sqrt{5}}{3}$。一致。