この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

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

難易度 2教科書の演習問題レベル大学数学最適化・線形計画法

実数 $x, y$ についての次の最適化問題を考える。
$minimize subject to f (x, y) = (x - 4)^{2} + (y - 1)^{2} g_{1} (x, y) = x + 2 y - 4 \leq 0, g_{2} (x, y) = - x \leq 0, g_{3} (x, y) = - y \leq 0.$
KKT 条件を
$\nabla f (x, y) + μ_{1} \nabla g_{1} (x, y) + μ_{2} \nabla g_{2} (x, y) + μ_{3} \nabla g_{3} (x, y) = 0, μ_{i} \geq 0, μ_{i} g_{i} (x, y) = 0 (i = 1, 2, 3)$
と、制約 $g_{i} (x, y) \leq 0 (i = 1, 2, 3)$ の組とする。この問題の最適解 $(x^{*}, y^{*})$ と、そこでの KKT 乗数 $μ_{1}^{*}$ を、組 $(x^{*}, y^{*}, μ_{1}^{*})$ の形で求めよ。

この問題で使うもの

KKT 条件（説明と入口の問題）
凸計画と KKT 条件の十分性（説明と入口の問題）

この問題を解けるようになるまで（79 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

まず制約がないときの最小点 $(4, 1)$ が制約を満たすかを調べ、どの制約が最適解で有効（等号成立）になりそうか考えよう。

ヒント 2

$g_{1}$ だけが有効で $μ_{2} = μ_{3} = 0$ と仮定すると、停留条件は $2 (x - 4) + μ_{1} = 0, 2 (y - 1) + 2 μ_{1} = 0$ となる。これと $x + 2 y = 4$ を連立する。

ヒント 3

停留条件から $x = 4 - \frac{μ _{1}}{2}, y = 1 - μ_{1}$ 。これを $x + 2 y = 4$ に代入して $μ_{1}$ を求め、最後に $μ_{1} \geq 0$ と $x > 0, y > 0$ を確認する。

答えと解説

答えを見る

(\frac{18}{5}, \frac{1}{5}, \frac{4}{5})

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

目的関数 $f$ は狭義凸関数で、制約はすべて一次式なので、この問題は凸計画問題である。制約はすべて一次式なので制約想定（制約条件の正則性）が成り立ち、KKT 条件を満たす点が最適解であり、その点は $f$ の狭義凸性からただ 1 つに決まる。

制約なしの最小点を調べる. 制約がなければ最小点は $(4, 1)$ だが、 $g_{1} (4, 1) = 4 + 2 - 4 = 2 > 0$ なので実行可能でない。したがって最適解では $g_{1}$ が有効（ $x + 2 y = 4$ ）であると予想できる。

$g_{1}$ のみ有効、 $μ_{2} = μ_{3} = 0$ と仮定する. $\nabla f = (2 (x - 4), 2 (y - 1))$ 、 $\nabla g_{1} = (1, 2)$ より、停留条件は
$2 (x - 4) + μ_{1} = 0, 2 (y - 1) + 2 μ_{1} = 0.$
よって $x = 4 - \frac{μ _{1}}{2}$ 、 $y = 1 - μ_{1}$ 。これを $x + 2 y = 4$ に代入すると
$4 - \frac{μ _{1}}{2} + 2 - 2 μ_{1} = 4 ⟹ \frac{5}{2} μ_{1} = 2 ⟹ μ_{1} = \frac{4}{5} .$
したがって
$x = 4 - \frac{2}{5} = \frac{18}{5}, y = 1 - \frac{4}{5} = \frac{1}{5} .$

KKT 条件の確認.
- $μ_{1} = \frac{4}{5} \geq 0$ 、 $g_{1} = \frac{18}{5} + \frac{2}{5} - 4 = 0$ なので相補性も成り立つ。
- $x = \frac{18}{5} > 0$ 、 $y = \frac{1}{5} > 0$ なので $g_{2} < 0$ 、 $g_{3} < 0$ で、 $μ_{2} = μ_{3} = 0$ と相補性が成り立つ。

よって $(x, y) = (\frac{18}{5}, \frac{1}{5})$ は KKT 条件を満たし、凸計画問題なので最適解である。また有効な制約は $g_{1}$ だけで $\nabla g_{1} \neq = 0$ なので、乗数 $μ_{1}$ は一意に $\frac{4}{5}$ と決まる。

（参考: 最小値は $f = (- \frac{2}{5})^{2} + (- \frac{4}{5})^{2} = \frac{4}{5}$ 。これは点 $(4, 1)$ から直線 $x + 2 y = 4$ までの距離 $\frac{2}{5}$ の 2 乗に一致する。）

答えは $(\frac{18}{5}, \frac{1}{5}, \frac{4}{5})$ 。

別解

目的関数 $f$ は凸、制約はすべて線形なので、KKT 条件を満たす点が最適解である。

$\nabla f = (2 (x - 4), 2 (y - 1))$ , $\nabla g_{1} = (1, 2)$ , $\nabla g_{2} = (- 1, 0)$ , $\nabla g_{3} = (0, - 1)$ 。

点 $(4, 1)$ は $g_{1} = 4 + 2 - 4 = 2 > 0$ で実行可能でないので、 $g_{1}$ が有効 ( $μ_{1} > 0$ , $x + 2 y = 4$ ) と予想する。 $x, y > 0$ と仮定して $μ_{2} = μ_{3} = 0$ とすると、
$2 (x - 4) + μ_{1} = 0$ , $2 (y - 1) + 2 μ_{1} = 0$ , $x + 2 y = 4$ 。
$x = 4 - μ_{1} /2$ , $y = 1 - μ_{1}$ を $x + 2 y = 4$ に代入: $4 - \frac{μ _{1}}{2} + 2 - 2 μ_{1} = 4 \Rightarrow \frac{5}{2} μ_{1} = 2 \Rightarrow μ_{1} = \frac{4}{5}$ 。
よって $x = 4 - \frac{2}{5} = \frac{18}{5}$ , $y = 1 - \frac{4}{5} = \frac{1}{5}$ 。

確認: $x = \frac{18}{5} > 0$ , $y = \frac{1}{5} > 0$ で $g_{2} < 0, g_{3} < 0$ なので $μ_{2} = μ_{3} = 0$ と矛盾しない。 $μ_{1} = \frac{4}{5} \geq 0$ 。 $g_{1} = \frac{18}{5} + \frac{2}{5} - 4 = 0$ 。
勾配の式: $2 (\frac{18}{5} - 4) + \frac{4}{5} = - \frac{4}{5} + \frac{4}{5} = 0$ , $2 (\frac{1}{5} - 1) + 2 \cdot \frac{4}{5} = - \frac{8}{5} + \frac{8}{5} = 0$ 。

幾何的な検算: $(4, 1)$ を直線 $x + 2 y = 4$ へ射影した点は $(4, 1) - \frac{4 + 2 - 4}{5} (1, 2) = (\frac{18}{5}, \frac{1}{5})$ で一致し、これは $x, y \geq 0$ を満たす。

答え: $(x^{*}, y^{*}, μ_{1}^{*}) = (\frac{18}{5}, \frac{1}{5}, \frac{4}{5})$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題