最適性条件の地図｜数理最適化

← 数理最適化一覧

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：局所最適と大域最適・凸性の役割　|　関連：不等式制約とKKT条件

要点（BLUF）

1次条件（勾配ゼロ $\nabla f = 0$ ）は局所最適の 必要条件。極小・極大・鞍点を区別しない。
2次条件（ヘッセ行列 $\nabla^2 f$ の正定値性）で極小かどうかを判定する。
制約が付くと、勾配ゼロは KKT 条件（勾配＝制約勾配の線形結合）に一般化される。これが第4章の主役。

概念 ── 「最適なら必ず成り立つ式」を探す

最適性条件とは「ここが最適解なら、必ずこの式が成り立つ」という関係。これがあれば、最適解の候補を方程式を解いて絞り込むことができる。必要条件（最適なら成り立つ）と十分条件（成り立てば最適）を区別するのが肝心。

無制約の最適性条件

1次の必要条件（停留点）

$f$ が微分可能で $x^\star$ が局所最適なら、

\nabla f(x^\star) = 0.

これを満たす点を 停留点という。直観：どの方向に少し動かしても1次の変化がゼロ（坂がフラット）でなければ、改善できてしまう。ただし停留点には 極小・極大・鞍点の3種が混じる。

2次の条件（極小の判定）

ヘッセ行列 $H = \nabla^2 f(x^\star)$ を使う：

2次の必要条件： $x^\star$ が局所極小 $\Rightarrow$ $H \succeq 0$ （半正定値）。
2次の十分条件： $\nabla f(x^\star)=0$ かつ $H \succ 0$ （正定値） $\Rightarrow$ $x^\star$ は 狭義局所極小。

ヘッセ $H$	停留点の種類
正定値 $H \succ 0$	局所極小
負定値 $H \prec 0$	局所極大
不定（正と負の固有値）	鞍点
半定値（境界）	判定不能（高次が必要）

要するに：1次条件で「坂がフラットな点」を見つけ、2次条件で「お椀型か山型か鞍か」を見分ける。

制約付きへの拡張 ── KKT 条件の予告

制約があると「勾配ゼロ」では不十分。最適点が制約境界上にあると、目的を下げたい方向が制約に阻まれて打ち消される。この釣り合いを表すのが KKT（Karush–Kuhn–Tucker）条件。問題

\min f(x)\ \text{s.t.}\ g_i(x)\le 0,\ h_j(x)=0

に対し、最適点では乗数 $\lambda_i \ge 0,\ \mu_j$ が存在して

\nabla f(x^\star) + \sum_i \lambda_i \nabla g_i(x^\star) + \sum_j \mu_j \nabla h_j(x^\star) = 0,

\lambda_i \ge 0,\quad \lambda_i\, g_i(x^\star) = 0 \ (\text{相補性}),\quad g_i(x^\star)\le 0,\quad h_j(x^\star)=0.

直観：「目的を下げる力 $-\nabla f$ 」が「効いている制約の壁の法線方向 $\nabla g_i$ 」の重ね合わせとちょうど釣り合っている。詳しい導出は等式制約とラグランジュ乗数・不等式制約とKKT条件。

凸性で必要が十分に変わる

一般には KKT は 必要条件にすぎない。だが問題が凸（ $f$ と各 $g_i$ が凸、 $h_j$ が線形）で適切な制約想定（Slater 条件など）を満たすと、KKT は十分条件にもなり、KKT 点＝大域最適になる（凸最適化問題と双対理論）。これが「凸だと嬉しい」のもう一つの顔。

graph LR
  A["1次条件 grad f = 0"] --> B["2次条件 ヘッセの正定値性"]
  A --> C["制約付き: KKT条件"]
  C --> D["凸なら KKT は十分条件 = 大域最適"]

数式の直観的意味

なぜ「勾配＝制約勾配の線形結合」なのか。無制約なら最適点で $-\nabla f=0$ （下げる力ゼロ）。制約があると、下げる力 $-\nabla f$ がまだ残っていても、それが実行可能領域の外を向いていれば動けない。「外を向く力」は効いている制約の法線 $\nabla g_i$ の非負結合で表せる（凸錐）。だから $-\nabla f = \sum \lambda_i \nabla g_i$ （ $\lambda_i \ge 0$ ）が成り立つ。相補性 $\lambda_i g_i = 0$ は「効いていない制約（ $g_i<0$ ）の乗数はゼロ」を意味する。乗数 $\lambda_i$ は後に 影の価格（感度分析）として経済的意味を持つ。

⚠️ よくある誤解・落とし穴

停留点＝最適ではない。鞍点・極大も $\nabla f=0$ を満たす。2次条件で必ず確認する。
端点最適を見落とさない。制約境界（端点）では $\nabla f \ne 0$ でも最適があり得る。だから KKT が要る。
KKT は無条件に十分ではない。凸性＋制約想定が無いと、KKT 点が大域最適とは限らない。
ヘッセが半定値（境界ケース）のときは2次条件で判定不能。より高次の項を見る必要がある。