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

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

難易度 3期末試験の応用レベル大学数学最適化・線形計画法

実数 $x, y$ についての次の最適化問題を考える。
$minimize subject to f (x, y) = (x - 3)^{2} + (y - 2)^{2} g_{1} (x, y) = x^{2} + y^{2} - 5 \leq 0, g_{2} (x, y) = x + 2 y - 4 \leq 0.$
ラグランジュ関数を $L (x, y, λ_{1}, λ_{2}) = f (x, y) + λ_{1} g_{1} (x, y) + λ_{2} g_{2} (x, y)$ とする。この問題の最適解 $(x^{*}, y^{*})$ において KKT 条件を満たすラグランジュ乗数 $λ_{1}, λ_{2} (\geq 0)$ は一意に定まる。その組 $(λ_{1}, λ_{2})$ をこの順に求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

問題は凸計画でスレーター条件も成り立つので、KKT 条件を満たす点が最適解です。どの制約が等号で成り立つかで場合分けしましょう。

ヒント 2

停留条件は $2 (x - 3) + 2 λ_{1} x + λ_{2} = 0$ 、 $2 (y - 2) + 2 λ_{1} y + 2 λ_{2} = 0$ です。制約なしの最小点 $(3, 2)$ や、片方の制約だけを等号にした場合の点が、もう一方の制約を満たすかを確かめましょう。

ヒント 3

片方だけが有効な場合はどちらも他方の制約に反するので、両方の制約が有効です。 $x^{2} + y^{2} = 5$ と $x + 2 y = 4$ の交点は $(2, 1)$ と $(- \frac{2}{5}, \frac{11}{5})$ です。それぞれで乗数を求め、非負かどうかを調べましょう。

答えと解説

答えを見る

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

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

解説を読む

凸性と KKT 条件の位置づけ

$f$ は狭義凸な 2 次関数、 $g_{1}$ は凸関数、 $g_{2}$ は 1 次関数なので、この問題は凸計画問題である。さらに $(0, 0)$ で $g_{1} = - 5 < 0, g_{2} = - 4 < 0$ だからスレーター条件が成り立つ。よって KKT 条件は最適性の必要十分条件であり、 $f$ が狭義凸なので最適解はただ 1 つである。

KKT 条件は次のとおりである。
$2 (x - 3) + 2 λ_{1} x + λ_{2} = 0, 2 (y - 2) + 2 λ_{1} y + 2 λ_{2} = 0, g_{1} \leq 0, g_{2} \leq 0, λ_{1}, λ_{2} \geq 0, λ_{1} g_{1} = 0, λ_{2} g_{2} = 0.$

どの制約が有効（等号）になるかで場合分けする。

(i) $λ_{1} = λ_{2} = 0$ のとき

停留条件から $(x, y) = (3, 2)$ となる。しかし $g_{1} = 13 - 5 > 0$ なので実行不可能である。

(ii) $λ_{2} = 0, g_{1} = 0$ のとき

停留条件から $x = \frac{3}{1 + λ _{1}}, y = \frac{2}{1 + λ _{1}}$ となる。これを $x^{2} + y^{2} = 5$ に代入すると $\frac{13}{( 1 + λ _{1} ) ^{2}} = 5$ より $1 + λ_{1} = 13/5$ である。このとき
$x + 2 y = \frac{7}{1 + λ _{1}} = 7 \frac{5}{13} = \frac{245}{13} > 16 = 4$
となり、 $g_{2} \leq 0$ に反する。

(iii) $λ_{1} = 0, g_{2} = 0$ のとき

停留条件から $x = 3 - \frac{λ _{2}}{2}, y = 2 - λ_{2}$ となる。 $x + 2 y = 7 - \frac{5}{2} λ_{2} = 4$ より $λ_{2} = \frac{6}{5}$ で、 $(x, y) = (\frac{12}{5}, \frac{4}{5})$ を得る。しかし $x^{2} + y^{2} = \frac{144 + 16}{25} = \frac{32}{5} > 5$ となり、 $g_{1} \leq 0$ に反する。

(iv) $g_{1} = g_{2} = 0$ のとき

