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

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

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

$R^{2}$ 上の関数
$f (x, y) = x^{3} + 2 x y^{2} + y^{2}$
を考える。実数 $c$ に対して
$D_{c} = {(x, y) \in R^{2} ∣ x \geq c, - 1 \leq y \leq 1}$
とおく（ $D_{c}$ は凸集合である）。 $f$ が $D_{c}$ 上で凸関数となる、すなわち任意の $p, q \in D_{c}$ と $0 \leq λ \leq 1$ に対して
$f (λ p + (1 - λ) q) \leq λ f (p) + (1 - λ) f (q)$
が成り立つような $c$ の最小値を求めよ。

この問題で使うもの

ヘッセ行列による凸性の判定（説明と入口の問題）
偏微分と全微分（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$C^{2}$ 級の関数が（内部をもつ）凸集合上で凸であることは、その集合上でヘッセ行列が半正定値であることと同値になる。まずヘッセ行列を計算する。

ヒント 2

$\nabla^{2} f = (6 x 4 y 4 y 4 x + 2)$ 。 $2 \times 2$ 対称行列が半正定値 $⟺$ 対角成分が $0$ 以上かつ行列式が $0$ 以上。

ヒント 3

行列式は $24 x^{2} + 12 x - 16 y^{2}$ で、 $- 1 \leq y \leq 1$ の範囲では $y^{2} = 1$ のときが最も厳しい。 $x \geq 0$ と $6 x^{2} + 3 x - 4 \geq 0$ がすべての $x \geq c$ で成り立つ条件を考える。

答えと解説

答えを見る

\frac{- 3 + 105}{12}

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

解説を読む

用いる事実　 $f$ は $C^{2}$ 級で、 $D_{c}$ は内部が空でない閉凸集合である。このとき
- $f$ が $D_{c}$ 上で凸 $⟹$ $D_{c}$ の内部の各点でヘッセ行列が半正定値、
- $D_{c}$ の各点でヘッセ行列が半正定値 $⟹$ $f$ は $D_{c}$ 上で凸

が成り立つ（後者は、 $D_{c}$ 内の線分上で $φ (t) = f (q + t (p - q))$ とおくと $φ^{''} (t) = (p - q)^{T} \nabla^{2} f (p - q) \geq 0$ となることからわかる）。

ヘッセ行列
$f_{x} = 3 x^{2} + 2 y^{2}, f_{y} = 4 x y + 2 y,$
$f_{xx} = 6 x, f_{x y} = 4 y, f_{y y} = 4 x + 2$
より
$\nabla^{2} f (x, y) = (6 x 4 y 4 y 4 x + 2), det \nabla^{2} f = 6 x (4 x + 2) - 16 y^{2} = 24 x^{2} + 12 x - 16 y^{2} .$
$2 \times 2$ 対称行列が半正定値であるための必要十分条件は、対角成分がともに $0$ 以上かつ行列式が $0$ 以上であることなので、
$x \geq 0, 4 x + 2 \geq 0, 24 x^{2} + 12 x - 16 y^{2} \geq 0.$

$- 1 \leq y \leq 1$ での条件　 $x$ を固定すると、行列式 $24 x^{2} + 12 x - 16 y^{2}$ は $- 1 \leq y \leq 1$ の範囲で $y^{2} = 1$ のとき最小になる。よって、 $x$ を固定したとき $- 1 \leq y \leq 1$ のすべての点 $(x, y)$ でヘッセ行列が半正定値となる条件は
$x \geq 0 かつ 24 x^{2} + 12 x - 16 \geq 0 ⟺ x \geq 0 かつ 6 x^{2} + 3 x - 4 \geq 0.$
$6 x^{2} + 3 x - 4 = 0$ の解は $x = \frac{- 3 \pm 9 + 96}{12} = \frac{- 3 \pm 105}{12}$ なので、 $x \geq 0$ とあわせて
$x \geq c_{0} := \frac{- 3 + 105}{12} (\approx 0.604)$
が条件である。

十分性　 $c = c_{0}$ のとき、 $D_{c_{0}}$ の各点 $(x, y)$ で $x \geq c_{0} > 0$ , $4 x + 2 > 0$ であり、 $24 x^{2} + 12 x - 16 y^{2} \geq 24 x^{2} + 12 x - 16 \geq 0$ なので、ヘッセ行列は半正定値。よって $f$ は $D_{c_{0}}$ 上で凸である（ $c \geq c_{0}$ でも同様）。

必要性　 $c < c_{0}$ とする。 $max (c, 0) < x_{0} < c_{0}$ をみたす $x_{0}$ をとると $24 x_{0}^{2} + 12 x_{0} - 16 < 0$ 。連続性から、 $1$ に十分近い $y_{0}$ （ $0 < y_{0} < 1$ ）で $24 x_{0}^{2} + 12 x_{0} - 16 y_{0}^{2} < 0$ となる。点 $(x_{0}, y_{0})$ は $D_{c}$ の内部にあり、そこでヘッセ行列の行列式が負なので半正定値でない。したがって $f$ は $D_{c}$ 上で凸でない。

以上より、求める $c$ の最小値は
$\frac{- 3 + 105}{12} .$

別解

$f$ は $C^{2}$ 級で、 $D_{c}$ は内部が空でない凸集合なので、 $D_{c}$ 上で凸であることは、内部の各点でヘッセ行列が半正定値であることと同値である（境界の点は連続性より従う）。

$f_{x} = 3 x^{2} + 2 y^{2}$ , $f_{y} = 4 x y + 2 y$ より $f_{xx} = 6 x$ , $f_{x y} = 4 y$ , $f_{y y} = 4 x + 2$ 。ヘッセ行列は $H = (6 x 4 y 4 y 4 x + 2)$ 。

半正定値となる条件は $6 x \geq 0$ , $4 x + 2 \geq 0$ , $det H = 6 x (4 x + 2) - 16 y^{2} = 24 x^{2} + 12 x - 16 y^{2} \geq 0$ 。

$D_{c}$ の内部は $x > c$ , $- 1 < y < 1$ 。 $y^{2}$ は 1 に任意に近づけるので、すべての内部の点で $det H \geq 0$ となる条件は、 $x > c$ の全ての $x$ で $24 x^{2} + 12 x - 16 \geq 0$ （ $y^{2} \to 1$ の極限）かつ $x \geq 0$ 。すなわち $6 x^{2} + 3 x - 4 \geq 0$ , $x \geq 0$ より $x \geq x_{0} = \frac{- 3 + 105}{12} \approx 0.604$ 。

$x \geq 0$ で $24 x^{2} + 12 x$ は単調増加なので、 $x > c$ のすべての点で条件が成り立つ $⟺ c \geq x_{0}$ 。 $c < x_{0}$ なら、 $x_{0}$ より小さい $x$ と $∣ y ∣$ が 1 に近い点でヘッセ行列が半正定値でなくなる（ $c < 0$ なら $f_{xx} < 0$ ）。 $c = x_{0}$ では内部で $x > x_{0}$ より $det H > 0$ かつ $f_{xx} > 0$ なので凸。

検算: $x = x_{0}$ , $y = \pm 1$ で $6 x^{2} + 3 x - 4 = 0$ を確かめると $24 x^{2} + 12 x = 16$ となり $det H = 0$ 。 $x = 0.5$ , $y = 1$ では $det = 6 + 6 - 16 = - 4 < 0$ で凸でない。

よって最小値は $\frac{- 3 + 105}{12}$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題