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

難易度 4大学院入試の難問レベル証明問題大学院数学凸最適化・組合せ最適化

$n \geq 2$ を整数とし、 $J$ を成分がすべて $1$ の $n$ 次正方行列、 $I$ を $n$ 次単位行列、 $W = J - I$ とする。 $x \in R^{n}$ を変数とする最適化問題
$(P) minimize x^{⊤} W x subject to x_{i}^{2} - 1 = 0 (i = 1, \dots, n)$
を考え、その最適値を $p^{*}$ とする。 $ν \in R^{n}$ に対しラグランジュ関数を
$L (x, ν) = x^{⊤} W x + i = 1 \sum n ν_{i} (x_{i}^{2} - 1)$
と定め、双対関数を $g (ν) = in f_{x \in R^{n}} L (x, ν) \in [- \infty, \infty)$ 、双対問題の最適値を $d^{*} = sup_{ν \in R^{n}} g (ν)$ とする。

双対ギャップ $p^{*} - d^{*}$ が、 $n$ が奇数のとき $1$ 、 $n$ が偶数のとき $0$ であることを証明せよ。

この問題で使うもの

非凸・整数の問題の双対ギャップ（説明と入口の問題）
ラグランジュ双対関数と弱双対性（説明と入口の問題）
半正定値計画の双対と最適値の決定（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$p^{*}$ と $d^{*}$ を別々に正確に求めます。主問題は実行可能集合が ${\pm 1}^{n}$ であることに注目し、双対問題はまず $g (ν)$ を行列の半正定値条件で書き表しましょう。

ヒント 2

$x^{⊤} W x = (\sum_{i} x_{i})^{2} - n$ と書けます。また $L (x, ν) = x^{⊤} (W + diag (ν)) x - \sum_{i} ν_{i}$ なので、 $g (ν)$ は $W + diag (ν) ⪰ 0$ のとき $- \sum_{i} ν_{i}$ 、そうでなければ $- \infty$ です。

ヒント 3

$d^{*}$ の上からの評価には、 $W + diag (ν) ⪰ 0$ をベクトル $u_{k} = e_{k} - \frac{1}{n} 1$ （ $k = 1, \dots, n$ ）に適用して足し合わせ、 $\sum_{i} ν_{i}$ の下界を導きます。下からは $ν = 1$ を試してみましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$x^{⊤} W x = (\sum_{i} x_{i})^{2} - n$ と書き直し、 $\sum_{i} x_{i}$ の偶奇と達成例から $n$ 偶数で $p^{*} = - n$ 、奇数で $p^{*} = 1 - n$ を導いている（2 点）
$L (x, ν) = x^{⊤} (W + diag ν) x - \sum ν_{i}$ と書き、半正定値なら $g (ν) = - \sum ν_{i}$ 、そうでなければ $x = t v$ で $- \infty$ になることを示している（2 点）
$W + diag ν ⪰ 0$ から $\sum_{i} ν_{i} \geq n$ を、 $e_{k} - \frac{1}{n} 1$ への二次形式の和（または $I - \frac{1}{n} J$ との内積）を計算して正しく導き、 $d^{*} \leq - n$ としている（3 点）
$ν = 1$ で $W + I = J ⪰ 0$ となることを確かめて $d^{*} \geq - n$ を示し、 $d^{*} = - n$ を確定している（2 点）
$p^{*} - d^{*}$ を計算し、奇数で $1$ 、偶数で $0$ と結論している（1 点）

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

模範解答を読む

$1 = (1, \dots, 1)^{⊤}$ とおくと $J = 1 1^{⊤}$ である。 $p^{*}$ と $d^{*}$ をそれぞれ求めて差をとる。

1. 主問題の最適値 $p^{*}$ 。 制約 $x_{i}^{2} = 1$ は $x_{i} \in {1, - 1}$ と同値なので、実行可能集合は ${\pm 1}^{n}$ （有限集合で空でない）であり、最小値が存在する。 $s = \sum_{i} x_{i} = 1^{⊤} x$ とおくと
$x^{⊤} W x = x^{⊤} 1 1^{⊤} x - x^{⊤} x = s^{2} - i \sum x_{i}^{2} = s^{2} - n .$
$x$ の成分のうち $+ 1$ の個数を $a$ とすると $s = a - (n - a) = 2 a - n$ で、 $a$ は $0 \leq a \leq n$ の整数を自由にとれる。
- $n$ が偶数のとき、 $a = n /2$ で $s = 0$ となり $s^{2} \geq 0$ の下限 $0$ が達成されるので $p^{*} = - n$ 。
- $n$ が奇数のとき、 $s = 2 a - n$ は奇数なので $s \neq = 0$ 、よって $s^{2} \geq 1$ 。 $a = (n + 1) /2$ で $s = 1$ となり達成されるので $p^{*} = 1 - n$ 。

