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

$y=y^{\circ }$ とおき、$g(x)=⟨y,x⟩-f(x)$ とする。$f$ は凸関数（$\log (e^{x_1}+e^{x_2})$ は log-sum-exp 関数で凸、$\frac{1}{2}(x_1-x_2{)}^2$ も凸）の和で凸かつ微分可能だから、$g$ は微分可能な凹関数である。したがって $\nabla g(x)=0$ となる点 $x$ があれば、そこで $g$ は最大値をとり、$f^{\ast }(y)=g(x)$ となる。

勾配の計算. $d=x_1-x_2$ とし、$\sigma (t)=\frac{1}{1+e^{-t}}$ とおくと、
$$\frac{e^{x_1}}{e^{x_1}+e^{x_2}}=\sigma (d),\frac{e^{x_2}}{e^{x_1}+e^{x_2}}=1-\sigma (d)$$
なので
$$\nabla f(x)=(\sigma (d)+d,1-\sigma (d)-d).$$

停留点. $\nabla f(x)=y$ を解く。第 2 成分の方程式は第 1 成分の方程式と $y_1+y_2=1$ から従うので、第 1 成分
$$\sigma (d)+d=\frac{3}{4}+\log 3$$
だけを考えればよい。$\phi (d)=\sigma (d)+d$ は狭義単調増加（${\phi }^{\prime }(d)=\sigma (d)(1-\sigma (d))+1>0$）であり、$\sigma (\log 3)=\frac{1}{1+\frac{1}{3}}=\frac{3}{4}$ だから、解はただ一つ $d=\log 3$ である。

よって $x_1-x_2=\log 3$ を満たす点はすべて $g$ の最大点である。実際、$f(x+c(1,1))=f(x)+c$ かつ $⟨y,(1,1)⟩=y_1+y_2=1$ なので、$g$ は $(1,1)$ 方向に不変である。そこで $x=(\log 3,0)$ をとる。

値の計算.
$$⟨y,x⟩=\left(\frac{3}{4}+\log 3\right)\log 3=\frac{3}{4}\log 3+(\log 3{)}^2,$$
$$f(x)=\log (3+1)+\frac{1}{2}(\log 3{)}^2=2\log 2+\frac{1}{2}(\log 3{)}^2.$$
したがって
$$f^{\ast }(y^{\circ })=\frac{3}{4}\log 3+(\log 3{)}^2-2\log 2-\frac{1}{2}(\log 3{)}^2=\frac{3}{4}\log 3+\frac{1}{2}(\log 3{)}^2-2\log 2.$$

（別解：$(f_1+f_2{)}^{\ast }=f_1^{\ast }\square f_2^{\ast }$（下限たたみこみ）を用いる。$f_1^{\ast }$ は単体上の負のエントロピー $\sum u_i\log u_i$、$f_2^{\ast }(t(1,-1))=\frac{t^2}{2}$（それ以外の点では $+\infty$）である。${\min }_t\{f_1^{\ast }(y-t(1,-1))+\frac{t^2}{2}\}$ は $t=\log 3$ で達成され、$y-t(1,-1)=(\frac{3}{4},\frac{1}{4})$ となる。値は $\frac{3}{4}\log \frac{3}{4}+\frac{1}{4}\log \frac{1}{4}+\frac{1}{2}(\log 3{)}^2$ で、上と一致する。）

答え：$\frac{3}{4}\log 3+\frac{1}{2}(\log 3{)}^2-2\log 2$

$f$ は微分可能な凸関数なので、$\nabla f(x)=y^{\circ }$ を満たす $x$ で上限がとれる。

$d=x_1-x_2$、$p=\frac{e^{x_1}}{e^{x_1}+e^{x_2}}=\frac{e^d}{1+e^d}$ とおくと、
$\nabla f(x)=(p+d,1-p-d)$。

$y_1^{\circ }=\frac{3}{4}+\log 3$ より $p+d=\frac{3}{4}+\log 3$。$d=\log 3$ のとき $p=\frac{3}{4}$ となり、これを満たす。また $p+d$ は $d$ について狭義単調増加なので、この解は一意に定まる。
$y_2^{\circ }=1-y_1^{\circ }$ も成り立つ。

$f$ の値は $x$ に $(1,1)$ を足すと $f$ は 1 増え、$⟨y^{\circ },x⟩$ も $y_1^{\circ }+y_2^{\circ }=1$ だけ増える。よって $x_2$ は任意でよく、$x=(\log 3,0)$ をとる。

$⟨y^{\circ },x⟩=\left(\frac{3}{4}+\log 3\right)\log 3$。
$f(x)=\log 4+\frac{1}{2}(\log 3{)}^2$。

したがって
$f^{\ast }(y^{\circ })=\frac{3}{4}\log 3+(\log 3{)}^2-2\log 2-\frac{1}{2}(\log 3{)}^2=\frac{3}{4}\log 3+\frac{1}{2}(\log 3{)}^2-2\log 2$。