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

凸最適化・組合せ最適化の問題

難易度 2大学院の講義の演習問題レベル大学院数学凸最適化・組合せ最適化

$R^{3}$ に標準内積 $⟨ \cdot, \cdot ⟩$ を入れる。関数 $f : R^{3} \to R \cup {+ \infty}$ を
$f (x) = {x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{1} x_{2} + x_{2} x_{3} + \infty (x_{1} \geq 0, x_{2} \geq 0, x_{3} \geq 0) (otherwise)$
で定める。 $f$ の凸共役（ルジャンドル・フェンシェル変換）を
$f^{*} (y) = x \in R^{3} sup (⟨ y, x ⟩ - f (x))$
とするとき、 $y = (3, 1, 3)$ における値 $f^{*} (3, 1, 3)$ を求めよ。

この問題で使うもの

凸共役（ルジャンドル・フェンシェル変換）（説明と入口の問題）
掃き出し法による逆行列（説明と入口の問題）
2 次形式の標準形と符号（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$f^{*} (y)$ は、非負象限 $x \geq 0$ 上で凹な 2 次関数 $⟨ y, x ⟩ - f (x)$ を最大化した値です。KKT 条件で最大点を特定しましょう。

ヒント 2

$f (x) = \frac{1}{2} ⟨ x, A x ⟩$ （ $A$ は三重対角行列 $210121012$ ）と書けます。KKT 条件は $x \geq 0$ 、 $y - A x \leq 0$ 、 $x_{i} (y - A x)_{i} = 0$ です。

ヒント 3

制約なしの最大点 $A^{- 1} y$ は $(\frac{5}{2}, - 2, \frac{5}{2})$ で、第 2 成分が負になります。 $x_{2} = 0$ として残りの変数で最大化すると $x_{1} = x_{3} = \frac{3}{2}$ が得られます。この点で KKT 条件を確かめましょう。

答えと解説

答えを見る

\frac{9}{2}

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

解説を読む

$A = 210121012$ とおくと、 $x \geq 0$ （各成分が非負）のとき $f (x) = \frac{1}{2} ⟨ x, A x ⟩$ である。 $A$ の首座小行列式は $2, 3, 4$ ですべて正なので $A$ は正定値であり、
$f^{*} (y) = x \geq 0 sup (⟨ y, x ⟩ - \frac{1}{2} ⟨ x, A x ⟩)$
は、強凹な関数を閉凸集合 $R_{\geq 0}^{3}$ 上で最大化する問題になる。よって最大値は有限で、最大点はただ一つ存在する。制約は線形なので、KKT 条件が最大点であるための必要十分条件になる。 $g (x) = y - A x$ （目的関数の勾配）とおくと、KKT 条件は
$x \geq 0, g (x) \leq 0, x_{i} g_{i} (x) = 0 (i = 1, 2, 3)$
である。

まず制約を無視した最大点は $x = A^{- 1} y$ である。 $A^{- 1} = \frac{1}{4} 3 - 2 1 - 2 4 - 2 1 - 2 3$ より
$A^{- 1} y = \frac{1}{4} (9 - 2 + 3, - 6 + 4 - 6, 3 - 2 + 9) = (\frac{5}{2}, - 2, \frac{5}{2})$
となり、第 2 成分が負なので実行可能でない。

そこで $x_{2} = 0$ とし、 $x_{1}, x_{3}$ について制約なしで最大化する。 $x_{2} = 0$ のとき目的関数は $(3 x_{1} - x_{1}^{2}) + (3 x_{3} - x_{3}^{2})$ となるので、最大点は $x_{1} = x_{3} = \frac{3}{2}$ である。 $x = (\frac{3}{2}, 0, \frac{3}{2})$ で KKT 条件を確かめる。
$A x = (3, \frac{3}{2} + \frac{3}{2}, 3) = (3, 3, 3), g (x) = y - A x = (0, - 2, 0)$
となる。したがって $x \geq 0$ 、 $g (x) \leq 0$ であり、 $x_{i} g_{i} = 0$ もすべての $i$ で成り立つ。よって $x = (\frac{3}{2}, 0, \frac{3}{2})$ が最大点である。

値を計算する。 $⟨ y, x ⟩ = \frac{9}{2} + \frac{9}{2} = 9$ 、 $\frac{1}{2} ⟨ x, A x ⟩ = \frac{1}{2} (\frac{3}{2} \cdot 3 + \frac{3}{2} \cdot 3) = \frac{9}{2}$ である。よって
$f^{*} (3, 1, 3) = 9 - \frac{9}{2} = \frac{9}{2} .$

（注意：制約なし最大点 $(\frac{5}{2}, - 2, \frac{5}{2})$ の負の成分を $0$ に置き換えた点 $(\frac{5}{2}, 0, \frac{5}{2})$ は最大点ではない。）

別解

$f (x) = x^{T} Q x$ （ $x \geq 0$ ）で、 $Q = 1 1/2 0 1/2 1 1/2 0 1/2 1$ である。 $Q$ の固有値は $1, 1 \pm \frac{2}{2}$ で、すべて正だから $Q$ は正定値であり、 $f$ は凸である。

求めるのは、 $x \geq 0$ のもとでの $g (x) = 3 x_{1} + x_{2} + 3 x_{3} - (x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{1} x_{2} + x_{2} x_{3})$ の最大値である。 $g$ は狭義凹だから、KKT 条件を満たす点が最大点になる。

まず制約なしで $\nabla g = 0$ を解く。 $2 x_{1} + x_{2} = 3, x_{1} + 2 x_{2} + x_{3} = 1, x_{2} + 2 x_{3} = 3$ より $x_{1} = x_{3} = 5/2, x_{2} = - 2 < 0$ となり、制約に反する。そこで $x_{2} = 0$ と仮定する。

$x_{2} = 0$ のとき $g = 3 x_{1} + 3 x_{3} - x_{1}^{2} - x_{3}^{2}$ なので、 $x_{1} = x_{3} = 3/2$ となる。

$x_{2}$ 方向の KKT 条件を確かめる。 $\partial g / \partial x_{2} = 1 - (x_{1} + 2 x_{2} + x_{3}) = 1 - 3 = - 2 \leq 0$ なので成り立つ。 $x_{1}, x_{3} > 0$ の方向では偏微分が 0 である。

最大値は $g (3/2, 0, 3/2) = 9 - \frac{9}{4} - \frac{9}{4} = \frac{9}{2}$ である。

検算として、 $x = (3/2, ε, 3/2)$ を考えると $g = 9/2 - 2 ε - ε^{2} < 9/2$ （ $ε > 0$ ）となり、 $x_{2} = 0$ が最適であることと整合する。

よって $f^{*} (3, 1, 3) = 9/2$ 。

凸最適化・組合せ最適化の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題