最適化・線形計画法の問題

1. 凸計画問題であることの確認

目的関数 $f(x,y)=x^2+2y^2$ のヘッセ行列は
$${\nabla }^{2}f=\left(\begin{array}{cc}2& 0\\ 0& 4\end{array}\right)$$
です。主小行列式は $2>0$、$2\cdot 4-0=8>0$ なので、ヘッセ行列はすべての点で正定値です。よって $f$ は凸関数（狭義凸関数）です。

制約関数 $g(x,y)=3-x-y$ は 1 次式なので凸関数です。したがって実行可能領域 $\{(x,y)\mid x+y\ge 3\}$ は半平面であり、凸集合です。

以上から、この問題は凸計画問題です。凸計画問題では KKT 条件を満たす点は大域的な最小解 になります。そこで、KKT 点を 1 つ求めれば十分です。

2. KKT 条件を立てる

$\nabla f=(2x,4y)$、$\nabla g=(-1,-1)$ なので、KKT 条件は
$$2x-\mu =0,4y-\mu =0,\mu \ge 0,\mu (3-x-y)=0,3-x-y\le 0$$
です。

3. KKT 条件を解く

- $\mu =0$ の場合：$2x=0$、$4y=0$ より $(x,y)=(0,0)$ です。しかし $3-0-0=3>0$ となり制約を満たしません。よって不適です。
- $\mu >0$ の場合：$\mu (3-x-y)=0$ より $x+y=3$ です。$x=\frac{\mu }{2}$、$y=\frac{\mu }{4}$ を代入すると
$$\frac{\mu }{2}+\frac{\mu }{4}=\frac{3\mu }{4}=3$$
となるので、$\mu =4$ です。このとき $x=2$、$y=1$ です。$\mu =4\ge 0$ なので、すべての条件を満たします。

したがって KKT 点は $(x,y)=(2,1)$、乗数は $\mu =4$ です。

4. 結論

凸計画問題なので、KKT 点 $(2,1)$ は大域的な最小解です。最小値は
$$f(2,1)=2^2+2\cdot 1^2=6$$
です。

$f$ のヘッセ行列は $\mathrm{diag}(2,4)$ で正定値なので $f$ は凸関数である。$g$ は 1 次関数なので凸であり、実行可能領域 $x+y\ge 3$ は凸集合である。よって凸計画問題であり、KKT 条件を満たす点が大域的最小点になる。

ラグランジュ関数を $L=x^2+2y^2+\lambda (3-x-y)$ とする。KKT 条件は次の通り。
- $2x-\lambda =0$
- $4y-\lambda =0$
- $\lambda \ge 0$
- $3-x-y\le 0$
- $\lambda (3-x-y)=0$

場合 1: $\lambda =0$ のとき、$x=y=0$ となる。しかし $g(0,0)=3>0$ で実行可能でないため不適。

場合 2: $\lambda >0$ のとき、$x+y=3$ である。$x=\lambda /2$、$y=\lambda /4$ なので $3\lambda /4=3$ より $\lambda =4$。したがって $x=2$、$y=1$ で、$\lambda =4\ge 0$ を満たす。

最小値は $f(2,1)=4+2=6$。

検算: $y=3-x$ を代入すると $x^2+2(3-x{)}^2=3x^2-12x+18=3(x-2{)}^2+6$ となり、$x=2$ で最小値 $6$ をとる。これは上の結果と一致する。

KKT 点は $(x,y)=(2,1)$（$\lambda =4$）で、最小値は $6$ である。