凸計画と KKT 条件の十分性

目的関数が凸（最大化なら凹）で制約が凸集合を表すとき、KKT 点が大域的な最適解になることを使える。 $lo g (a_{i} + x_{i})$ の和の最大化のような問題で、KKT 条件を解いて最適値を求められる

前提

KKT 条件（大学数学最適化・線形計画法）
ヘッセ行列による凸性の判定（大学数学最適化・線形計画法）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

凸計画とは、凸関数を凸集合の上で最小化する問題のことです。凹関数を凸集合の上で最大化する問題も、符号を変えれば凸計画になります。凸計画では、KKT 条件を満たす点（KKT 点）が 1 つ見つかれば、それがそのまま大域的な最適解になります。局所解どうしを比べたり、すべての場合の値を比べ合わせたりする必要はありません。資源配分の問題（ $\sum lo g (a_{i} + x_{i})$ の最大化など）や、非負条件のついた 2 次関数の最小化などで、KKT 条件を解くだけで最適値まで確定させるときに使います。

なぜそうしてよいのか

問題を「 $f (x)$ を最小化、制約 $g_{i} (x) \leq 0$ $(i = 1, \dots, m)$ 」の形にします。実行可能集合を含む開いた凸集合 $D$ をとり、 $f$ と各 $g_{i}$ は $D$ の上で凸かつ全微分可能（たとえば $C^{1}$ 級）とします。ヘッセ行列で凸性を判定するときは、さらに $C^{2}$ 級を仮定します。このとき実行可能集合 ${x ∣ g_{i} (x) \leq 0 (i = 1, \dots, m)}$ は凸集合です。実際、 $g_{i} (x) \leq 0$ , $g_{i} (y) \leq 0$ ならば、線分は $D$ に含まれ、 $0 \leq t \leq 1$ について $g_{i} ((1 - t) x + t y) \leq (1 - t) g_{i} (x) + t g_{i} (y) \leq 0$ が成り立ちます。

まず、凸関数の定義から「接平面より上にある」という不等式を導きます。 $D$ 上の凸関数 $φ$ と 2 点 $x, y \in D$ 、 $0 < t \leq 1$ をとります。定義より $φ (x + t (y - x)) \leq (1 - t) φ (x) + tφ (y)$ なので、変形すると $\frac{φ ( x + t ( y - x )) - φ ( x )}{t} \leq φ (y) - φ (x)$ です。 $φ$ は $x$ で全微分可能なので、 $φ (x + h) = φ (x) + \nabla φ (x) \cdot h + o (∣ h ∣)$ と書けます。 $h = t (y - x)$ を代入して $t \to + 0$ とすると、左辺は $\nabla φ (x) \cdot (y - x)$ に収束します。偏微分可能なだけではこの式は保証されないので、全微分可能性が必要です。よって
$φ (y) \geq φ (x) + \nabla φ (x) \cdot (y - x)$
が成り立ちます。とくに $\nabla φ (x) = 0$ ならば、 $x$ は $D$ 上での $φ$ の大域的な最小点です。

次に、 $x^{*}$ を KKT 点とし、その乗数を $μ_{i} \geq 0$ とします。 $L (x) = f (x) + \sum μ_{i} g_{i} (x)$ は凸関数の非負係数の和なので、 $D$ 上で凸かつ全微分可能です。また KKT 条件から $\nabla L (x^{*}) = 0$ です。したがって、任意の実行可能な $y$ について
$f (y) \geq f (y) + \sum μ_{i} g_{i} (y) = L (y) \geq L (x^{*}) = f (x^{*}) + \sum μ_{i} g_{i} (x^{*}) = f (x^{*})$
が成り立ちます。1 つ目の不等号は $μ_{i} \geq 0$ と $g_{i} (y) \leq 0$ から、2 つ目の不等号は上の不等式から、最後の等号は相補性 $μ_{i} g_{i} (x^{*}) = 0$ から従います。こうして $x^{*}$ が大域的な最小解だとわかります。なお、この十分性の議論では、制約想定（KKT 条件が必要条件になるための仮定）は使っていません。

手順

標準形に直す: 最大化 $max h$ は $min f = - h$ に書き換え、制約はすべて $g_{i} (x) \leq 0$ の形にそろえる（非負条件 $x_{j} \geq 0$ は $- x_{j} \leq 0$ とする）。
凸性を確かめる: 実行可能集合を含む開いた凸集合 $D$ を決める。 $f$ と各 $g_{i}$ が $D$ 上で $C^{2}$ 級であることと、ヘッセ行列が $D$ のすべての点で半正定値であることを調べる。1 次式の制約はそのままで凸である。
KKT 条件を書く: $\nabla f + \sum μ_{i} \nabla g_{i} = 0$ 、 $μ_{i} \geq 0$ 、 $μ_{i} g_{i} = 0$ 、 $g_{i} \leq 0$ の 4 種類。
有効な制約を見当づけて場合分けし、KKT 点を 1 つ求める。そのとき $μ_{i} \geq 0$ と実行可能性 $g_{i} \leq 0$ がすべて成り立つかを必ず確認する。
凸計画なので、条件を満たす KKT 点は大域的な最適解だと結論する。その点で最適値を計算する（最大化なら符号を戻す）。

例題

$x_{1} + x_{2} + x_{3} \leq 4$ 、 $x_{1} \geq 0$ 、 $x_{2} \geq 0$ 、 $x_{3} \geq 0$ のもとで、 $lo g (1 + x_{1}) + lo g (2 + x_{2}) + lo g (4 + x_{3})$ の最大値を求めよ。

