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

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

難易度 3大学院入試の専門科目の標準レベル大学院数学凸最適化・組合せ最適化

$S^{3}$ を $3$ 次実対称行列全体とし、 $A, B \in S^{3}$ に対して $⟨ A, B ⟩ = tr (A B)$ と定める。 $X ⪰ O$ は $X$ が半正定値であることを表す。
$C = 011102120$
として、次の半正定値計画問題 $(P)$ を考える。
$(P) minimize ⟨ C, X ⟩ subject to X_{11} = X_{22} = X_{33} = 1, X \in S^{3}, X ⪰ O$
$(P)$ の最適値を求めよ。

この問題で使うもの

半正定値計画の双対と最適値の決定（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

双対問題 $max y_{1} + y_{2} + y_{3}$ s.t. $C - Diag (y) ⪰ O$ で下界を作り、具体的な $X$ で上界を作って一致させます。

ヒント 2

双対では $C - Diag (y)$ を階数 $1$ の $w w^{T}$ にとれないか考えます。非対角成分の条件 $w_{1} w_{2} = 1$ , $w_{1} w_{3} = 1$ , $w_{2} w_{3} = 2$ から $w$ が決まります。

ヒント 3

主問題では $X$ を平面内の単位ベクトル $v_{1} = (1, 0)$ , $v_{2}, v_{3} = (cos θ, \pm sin θ)$ のグラム行列にとると、目的関数は $u = cos θ$ の 2 次式 $8 u^{2} + 4 u - 4$ になります。

答えと解説

答えを見る

- \frac{9}{2}

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

解説を読む

$⟨ C, X ⟩ = 2 X_{12} + 2 X_{13} + 4 X_{23}$ である。

双対問題

$(P)$ のラグランジュ双対は
$(D) maximize y_{1} + y_{2} + y_{3} subject to S = C - Diag (y_{1}, y_{2}, y_{3}) ⪰ O$
であり、弱双対性より、 $(P)$ の任意の実行可能解 $X$ と $(D)$ の任意の実行可能解 $y$ について
$⟨ C, X ⟩ - (y_{1} + y_{2} + y_{3}) = ⟨ C - Diag (y), X ⟩ = ⟨ S, X ⟩ \geq 0$
（半正定値行列どうしの内積は非負）が成り立つ。

双対の実行可能解（下界）

$w = (\frac{1}{2}, 2, 2)^{T}$ とおくと
$w w^{T} = \frac{1}{2} 11 122122$
で、非対角成分が $C$ と一致する。そこで $y = (- \frac{1}{2}, - 2, - 2)$ とすると $S = C - Diag (y) = w w^{T} ⪰ O$ なので $y$ は $(D)$ の実行可能解で、
$y_{1} + y_{2} + y_{3} = - \frac{1}{2} - 2 - 2 = - \frac{9}{2}$
よって $(P)$ の最適値は $- \frac{9}{2}$ 以上である。

主の実行可能解（上界）

$X$ を単位ベクトル $v_{1}, v_{2}, v_{3}$ のグラム行列 $X_{ij} = v_{i} \cdot v_{j}$ として作る。 $R^{2}$ で $v_{1} = (1, 0)$ , $v_{2} = (cos θ, sin θ)$ , $v_{3} = (cos θ, - sin θ)$ とし、 $u = cos θ$ とおくと
$X_{12} = X_{13} = u, X_{23} = cos 2 θ = 2 u^{2} - 1$
なので
$⟨ C, X ⟩ = 4 u + 4 (2 u^{2} - 1) = 8 u^{2} + 4 u - 4 = 8 (u + \frac{1}{4})^{2} - \frac{9}{2}$
$u = - \frac{1}{4}$ とすると
$X = 1 - \frac{1}{4} - \frac{1}{4} - \frac{1}{4} 1 - \frac{7}{8} - \frac{1}{4} - \frac{7}{8} 1$
はグラム行列なので半正定値で対角成分は $1$ 、 $⟨ C, X ⟩ = 2 (- \frac{1}{4}) + 2 (- \frac{1}{4}) + 4 (- \frac{7}{8}) = - \frac{1}{2} - \frac{1}{2} - \frac{7}{2} = - \frac{9}{2}$ 。

（相補性の確認: $S w$ の向きについて $⟨ S, X ⟩ = \frac{1}{2} v_{1} + 2 (v_{2} + v_{3})^{2}$ で、 $v_{2} + v_{3} = (2 u, 0) = (- \frac{1}{2}, 0) = - \frac{1}{2} v_{1}$ より $0$ になる。）

上界と下界が一致するので、最適値は $- \frac{9}{2}$ である。

別解

$X_{12} = x, X_{13} = y, X_{23} = z$ とおくと $⟨ C, X ⟩ = 2 (x + y + 2 z)$ 。 $X ⪰ O$ かつ対角成分 1 なので $X$ は単位ベクトル $u_{1}, u_{2}, u_{3}$ のグラム行列である。

【上界】 $u_{1}$ を基準に、 $u_{2}, u_{3}$ を $u_{1}$ とのなす角が $\pm t$ となる平面上のベクトルにとると $x = y = cos t, z = cos 2 t$ 。 $x + y + 2 z = 2 cos t + 2 (2 cos^{2} t - 1) = 4 c^{2} + 2 c - 2$ （ $c = cos t$ ）。 $c = - 1/4$ で最小値 $- 9/4$ 。このとき $x = y = - 1/4, z = - 7/8$ 、
$X^{*} = 1 - 1/4 - 1/4 - 1/4 1 - 7/8 - 1/4 - 7/8 1$
固有値を確かめると $X^{*} ⪰ O$ （ $det = 1 + 2 \cdot (- 1/4) (- 1/4) (- 7/8) - 1/16 - 1/16 - 49/64 = 0$ 、主小行列式も非負）で、 $⟨ C, X^{*} ⟩ = 2 (- 1/4 - 1/4 - 7/4) = - 9/2$ 。

【下界（双対）】双対問題は maximize $y_{1} + y_{2} + y_{3}$ subject to $C - Diag (y) ⪰ O$ 。 $y = (- 1/2, - 2, - 2)$ とすると
$C - Diag (y) = 1/2 11 122122 = \frac{1}{2} v v^{⊤}, v = (1, 2, 2)^{⊤} ⪰ O$
なので実行可能で、双対目的値は $- 9/2$ 。弱双対性より任意の実行可能な $X$ で $⟨ C, X ⟩ \geq \sum y_{i} = - 9/2$ 。

上界と下界が一致するので最適値は $- 9/2$ 。検算: $(C - Diag (y)) X^{*} = O$ （相補性）を確認済み。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題