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

$f^{\ast }(y)={\sup }_{x\in C}\phi (x)$、$\phi (x)=⟨x,y⟩-{\sum }_i{x}_i\log x_i$ である。$\phi$ は $C$ 上で連続かつ（$t\log t$ が狭義凸なので）狭義凹で、$C$ はコンパクト凸集合だから最大点がただ 1 つ存在し、KKT 条件を満たす点が最大点である。

制約を無視した場合. $x_i\le \frac{1}{2}$ を外すと、最大点はソフトマックス $x_i=e^{y_i}/{\sum }_j{e}^{y_j}$ で、$e^y=(9,3,1)$ より $x=(\frac{9}{13},\frac{3}{13},\frac{1}{13})$。$x_1=\frac{9}{13}>\frac{1}{2}$ なので上限制約が効く。

$x_1=\frac{1}{2}$ と推測して KKT 条件を確かめる. ラグランジュ関数
$$L=⟨x,y⟩-\sum _i{x}_i\log x_i-\nu (\sum _i{x}_i-1)-\sum _i{\mu }_i(x_i-\frac{1}{2})({\mu }_i\ge 0)$$
の停留条件は $y_i-\log x_i-1-\nu -{\mu }_i=0$、すなわち $x_i=e^{y_i}{e}^{-1-\nu }{e}^{-{\mu }_i}$。${\mu }_2={\mu }_3=0$ とすると $x_2:x_3=e^{y_2}:e^{y_3}=3:1$、$x_2+x_3=1-\frac{1}{2}=\frac{1}{2}$ より
$$x_2=\frac{3}{8},x_3=\frac{1}{8}.$$
このとき $e^{-1-\nu }=x_3=\frac{1}{8}$、$x_1=9\cdot \frac{1}{8}\cdot e^{-{\mu }_1}=\frac{1}{2}$ より $e^{-{\mu }_1}=\frac{4}{9}$、${\mu }_1=\log \frac{9}{4}>0$。$x_2,x_3<\frac{1}{2}$ で相補性もみたし、すべての $x_i>0$ なので KKT 条件が成り立つ。よって最大点は $x^{\ast }=(\frac{1}{2},\frac{3}{8},\frac{1}{8})$。

値の計算.
$$⟨x^{\ast },y⟩=\frac{1}{2}\cdot 2\log 3+\frac{3}{8}\log 3=\frac{11}{8}\log 3,$$
$$\sum _i{x}_i^{\ast }\log x_i^{\ast }=\frac{1}{2}\log \frac{1}{2}+\frac{3}{8}\log \frac{3}{8}+\frac{1}{8}\log \frac{1}{8}=-\frac{1}{2}\log 2+\frac{3}{8}\log 3-\frac{9}{8}\log 2-\frac{3}{8}\log 2=\frac{3}{8}\log 3-2\log 2.$$
したがって
$$f^{\ast }(y)=\frac{11}{8}\log 3-(\frac{3}{8}\log 3-2\log 2)=\log 3+2\log 2=\log 12.$$

$f^{\ast }(y)={\max }_{x\in C}({\sum }_i{x}_i{y}_i-{\sum }_i{x}_i\log x_i)$。目的関数は $C$ 上で狭義凹（$-x\log x$ が凹）なので最大点は一意で、KKT 条件で求まる。ラグランジュ乗数を使うと、最適点は $x_i=\min (\frac{1}{2},c{e}^{y_i})$ の形（$c>0$ は $\sum x_i=1$ から決まる）になる。ここで $e^y=(9,3,1)$。
- 上限を無視した解 $x\propto (9,3,1)$ は $x_1=9/13>1/2$ で実行不可能なので、$x_1=\frac{1}{2}$ に固定する。
- 残り $\frac{1}{2}$ を $x_2,x_3$ に $3:1$ で分けて $x_2=\frac{3}{8},x_3=\frac{1}{8}$（$c=\frac{1}{8}$）。$x_2,x_3\in (0,\frac{1}{2}]$ を満たし、$x_1$ について $c{e}^{y_1}=\frac{9}{8}>\frac{1}{2}$ で上限が有効。KKT 条件を満たす。
最適点 $x^{\ast }=(\frac{1}{2},\frac{3}{8},\frac{1}{8})$ での値を計算する。
$⟨x^{\ast },y⟩=\frac{1}{2}\cdot 2\log 3+\frac{3}{8}\log 3+0=\frac{11}{8}\log 3$。
$\sum x_i\log x_i=\frac{1}{2}(-\log 2)+\frac{3}{8}(\log 3-3\log 2)+\frac{1}{8}(-3\log 2)=\frac{3}{8}\log 3-(\frac{1}{2}+\frac{9}{8}+\frac{3}{8})\log 2=\frac{3}{8}\log 3-2\log 2$。
よって $f^{\ast }(y)=\frac{11}{8}\log 3-\frac{3}{8}\log 3+2\log 2=\log 3+2\log 2=\log 12$。
検算: 上限なしの単体上の最大値は $\log (9+3+1)=\log 13\approx 2.565$ で、制約付きの $\log 12\approx 2.485$ はそれ以下で整合。別の実行可能点 $(\frac{1}{2},\frac{1}{2},0)$ では $\log 3+\log 3\cdot \frac{1}{2}\cdot ...$ すなわち $\frac{1}{2}\cdot 2\log 3+\frac{1}{2}\log 3-(\log \frac{1}{2})=\frac{3}{2}\log 3+\log 2\approx 2.341<2.485$ で、確かに $x^{\ast }$ の方が大きい。