例題の解答

【手順 1】 $f (x) = - lo g (1 + x_{1}) - lo g (2 + x_{2}) - lo g (4 + x_{3})$ を最小化する問題に直す。制約は $g_{0} = x_{1} + x_{2} + x_{3} - 4 \leq 0$ 、 $g_{j} = - x_{j} \leq 0$ $(j = 1, 2, 3)$ とする。

【手順 2】 $D = {x_{1} > - 1, x_{2} > - 2, x_{3} > - 4}$ は開いた凸集合で、実行可能集合を含む。 $f$ は $D$ 上で $C^{2}$ 級であり、ヘッセ行列は対角行列 $diag (\frac{1}{( 1 + x _{1} ) ^{2}}, \frac{1}{( 2 + x _{2} ) ^{2}}, \frac{1}{( 4 + x _{3} ) ^{2}})$ である。固有値はすべて正なので正定値であり、 $f$ は $D$ 上で凸である。制約はすべて 1 次式なので凸である。したがってこの問題は凸計画である。

【手順 3】 $g_{0}$ の乗数を $λ$ 、 $g_{j}$ の乗数を $μ_{j}$ とし、 $a_{1} = 1, a_{2} = 2, a_{3} = 4$ とおく。KKT 条件は次のとおり。
・停留条件: $- \frac{1}{a _{j} + x _{j}} + λ - μ_{j} = 0$ $(j = 1, 2, 3)$
・乗数の符号: $λ \geq 0$ 、 $μ_{j} \geq 0$
・相補性: $λ g_{0} = 0$ 、 $μ_{j} x_{j} = 0$
・実行可能性: $g_{0} \leq 0$ 、 $g_{j} \leq 0$

【手順 4】停留条件から $λ = \frac{1}{a _{j} + x _{j}} + μ_{j} > 0$ なので、 $g_{0}$ は有効で $x_{1} + x_{2} + x_{3} = 4$ である。
・まず $x_{1}, x_{2}, x_{3} > 0$ （ $μ_{j} = 0$ ）とすると、 $a_{j} + x_{j} = \frac{1}{λ}$ が 3 つとも共通になる。 $3 \cdot \frac{1}{λ} = 4 + (1 + 2 + 4) = 11$ より $\frac{1}{λ} = \frac{11}{3}$ となるが、 $x_{3} = \frac{11}{3} - 4 = - \frac{1}{3} < 0$ で実行可能でない。
・次に $x_{3} = 0$ 、 $x_{1}, x_{2} > 0$ とすると、 $μ_{1} = μ_{2} = 0$ で $1 + x_{1} = 2 + x_{2} = \frac{1}{λ}$ となる。 $x_{1} + x_{2} = 4$ より $\frac{2}{λ} - 3 = 4$ なので $\frac{1}{λ} = \frac{7}{2}$ 、 $λ = \frac{2}{7}$ である。よって $x_{1} = \frac{5}{2}$ 、 $x_{2} = \frac{3}{2}$ 。さらに $μ_{3} = λ - \frac{1}{4} = \frac{2}{7} - \frac{1}{4} = \frac{1}{28} \geq 0$ である。
この点はすべての制約と $λ, μ_{j} \geq 0$ を満たすので、KKT 点である。

【手順 5】凸計画なので、 $(x_{1}, x_{2}, x_{3}) = (\frac{5}{2}, \frac{3}{2}, 0)$ が大域的な最適解である。最大値は $lo g \frac{7}{2} + lo g \frac{7}{2} + lo g 4 = lo g 49 = 2 lo g 7$ である。

答え: $2 lo g 7$

よくある誤り

凸でない問題でも、KKT 点なら最適解だとしてしまう誤り。例えば $- x^{2}$ を $- 1 \leq x \leq 1$ で最小化すると、 $x = 0$ （乗数はすべて $0$ ）は KKT 点だが、実は最大点である。正しくは、十分性を使う前に $f$ と各 $g_{i}$ の凸性をヘッセ行列などで確認する（この例の最小値は $x = \pm 1$ での $- 1$ ）。
非負条件 $x_{j} \geq 0$ を無視して、等式 $\sum x_{j} = 4$ だけでラグランジュの未定乗数法を使ってしまう誤り。例題では $x_{3} = - \frac{1}{3}$ という実行可能でない点が出てくる。正しくは、 $- x_{j} \leq 0$ も制約として KKT 条件に入れ、 $x_{3} = 0$ の場合を調べて $μ_{3} = \frac{1}{28} \geq 0$ を確認する。
最大化問題のまま $\nabla h + \sum μ_{i} \nabla g_{i} = 0$ と書いて、乗数の符号を逆にしてしまう誤り。正しくは $f = - h$ の最小化に直して $- \nabla h + \sum μ_{i} \nabla g_{i} = 0$ （すなわち $\nabla h = \sum μ_{i} \nabla g_{i}$ ）とし、 $μ_{i} \geq 0$ を確かめる。
1 次式でない等式制約（例: $x^{2} + y^{2} = 1$ ）を凸な制約とみなしてしまう誤り。円周は凸集合ではないので、十分性は使えない。正しくは、等式制約が許されるのは $a \cdot x = b$ のような 1 次式のときだけである。そのときは $a \cdot x - b \leq 0$ と $- (a \cdot x - b) \leq 0$ の 2 つの凸な制約として扱える。

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

凸計画と KKT 条件の十分性

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題