$x = 4 - 2 y$ を $x^{2} + y^{2} = 5$ に代入すると
$(4 - 2 y)^{2} + y^{2} = 5 ⟺ 5 y^{2} - 16 y + 11 = 0 ⟺ (y - 1) (5 y - 11) = 0$
となり、候補は $(2, 1)$ と $(- \frac{2}{5}, \frac{11}{5})$ である。

点 $(2, 1)$ では、停留条件は $- 2 + 4 λ_{1} + λ_{2} = 0, - 2 + 2 λ_{1} + 2 λ_{2} = 0$ となる。2 式目から $λ_{1} + λ_{2} = 1$ で、1 式目との差をとると $3 λ_{1} = 1$ である。よって $λ_{1} = \frac{1}{3}, λ_{2} = \frac{2}{3}$ で、ともに非負なので KKT 条件をすべて満たす。
点 $(- \frac{2}{5}, \frac{11}{5})$ では、停留条件は $- \frac{34}{5} - \frac{4}{5} λ_{1} + λ_{2} = 0, \frac{2}{5} + \frac{22}{5} λ_{1} + 2 λ_{2} = 0$ となる。1 式目から $λ_{2} = \frac{34}{5} + \frac{4}{5} λ_{1}$ で、これを 2 式目に代入すると $14 + 6 λ_{1} = 0$ 、すなわち $λ_{1} = - \frac{7}{3} < 0$ となり不適である。

結論

最適解は $(x^{*}, y^{*}) = (2, 1)$ （最適値 $2$ ）である。この点で有効な制約の勾配 $\nabla g_{1} = (4, 2)$ と $\nabla g_{2} = (1, 2)$ は 1 次独立（LICQ が成立）なので、乗数は一意に定まる。

したがって、求める組は $(λ_{1}, λ_{2}) = (\frac{1}{3}, \frac{2}{3})$ である。

別解

点 $(3, 2)$ から実行可能領域（円板 $x^{2} + y^{2} \leq 5$ と半平面 $x + 2 y \leq 4$ の共通部分）への最短距離を求める問題である。

$(3, 2)$ では $g_{1} = 8 > 0$ , $g_{2} = 3 > 0$ で、どちらの制約も破れている。

(i) 直線 $x + 2 y = 4$ への射影は $(12/5, 4/5)$ 。このとき $g_{1} = 6.4 - 5 > 0$ なので実行不可能。
(ii) 円板への射影は $5/13 (3, 2)$ 。このとき $x + 2 y = 7 5/13 \approx 4.34 > 4$ なので実行不可能。

よって両方の制約が有効で、最適解は円と直線の交点のうち $(3, 2)$ に近い方である。 $x = 4 - 2 y$ を円の式に代入すると $5 y^{2} - 16 y + 11 = 0$ より $y = 1, 11/5$ 。交点は $(2, 1)$ と $(- 6/5, 11/5)$ 。 $(3, 2)$ との距離の2乗はそれぞれ $2$ と $(21/5)^{2} + (1/5)^{2} = 442/25$ なので、最適解は $(2, 1)$ 。

KKT 条件（停留条件）は $\nabla f + λ_{1} \nabla g_{1} + λ_{2} \nabla g_{2} = 0$ 。 $(2, 1)$ で $\nabla f = (- 2, - 2)$ , $\nabla g_{1} = (4, 2)$ , $\nabla g_{2} = (1, 2)$ なので
$- 2 + 4 λ_{1} + λ_{2} = 0$ , $- 2 + 2 λ_{1} + 2 λ_{2} = 0$ 。
第2式より $λ_{1} + λ_{2} = 1$ 。第1式との差から $3 λ_{1} = 1$ 、よって $λ_{1} = 1/3$ , $λ_{2} = 2/3$ 。ともに $0$ 以上である。

検算： $4/3 + 2/3 = 2$ ✓、 $2/3 + 4/3 = 2$ ✓。 $g_{1} = g_{2} = 0$ なので相補性条件も成り立つ。目的関数と制約はすべて凸なので、KKT 点は最適解である。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題