ISEGORIA / 数学百科事典
最適化：最良の選択の幾何
降下法・条件数・制約・影の価格を調べます。
前提知識: 微分・ベクトル・行列
予想してから操作し、計算例と問いで理解を確かめてください。グラフは数式の図示であり、証明ではありません。
1. 勾配降下法と条件数
楕円の等高線を横切る一定刻みの勾配降下法を、ドラッグできる始点から追います。各座標は毎回それぞれの倍率で掛けられるので、曲率の差が大きいと刻みを小さくせざるを得ず、速い方向ではジグザグになります。右図は f を対数目盛で示し、反復は ρ で決まる傾きの直線に沿って減ります。破線のニュートン法の厳密な1ステップは、この二次関数の最小点に一度で達します。
計算例. κ = 4 のとき、一定刻みの勾配降下法は 0 < η < 0.5 で収束し、η = 2/(1 + κ) = 0.4 で最速の ρ = 0.6 になります。
注意点. 1ステップで収束する性質は、可逆なヘッセ行列を持つ二次関数に特有です。一般には保証されません。
刻み幅を大きくすると悪化することがあるのはなぜですか？
更新の倍率の絶対値が1を超え、誤差を増幅するためです。
2. 動く制約
制約の直線 x + y = b を x² + y² の同心円の上でドラッグし、直線上の試験点を動かします。最適点は、到達できる最小の円が直線にちょうど接する点です。他の点はより大きな円の上にあることが右図から分かります。不等式 x + y ≥ b に切り替えると、原点が実行可能なとき制約が効かなくなる様子が見られます。
計算例. b=2 の最適点は (1,1)、目的関数値は2です。
注意点. これは等式制約です。不等式に変えると実行可能領域や最適点が変わることがあります。
最適点で x と y が等しくなるのはなぜですか？
x²+y²=b²/2+(x-y)²/2 なので、x=y で最小になります。
3. 乗数と感度
左図は最適値 \(f_*(b)=b^2/2\) とその接線で、傾きが乗数 \(\lambda_*\) です。右図は、各 \(\lambda\) についてラグランジアンを最小化して得る双対関数 \(g(\lambda)\) です。g は \(f_*\) を超えず（弱双対性）、\(\lambda=b\) での最大値はちょうど \(f_*\) に一致します。左で b、右で λ をドラッグできます。
計算例. b=2 で b を0.01増やすと、最適値は約0.02増えます。
注意点. 乗数の符号は制約の書き方に依存します。感度は局所的な近似です。
λ=b の双対ギャップはいくつですか？
0です。主問題の最小値も双対問題の最大値も b²/2 です。