半正定値制約と小さな半正定値計画

$2 \times 2$ 行列の半正定値条件（対角成分 $\geq 0$ かつ行列式 $\geq 0$ ）やシューア補行列を使って、半正定値制約を不等式に直し、小さな半正定値計画の最適値を求められる

前提

2 次形式の標準形と符号（大学数学線形代数）
区間での最大・最小（数学II 微分法と積分法）

この技能までの道筋（66 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）
基底の変換と表現行列（大学数学線形代数）
対角化と行列の累乗（大学数学線形代数）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
三角比の定義と値（数学I 図形と計量）
内積となす角（数学C ベクトル）
内積空間とグラム・シュミットの直交化（大学数学線形代数）
対称行列の直交対角化（大学数学線形代数）
2 次形式の標準形と符号（大学数学線形代数）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
区間での最大・最小（数学II 微分法と積分法）

説明

対称行列 $M$ が半正定値であるとは、すべてのベクトル $v$ について $v^{T} M v \geq 0$ が成り立つことで、 $M ⪰ 0$ と書きます。成分に変数を含む対称行列が半正定値であるという制約（半正定値制約）のもとで 1 次式を最小化・最大化する問題を半正定値計画といい、制御・組合せ最適化の緩和・統計などで広く使われます。この技能では、 $2 \times 2$ 行列の半正定値条件「対角成分 $\geq 0$ かつ行列式 $\geq 0$ 」やシューア補行列を使って半正定値制約を普通の不等式に書き直し、変数の少ない半正定値計画の最適値を計算します。

なぜそうしてよいのか

実対称行列 $M$ は直交行列 $P$ で $M = P diag (λ_{1}, \dots, λ_{n}) P^{T}$ と対角化できます。 $w = P^{T} v$ とおくと $v^{T} M v = \sum_{i} λ_{i} w_{i}^{2}$ で、 $v$ が全体を動けば $w$ も全体を動くので、 $M ⪰ 0$ はすべての固有値が $0$ 以上であることと同値です。

$2 \times 2$ の場合 $M = (a b b c)$ の固有値 $λ_{1}, λ_{2}$ （実数）は $λ_{1} + λ_{2} = a + c$ , $λ_{1} λ_{2} = det M = a c - b^{2}$ を満たします（固有方程式 $λ^{2} - (a + c) λ + (a c - b^{2}) = 0$ の解と係数の関係）。実数 2 つが両方 $0$ 以上であることは「和 $\geq 0$ かつ積 $\geq 0$ 」と同値です。また $M ⪰ 0$ なら $v = (1, 0)^{T}, (0, 1)^{T}$ を入れて $a \geq 0$ , $c \geq 0$ 。逆に $a \geq 0, c \geq 0$ なら和 $a + c \geq 0$ です。以上から $(a b b c) ⪰ 0 ⟺ a \geq 0, c \geq 0, a c - b^{2} \geq 0.$ 対角成分の条件は片方だけでは足りません（ $a = b = 0, c = - 1$ は $a \geq 0$ , $det = 0$ だが半正定値でない）。なお $a > 0$ のときは、 $a c \geq b^{2} \geq 0$ から $c \geq 0$ が自動的に出るので、「 $a > 0$ かつ $a c - b^{2} \geq 0$ 」だけで十分です。

大きな行列はシューア補行列で小さくします。 $M = (A B^{T} B C)$ （ $A, C$ は対称、 $A$ は正定値＝固有値がすべて正なので可逆）とし、 $Q = (I O - A^{- 1} B I)$ とおきます。ブロックごとに掛けると $M Q = (A \cdot I + B \cdot O B^{T} \cdot I + C \cdot O A (- A^{- 1} B) + B B^{T} (- A^{- 1} B) + C) = (A B^{T} O C - B^{T} A^{- 1} B) .$ また $A$ が対称なので $(A^{- 1})^{T} = (A^{T})^{- 1} = A^{- 1}$ であり、 $(A^{- 1} B)^{T} = B^{T} A^{- 1}$ 、よって $Q^{T} = (I - B^{T} A^{- 1} O I)$ 。これを左から掛けて $Q^{T} (M Q) = (I \cdot A + O \cdot B^{T} - B^{T} A^{- 1} A + B^{T} I \cdot O + O (C - B^{T} A^{- 1} B) - B^{T} A^{- 1} O + (C - B^{T} A^{- 1} B)) = (A O O C - B^{T} A^{- 1} B) .$ $Q$ は可逆（上三角ブロックで対角が $I$ ）なので、 $v = Qw$ と置き換えると「 $v^{T} M v \geq 0 (\forall v)$ 」と「 $w^{T} (Q^{T} M Q) w \geq 0 (\forall w)$ 」は同値です。右辺はブロック対角で、 $w = (w_{1}, w_{2})$ に対し $w_{1}^{T} A w_{1} + w_{2}^{T} S w_{2}$ （ $S = C - B^{T} A^{- 1} B$ ）となり、 $A$ は正定値なので $M ⪰ 0 ⟺ S = C - B^{T} A^{- 1} B ⪰ 0$ が得られます（ $w_{1} = 0$ とおけば $\Rightarrow$ 、各項が $0$ 以上なので $\Leftarrow$ ）。 $S$ を $A$ のシューア補行列といいます。

