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

手順 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 点）は大域的な最小解になります。そこで 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 条件を解く。

(i) $\mu =0$ のとき

$x=0$, $y=0$ となります。このとき $g(0,0)=3>0$ となり、制約を満たしません。

(ii) $\mu >0$ のとき

相補性条件 $\mu (3-x-y)=0$ から $x+y=3$ です。停留条件から $x=\frac{\mu }{2}$, $y=\frac{\mu }{4}$ なので、
$$\frac{\mu }{2}+\frac{\mu }{4}=3⟹\frac{3\mu }{4}=3⟹\mu =4$$
となります。よって $x=2$, $y=1$ です。$\mu =4\ge 0$ であり、$g(2,1)=0\le 0$ も満たすので、$(x,y)=(2,1)$ は KKT 点です。

手順 4: 十分性を使って結論する。

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

答え: $6$

$f$ のヘッセ行列は $\mathrm{diag}(2,4)$ で正定値なので $f$ は凸関数である。$g=3-x-y$ は一次式（アフィン）なので凸関数であり、制約 $g\le 0$ は凸集合を定める。よって凸計画問題である。また $x=y=3$ で $g=-3<0$ となるので Slater の条件が成り立ち、KKT 条件は最適性の必要十分条件になる。

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

$\lambda =0$ とすると $x=y=0$ となるが、このとき $g=3>0$ で実行不可能である。したがって $\lambda >0$ であり、$x+y=3$ が成り立つ。

$x=\lambda /2$, $y=\lambda /4$ を $x+y=3$ に代入すると $3\lambda /4=3$ より $\lambda =4$ である。よって $x=2$, $y=1$ となる。

最小値は $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$ で一致する。