無制約最適化｜数理最適化

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：最適性条件の地図　|　関連：ニュートン法・準ニュートン法

要点（BLUF）

無制約最適化は 勾配 $\nabla f=0$ を満たす停留点を探す（最適性条件の地図）。
最急降下法：最も急に下る方向 $-\nabla f$ に、ステップ幅 $\alpha$ だけ進むのを繰り返す。
収束の速さは 条件数（関数の「歪み」）に強く依存し、谷が細長いと遅い。

概念 ── 「下る」を繰り返す

連続で微分可能な $f$ を制約なしで最小化する。各点で「どちらに動けば一番速く下がるか」は 負の勾配方向 $-\nabla f(x)$ 。そこへ少し進んで、また勾配を測って進む ── これが反復降下法の骨格。

x_{k+1} = x_k - \alpha_k \nabla f(x_k)

$\alpha_k > 0$ は ステップ幅（学習率）。勾配が「下る向きの羅針盤」、ステップ幅が「一歩の大きさ」。

なぜ $-\nabla f$ が最急降下方向か

点 $x$ で方向 $d$ （単位ベクトル）に動いたときの1次の変化は $\nabla f(x)^\top d$ 。これを最小（最も負）にする $d$ はコーシー・シュワルツより $d = -\nabla f/\|\nabla f\|$ 。つまり負の勾配が、その点で最も急に関数を下げる方向。 $\nabla f(x_k)=0$ になれば停留点に到達し、（凸なら）大域最適（局所最適と大域最適・凸性の役割）。

ステップ幅の選び方

固定ステップ：簡単だが、大きすぎると発散（行き過ぎて振動）、小さすぎると遅い。
直線探索（line search）：各反復で $\min_\alpha f(x_k - \alpha \nabla f(x_k))$ を（近似的に）解く。Armijo 条件などで「十分下がる $\alpha$ 」を選ぶ。
凸で勾配が $L$ -リプシッツなら $\alpha \le 1/L$ で収束保証。

Pythonで収束を見る

$f(x,y)=(x-3)^2 + 10(y-1)^2$ 。 $y$ 方向の曲率が10倍きつい（細長い谷）。最急降下で最小 $(3,1)$ に近づくが、ステップ幅は $y$ 方向の発散を避けるため小さくせざるを得ず、 $x$ 方向の進みが遅い。

import numpy as np

def f(p):    return (p[0]-3)**2 + 10*(p[1]-1)**2
def grad(p): return np.array([2*(p[0]-3), 20*(p[1]-1)])

x = np.array([0.0, 0.0])
lr = 0.05                      # 固定ステップ幅
for k in range(1, 41):
    x = x - lr * grad(x)       # x <- x - alpha * grad
    if k in (1, 5, 10, 20, 40):
        print(f"反復{k:>2}: x=({x[0]:.4f}, {x[1]:.4f}), f={f(x):.6f}")

実行結果：

反復 1: x=(0.3000, 1.0000), f=7.290000
反復 5: x=(1.2285, 1.0000), f=3.138106
反復10: x=(1.9540, 1.0000), f=1.094190
反復20: x=(2.6353, 1.0000), f=0.133028
反復40: x=(2.9557, 1.0000), f=0.001966

$y$ は1歩で最適 $y=1$ に乗る（曲率がきついので $20(y-1)$ の勾配が大きく、 $lr=0.05$ でちょうど収まる）が、 $x$ は40反復かけてやっと $2.96$ 。細長い谷では、きつい方向に合わせてステップを絞ると緩い方向が遅々として進まない。この条件数の悪さが最急降下の弱点で、2次情報を使うニュートン法（ニュートン法・準ニュートン法）が効く理由になる。

数式の直観的意味

最急降下が遅くなるのは「勾配が最短の道（最小点への直線）を指さない」から。等高線が同心円なら勾配は中心を指すが、細長い楕円だと勾配は谷の壁にほぼ垂直で、谷底に沿う成分が小さい。だからジグザグに進む。速さは ヘッセ行列の条件数（最大固有値÷最小固有値）で決まり、条件数 $\kappa$ のとき収束係数はおよそ $(\kappa-1)/(\kappa+1)$ 。 $\kappa$ が大きい（歪んだ谷）ほど1に近づき、進みが鈍る。前処理（変数スケーリング）やニュートン法は、この $\kappa$ を実効的に1に近づける工夫といえる。なお勾配法は機械学習の学習で主役になるが、その文脈（確率的勾配降下・Adam）は学習側で扱う。

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

ステップ幅が大きすぎると発散。下る方向でも、行き過ぎれば反対側の壁を駆け上がる。
勾配ゼロ＝最小ではない：鞍点・極大も停留点（最適性条件の地図）。非凸では初期点依存（局所最適と大域最適・凸性の役割）。
条件数が悪いと遅い：変数のスケールを揃える前処理が効く。
「収束した」は勾配ノルムが十分小さいことで判定。関数値だけ見ると停滞と収束を取り違える。