補助例: $t > 0$ のとき $M = t 11 1 x 0 10 y$ では $A = (t)$ , $B = (11)$ , $C = (x 0 0 y)$ なので $M ⪰ 0 ⟺ (x - \frac{1}{t} - \frac{1}{t} - \frac{1}{t} y - \frac{1}{t}) ⪰ 0 ⟺ x \geq \frac{1}{t}, y \geq \frac{1}{t}, (x - \frac{1}{t}) (y - \frac{1}{t}) \geq \frac{1}{t ^{2}}$ と、 $3 \times 3$ の制約が $2 \times 2$ の条件、さらに普通の不等式に落ちます。

手順

半正定値制約に現れる行列を確認する。 $3 \times 3$ 以上なら、正定値とわかっている左上ブロック $A$ （例えば $1 \times 1$ の $(t)$ , $t > 0$ ）を選び、シューア補行列 $C - B^{T} A^{- 1} B$ の半正定値条件に置き換えて $2 \times 2$ や $1 \times 1$ に小さくする
$2 \times 2$ なら「対角成分 2 つが $\geq 0$ 、行列式 $\geq 0$ 」の 3 つの不等式に書き直す: $(a b b c) ⪰ 0 ⟺ a \geq 0, c \geq 0, a c - b^{2} \geq 0$ （ $1 \times 1$ なら成分 $\geq 0$ ）
不等式から実行可能領域を求め、ありえない場合（例えば $a = 0$ なのに $b \neq = 0$ ）を除く
目的関数が最小（最大）になるのは不等式が等号の境界上であることを見て、変数を 1 つ消去して 1 変数関数にする
区間での最大・最小（増減表）で最適値を求め、そのときの点が元の半正定値制約を満たすことを確かめる

例題

実数 $x, y$ が $(x 2 2 y) ⪰ 0$ を満たすとき、 $2 x + y$ の最小値を求めよ。ただし $M ⪰ 0$ は対称行列 $M$ が半正定値であることを表す。

例題の解答

手順 1: 制約の行列はすでに $2 \times 2$ の対称行列なので、シューア補行列による縮小は不要。

手順 2: 半正定値条件は $x \geq 0, y \geq 0, x y - 4 \geq 0.$

手順 3: $x = 0$ だと $x y - 4 = - 4 < 0$ となり不可能なので $x > 0$ 。このとき条件は $y \geq \frac{4}{x}$ と同値（ $y \geq 0$ は自動的に満たされる）。

手順 4: $x > 0$ を固定すると $2 x + y$ は $y$ が小さいほど小さいので、 $y = \frac{4}{x}$ のとき最小。よって $f (x) = 2 x + \frac{4}{x} (x > 0)$ の最小値を求めればよい。

手順 5: $f^{'} (x) = 2 - \frac{4}{x ^{2}} = \frac{2 ( x ^{2} - 2 )}{x ^{2}}$ 。 $0 < x < 2$ で $f^{'} < 0$ 、 $x > 2$ で $f^{'} > 0$ なので、 $x = 2$ で最小値 $f (2) = 22 + \frac{4}{2} = 42$ 。このとき $y = 22$ で、 $x > 0, y > 0, x y = 4$ なので半正定値制約を満たす。

よって最小値は $42$ 。

答え: $42$

よくある誤り

$2 \times 2$ の半正定値条件を「 $a \geq 0$ かつ $det \geq 0$ 」だけで判定してしまう誤り。 $(00 0 - 1)$ は $a = 0 \geq 0$ , $det = 0 \geq 0$ だが $v = (0, 1)^{T}$ で $v^{T} M v = - 1 < 0$ 。正しくは $a \geq 0, c \geq 0, a c - b^{2} \geq 0$ の 3 つを確かめる（ $a > 0$ のときは $a > 0$ と $a c - b^{2} \geq 0$ だけで十分で、 $c \geq 0$ は自動的に出る）。
行列式 $\geq 0$ だけで半正定値としてしまう誤り。 $(- 1 0 0 - 1)$ は $det = 1 > 0$ だが負定値。正しくは対角成分（または固有値の和 $a + c$ ）の符号も必要。
行列式の符号を誤って $a c + b^{2} \geq 0$ や $a c - 2 b \geq 0$ としてしまう誤り。例題で $x y + 4 \geq 0$ とすると制約がほぼなくなる。正しくは $det (x 2 2 y) = x y - 4 \geq 0$ 。
シューア補行列を使うとき $A$ が正定値（可逆）であることを確かめずに $C - B^{T} A^{- 1} B ⪰ 0$ を使う、あるいは $C - B A^{- 1} B^{T}$ と転置の位置を誤る誤り。正しくは $M = (A B^{T} B C)$ , $A$ 正定値のとき $M ⪰ 0 ⟺ C - B^{T} A^{- 1} B ⪰ 0$ （補助例なら $t > 0$ を確かめてから使う）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
実数 $x, y$ を変数とする次の最適化問題を考える。ここで、実対称行列 $A$ について $A ⪰ O$ は $A$ が半正定値であることを表す。
$minimize subject to x + 4 y (x 2 2 y) ⪰ O$
この問題の最適値（目的関数の最小値）を求めよ。

この技能を使う問題

この技能の次に学べること

半正定値計画の双対と最適値の決定（大学院数学凸最適化・組合せ最適化）