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

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

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

実数 $x, y$ についての次の最適化問題を考える。
$minimize subject to f (x, y) = x^{2} + x y + y^{2} - 6 x g_{1} (x, y) = x + y - 1 \leq 0, g_{2} (x, y) = x - y - 3 \leq 0.$
ラグランジュ関数を
$L (x, y, μ_{1}, μ_{2}) = f (x, y) + μ_{1} g_{1} (x, y) + μ_{2} g_{2} (x, y)$
とし、 $μ_{1}, μ_{2} \geq 0$ を KKT 乗数とする。この問題の最適解 $(x^{*}, y^{*})$ と、それに対応する KKT 乗数 $μ_{1}^{*}, μ_{2}^{*}$ を求め、 $(x^{*}, y^{*}, μ_{1}^{*}, μ_{2}^{*})$ の順に答えよ。

この問題で使うもの

KKT 条件（説明と入口の問題）
凸計画と KKT 条件の十分性（説明と入口の問題）
ヘッセ行列による凸性の判定（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

目的関数が凸で制約が一次式なので、KKT 条件を満たす点が最適解になる。どの制約が等号で成り立つ（能動的）かで場合分けしよう。

ヒント 2

停留条件は $2 x + y - 6 + μ_{1} + μ_{2} = 0, x + 2 y + μ_{1} - μ_{2} = 0$ 。相補性 $μ_{1} g_{1} = 0, μ_{2} g_{2} = 0$ と合わせて考える。

ヒント 3

制約なしの最小点 $(4, - 2)$ も、制約を 1 つだけ能動にした候補 $(\frac{7}{2}, - \frac{5}{2})$ , $(\frac{5}{2}, - \frac{1}{2})$ も実行不可能になる。残るのは両方の制約が等号で成り立つ場合である。

答えと解説

答えを見る

(2, - 1, \frac{3}{2}, \frac{3}{2})

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

解説を読む

凸性の確認. $f$ のヘッセ行列は $(2112)$ で、首座小行列式が $2 > 0$ , $4 - 1 = 3 > 0$ なので正定値である。よって $f$ は狭義凸関数であり、制約はすべて一次式なので、KKT 条件は最適性の必要十分条件であり、最適解はただ 1 つである。

KKT 条件. $\nabla f = (2 x + y - 6, x + 2 y)$ , $\nabla g_{1} = (1, 1)$ , $\nabla g_{2} = (1, - 1)$ より
$2 x + y - 6 + μ_{1} + μ_{2} = 0, x + 2 y + μ_{1} - μ_{2} = 0, μ_{1} \geq 0, μ_{2} \geq 0, g_{1} \leq 0, g_{2} \leq 0, μ_{1} g_{1} = 0, μ_{2} g_{2} = 0.$

場合分け.

(i) $μ_{1} = μ_{2} = 0$ : $2 x + y = 6, x + 2 y = 0$ より $(x, y) = (4, - 2)$ 。 $g_{1} = 4 - 2 - 1 = 1 > 0$ で実行不可能。

(ii) $μ_{2} = 0$ , $g_{1} = 0$ : $y = 1 - x$ を代入すると $f = x^{2} + x (1 - x) + (1 - x)^{2} - 6 x = x^{2} - 7 x + 1$ 。停留条件から $x = \frac{7}{2}, y = - \frac{5}{2}$ （このとき第 1 式から $μ_{1} = 6 - 2 x - y = \frac{3}{2}$ ）。しかし $g_{2} = \frac{7}{2} + \frac{5}{2} - 3 = 3 > 0$ で実行不可能。

(iii) $μ_{1} = 0$ , $g_{2} = 0$ : $y = x - 3$ を代入すると $f = 3 x^{2} - 15 x + 9$ 。 $x = \frac{5}{2}, y = - \frac{1}{2}$ だが $g_{1} = \frac{5}{2} - \frac{1}{2} - 1 = 1 > 0$ で実行不可能。

(iv) $g_{1} = g_{2} = 0$ : $x + y = 1, x - y = 3$ より $(x, y) = (2, - 1)$ 。このとき $\nabla f = (4 - 1 - 6, 2 - 2) = (- 3, 0)$ なので
$- 3 + μ_{1} + μ_{2} = 0, μ_{1} - μ_{2} = 0$
より $μ_{1} = μ_{2} = \frac{3}{2} \geq 0$ 。KKT 条件をすべて満たす。

能動制約の勾配 $(1, 1), (1, - 1)$ は一次独立なので乗数は一意に定まる。以上より
$(x^{*}, y^{*}, μ_{1}^{*}, μ_{2}^{*}) = (2, - 1, \frac{3}{2}, \frac{3}{2})$
（最適値は $f (2, - 1) = 4 - 2 + 1 - 12 = - 9$ ）。

別解

$f$ のヘッシアンは $(2112)$ で正定値なので $f$ は凸、制約は線形なので、KKT 条件を満たす点が最適解になる。

場合分けで調べる。
- 制約なし: $\nabla f = (2 x + y - 6, x + 2 y) = 0$ より $(4, - 2)$ 。このとき $g_{1} = 1 > 0$ となり実行可能でない。
- $g_{1}$ のみ有効: $y = 1 - x$ を代入すると $f = x^{2} - 7 x + 1$ となり、 $x = 7/2, y = - 5/2$ 。このとき $g_{2} = 3 > 0$ となり実行可能でない。
- $g_{2}$ のみ有効: $y = x - 3$ を代入すると $f = 3 x^{2} - 15 x + 9$ となり、 $x = 5/2, y = - 1/2$ 。このとき $g_{1} = 1 > 0$ となり実行可能でない。
- 両方有効: $x + y = 1, x - y = 3$ より $(x, y) = (2, - 1)$ 。

$(2, - 1)$ で $\nabla f = (4 - 1 - 6, 2 - 2) = (- 3, 0)$ 。定常性の条件 $\nabla f + μ_{1} (1, 1) + μ_{2} (1, - 1) = 0$ より
$- 3 + μ_{1} + μ_{2} = 0, μ_{1} - μ_{2} = 0$ 。
これを解くと $μ_{1} = μ_{2} = 3/2 \geq 0$ 。

検算: 両制約は等号で成り立ち、相補性 $μ_{i} g_{i} = 0$ も満たす。したがって KKT 条件をすべて満たす。
$f (2, - 1) = 4 - 2 + 1 - 12 = - 9$ 。

答え: $(x^{*}, y^{*}, μ_{1}^{*}, μ_{2}^{*}) = (2, - 1, 3/2, 3/2)$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題