2. 双対関数 $g$ 。 $D_{ν} = diag (ν_{1}, \dots, ν_{n})$ 、 $M_{ν} = W + D_{ν}$ とおくと、 $\sum_{i} ν_{i} x_{i}^{2} = x^{⊤} D_{ν} x$ より
$L (x, ν) = x^{⊤} M_{ν} x - i = 1 \sum n ν_{i} .$
- $M_{ν} ⪰ 0$ のとき、すべての $x$ で $x^{⊤} M_{ν} x \geq 0$ であり $x = 0$ で $0$ となるので、 $g (ν) = - \sum_{i} ν_{i}$ 。
- $M_{ν} \neq ⪰ 0$ のとき、 $v^{⊤} M_{ν} v < 0$ となる $v$ があり、 $x = t v$ とすれば $L (t v, ν) = t^{2} v^{⊤} M_{ν} v - \sum_{i} ν_{i} \to - \infty (t \to \infty)$ なので $g (ν) = - \infty$ 。
したがって
$d^{*} = sup {- i = 1 \sum n ν_{i} : ν \in R^{n}, W + D_{ν} ⪰ 0}$
である（ $ν = 1$ が下の通り条件を満たすので、この集合は空でない）。

3. $d^{*} \leq - n$ 。 $ν$ を $M_{ν} ⪰ 0$ を満たす任意のベクトルとする。 $k = 1, \dots, n$ に対し $u_{k} = e_{k} - \frac{1}{n} 1$ （ $e_{k}$ は第 $k$ 標準基底ベクトル）とおくと、半正定値性より $u_{k}^{⊤} M_{ν} u_{k} \geq 0$ なので
$0 \leq k = 1 \sum n u_{k}^{⊤} M_{ν} u_{k} .$
右辺を計算する。 $u_{k}^{⊤} M_{ν} u_{k} = e_{k}^{⊤} M_{ν} e_{k} - \frac{2}{n} e_{k}^{⊤} M_{ν} 1 + \frac{1}{n ^{2}} 1^{⊤} M_{ν} 1$ （ $M_{ν}$ の対称性を使った）を $k$ について足すと、 $\sum_{k} e_{k} = 1$ より
$k = 1 \sum n u_{k}^{⊤} M_{ν} u_{k} = tr M_{ν} - \frac{2}{n} 1^{⊤} M_{ν} 1 + \frac{1}{n} 1^{⊤} M_{ν} 1 = tr M_{ν} - \frac{1}{n} 1^{⊤} M_{ν} 1 .$
$W$ の対角成分は $0$ なので $tr M_{ν} = \sum_{i} ν_{i}$ 。また $1^{⊤} W 1 = n^{2} - n$ 、 $1^{⊤} D_{ν} 1 = \sum_{i} ν_{i}$ なので $1^{⊤} M_{ν} 1 = n (n - 1) + \sum_{i} ν_{i}$ 。 $S = \sum_{i} ν_{i}$ とおくと
$0 \leq S - \frac{n ( n - 1 ) + S}{n} = \frac{n - 1}{n} S - (n - 1) .$
$n \geq 2$ より $n - 1 > 0$ なので、両辺を $\frac{n - 1}{n}$ で割って $S \geq n$ 、すなわち $g (ν) = - S \leq - n$ 。 $M_{ν} \neq ⪰ 0$ のときは $g (ν) = - \infty$ なので、すべての $ν$ で $g (ν) \leq - n$ 、よって $d^{*} \leq - n$ 。

4. $d^{*} \geq - n$ 。 $ν = 1$ とすると $M_{ν} = W + I = J = 1 1^{⊤}$ で、 $x^{⊤} J x = (1^{⊤} x)^{2} \geq 0$ より半正定値。よって $g (1) = - n$ であり $d^{*} \geq - n$ 。3 と合わせて $d^{*} = - n$ 。

5. 結論。 1 と 4 より
$p^{*} - d^{*} = {(1 - n) - (- n) = 1 (- n) - (- n) = 0 (n が奇数) (n が偶数)$
となる（いずれも弱双対性 $p^{*} \geq d^{*}$ と整合する）。以上で、双対ギャップは $n$ が奇数のとき $1$ 、偶数のとき $0$ であることが示された。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる