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

手順 1：凸計画であることを確かめる。

定義域 $D=\{(x,y)\mid x>0,y>0\}$ は凸集合である。$f$ の偏導関数は
$$f_x=-\frac{1}{x^2},f_y=-\frac{4}{y^2},f_{xx}=\frac{2}{x^3},f_{yy}=\frac{8}{y^3},f_{xy}=0$$
なので、ヘッセ行列は
$${\nabla }^{2}f=\left(\begin{array}{cc}\frac{2}{x^3}& 0\\ 0& \frac{8}{y^3}\end{array}\right)$$
である。$D$ 上では対角成分がともに正なので正定値であり、$f$ は $D$ 上で凸関数である。制約関数 $g(x,y)=x+y-3$ は 1 次式なので凸関数であり、$g\le 0$ が表す集合と $D$ の共通部分は凸集合である。

よってこの問題は凸計画問題であり、KKT 条件を満たす点が見つかれば、それが大域的な最小解になる（KKT 条件の十分性）。

手順 2：KKT 条件を立てる。

乗数を $\mu$ とすると、KKT 条件は
$$-\frac{1}{x^2}+\mu =0,-\frac{4}{y^2}+\mu =0,\mu \ge 0,\mu (x+y-3)=0,x+y\le 3$$
である。

手順 3：KKT 条件を解く。

第 1 式より $\mu =\frac{1}{x^2}>0$ なので $\mu =0$ にはならない。したがって相補性条件 $\mu (x+y-3)=0$ から $x+y=3$ である。

また、第 1 式と第 2 式から
$$\frac{1}{x^2}=\frac{4}{y^2}⟹y^2=4x^2$$
で、$x>0,y>0$ より $y=2x$。これを $x+y=3$ に代入すると $3x=3$、すなわち $x=1,y=2$。このとき $\mu =\frac{1}{1^2}=1\ge 0$ で、すべての KKT 条件を満たす。

手順 4：最小値を求める。

手順 1 より、KKT 点 $(x,y)=(1,2)$ は大域的な最小解である。最小値は
$$f(1,2)=\frac{1}{1}+\frac{4}{2}=1+2=3$$
である。

目的関数 $f(x,y)=1/x+4/y$ は $x>0,y>0$ で、$f_{xx}=2/x^3>0$、$f_{yy}=8/y^3>0$、$f_{xy}=0$ なのでヘッセ行列は正定値であり、$f$ は凸である。制約関数 $g=x+y-3$ は線形なので凸であり、定義域 $x>0,y>0$ は凸集合である。したがって凸計画問題である。

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

$x,y>0$ より $\lambda =1/x^2>0$ となる。よって相補性から $x+y=3$ である。また $1/x^2=4/y^2$ より $y=2x$（$x,y>0$）となる。これを $x+y=3$ に代入すると $3x=3$ なので $x=1$、$y=2$、$\lambda =1$ を得る。

この問題は凸計画問題であり、KKT 条件は最適性の十分条件なので、$(1,2)$ は大域的最小点である。最小値は $f(1,2)=1+4/2=3$ である。

検算として、コーシー・シュワルツの不等式より $(1/x+4/y)(x+y)\ge (1+2{)}^2=9$ である。$x+y\le 3$ なので $f\ge 9/(x+y)\ge 3$ となり、等号は $x=1,y=2$ で成り立つ。これは上の結果と一致する。

なお、$x+y<3$ の内部には停留点がない（$f$ は $x,y$ について単調減少）ので、最小値は境界上でとられる。