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

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

難易度 4大学院入試の標準レベル大学数学最適化・線形計画法

実数 $x_{1}, x_{2}, x_{3}$ についての次の最適化問題を考える。
$minimize subject to f (x_{1}, x_{2}, x_{3}) = (x_{1} - 1)^{2} + (x_{2} - \frac{1}{4})^{2} + x_{3}^{2} x_{1} + x_{2} + x_{3} = 1, 0 \leq x_{i} \leq \frac{1}{2} (i = 1, 2, 3) .$
この問題のラグランジュ関数を、実数 $ν$ と $μ_{i} \geq 0$ , $λ_{i} \geq 0$ （ $i = 1, 2, 3$ ）を用いて
$L = f (x_{1}, x_{2}, x_{3}) + ν (x_{1} + x_{2} + x_{3} - 1) + i = 1 \sum 3 μ_{i} (x_{i} - \frac{1}{2}) - i = 1 \sum 3 λ_{i} x_{i}$
と定める。最適解において KKT 条件をみたす乗数はただ 1 組に定まる。上限制約 $x_{1} \leq \frac{1}{2}$ に対応する乗数 $μ_{1}$ の値を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

目的関数は狭義凸で制約は 1 次式なので、KKT 条件をみたす点が最適解です。どの不等式制約が等号で成り立つ（有効になる）かを見当をつけましょう。

ヒント 2

上限がなければ $x_{1}$ は $\frac{1}{2}$ を超えてしまいます。 $x_{1} = \frac{1}{2}$ が有効で、 $x_{2}, x_{3}$ は内部の点だと仮定すると、 $λ_{i} = 0$ , $μ_{2} = μ_{3} = 0$ になります。

ヒント 3

$2 (x_{2} - \frac{1}{4}) + ν = 0$ , $2 x_{3} + ν = 0$ , $x_{2} + x_{3} = \frac{1}{2}$ から $x_{2} = \frac{3}{8}$ , $x_{3} = \frac{1}{8}$ , $ν = - \frac{1}{4}$ が得られます。残りは $x_{1}$ についての停留条件です。

答えと解説

答えを見る

\frac{5}{4}

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

解説を読む

KKT 条件. 目的関数は狭義凸、制約はすべて 1 次式なので、KKT 条件は最適性の必要十分条件であり、最適解はただ 1 つである。KKT 条件は
$2 (x_{1} - 1) + ν + μ_{1} - λ_{1} = 0, 2 (x_{2} - \frac{1}{4}) + ν + μ_{2} - λ_{2} = 0, 2 x_{3} + ν + μ_{3} - λ_{3} = 0,$
$μ_{i} (x_{i} - \frac{1}{2}) = 0, λ_{i} x_{i} = 0, μ_{i} \geq 0, λ_{i} \geq 0,$
と実行可能性 $x_{1} + x_{2} + x_{3} = 1$ , $0 \leq x_{i} \leq \frac{1}{2}$ である。

有効な制約の見当. 上限制約を無視して単体 ${x_{1} + x_{2} + x_{3} = 1, x_{i} \geq 0}$ への射影を考えると $x_{1}$ が大きくなりすぎる（ $(1, \frac{1}{4}, 0)$ から等しく $τ$ を引くと $x_{1} > \frac{1}{2}$ となる）ので、 $x_{1} = \frac{1}{2}$ が有効で、 $x_{2}, x_{3}$ は $(0, \frac{1}{2})$ の内部にあると予想する。

このとき $λ_{1} = λ_{2} = λ_{3} = 0$ 、 $μ_{2} = μ_{3} = 0$ で、
$2 (x_{2} - \frac{1}{4}) + ν = 0, 2 x_{3} + ν = 0$
より $x_{2} - \frac{1}{4} = x_{3}$ 。 $x_{1} = \frac{1}{2}$ と $x_{1} + x_{2} + x_{3} = 1$ から $x_{2} + x_{3} = \frac{1}{2}$ 、よって $x_{3} = \frac{1}{8}$ , $x_{2} = \frac{3}{8}$ 。これらは $0 < x_{2}, x_{3} < \frac{1}{2}$ をみたす。

乗数. $2 x_{3} + ν = 0$ より $ν = - \frac{1}{4}$ 。 $x_{1}$ についての条件から
$2 (\frac{1}{2} - 1) - \frac{1}{4} + μ_{1} = 0 ⟹ μ_{1} = \frac{5}{4} (\geq 0) .$
すべての KKT 条件（符号条件・相補性条件・実行可能性）が成り立つので、 $(x_{1}, x_{2}, x_{3}) = (\frac{1}{2}, \frac{3}{8}, \frac{1}{8})$ が最適解である（最適値は $\frac{1}{4} + \frac{1}{64} + \frac{1}{64} = \frac{9}{32}$ ）。

乗数の一意性. 最適解で有効な制約は $x_{1} + x_{2} + x_{3} = 1$ と $x_{1} \leq \frac{1}{2}$ だけで、その勾配 $(1, 1, 1)$ , $(1, 0, 0)$ は 1 次独立（LICQ が成り立つ）なので、乗数はただ 1 組に定まる。

答え: $μ_{1} = \frac{5}{4}$

別解

目的関数は狭義凸、制約は線形なので、KKT 条件は最適性の必要十分条件。

停留条件: $2 (x_{i} - c_{i}) + ν + μ_{i} - λ_{i} = 0$ （ $c = (1, \frac{1}{4}, 0)$ ）。乗数を消すと $x_{i} = clip (c_{i} - t, 0, \frac{1}{2})$ , $t = \frac{ν}{2}$ の形になる。

$\sum x_{i} = 1$ となる $t$ を探す。 $- \frac{1}{4} < t < 0$ のとき $x_{1} = \frac{1}{2}$ （ $1 - t > \frac{1}{2}$ ）, $x_{2} = \frac{1}{4} - t \in (\frac{1}{4}, \frac{1}{2})$ , $x_{3} = - t \in (0, \frac{1}{4})$ で、和は $\frac{3}{4} - 2 t = 1$ より $t = - \frac{1}{8}$ 。

よって最適解 $x = (\frac{1}{2}, \frac{3}{8}, \frac{1}{8})$ , $ν = - \frac{1}{4}$ 。

確認: $x_{2}, x_{3}$ は上下限とも非活性なので $μ_{2} = λ_{2} = μ_{3} = λ_{3} = 0$ 。 $x_{2}$ : $2 (\frac{3}{8} - \frac{1}{4}) + ν = \frac{1}{4} - \frac{1}{4} = 0$ ✓、 $x_{3}$ : $2 \cdot \frac{1}{8} - \frac{1}{4} = 0$ ✓（ $ν = - \frac{1}{4}$ はここから一意に決まる）。

$x_{1} = \frac{1}{2} > 0$ なので $λ_{1} = 0$ 。 $2 (\frac{1}{2} - 1) + ν + μ_{1} = 0$ より $- 1 - \frac{1}{4} + μ_{1} = 0$ 、 $μ_{1} = \frac{5}{4} \geq 0$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題