1. ニュートン法
目的関数 $f: \mathbb{R}^n \to \mathbb{R}$ の最小化を考えます：
\text{minimize} \quad f(x), \quad x \in \mathbb{R}^n
ニュートン法による更新式：
dx = -[\nabla^2 f(x)]^{-1} \nabla f(x)
ここで、$\nabla f(x) \in \mathbb{R}^n$ は勾配、$\nabla^2 f(x) \in \mathbb{R}^{n \times n}$ はヘッセ行列を表します。
2. 等式制約付き最適化
問題設定
\begin{align*}
\text{minimize} & \quad f(x), \quad x \in \mathbb{R}^n \\
\text{subject to} & \quad g(x) = 0, \quad g: \mathbb{R}^n \to \mathbb{R}^m
\end{align*}
ラグランジアンの導入
\mathcal{L}: \mathbb{R}^n \times \mathbb{R}^m \to \mathbb{R}, \quad \mathcal{L}(x,\lambda) = f(x) - \lambda^T g(x)
ラグランジアンは、制約条件を目的関数に組み込むことで、制約付き最適化問題を取り扱いやすい形に変換します。$\lambda$ はラグランジュ乗数と呼ばれ、制約条件の感度を表す双対変数として解釈できます。
拡大系でのニュートン法
変数 $p = (x^T, \lambda^T)^T \in \mathbb{R}^{n+m}$ として：
dp = -[\nabla^2 \mathcal{L}(p)]^{-1} \nabla \mathcal{L}(p)
ここで、勾配とヘッセ行列の具体的な形は：
\nabla \mathcal{L}(p) =
\begin{pmatrix}
\frac{\partial \mathcal{L}}{\partial x} \\
g(x)
\end{pmatrix}, \quad
\nabla^2 \mathcal{L}(p) =
\begin{pmatrix}
\frac{\partial^2 \mathcal{L}}{\partial x^2} & -\frac{\partial g}{\partial x}^T \\
\frac{\partial g}{\partial x} & 0
\end{pmatrix}
これは通常のニュートン法の更新式と完全に同じ構造になります。
この方法がうまくいく直感的な理由は、ラグランジアンの停留点が元の制約付き最適化問題の解と一致するためです。つまり：
- $x$ に関する勾配がゼロ → 目的関数の最適性条件
- $\lambda$ に関する勾配がゼロ → 制約条件の充足
ただし、実際の数値計算では、ラグランジアンの停留点を見つけることは必ずしも容易ではありません。そこでmerit functionという考え方が重要になります：
\phi(x, \lambda) = \|\nabla_x \mathcal{L}(x,\lambda)\|^2 + \|g(x)\|^2
このmerit functionは：
- 目的関数の最適性（第1項）と制約条件の充足（第2項）を同時に評価
- $\phi(x, \lambda) = 0$ となる点が、元の問題の局所的最適解の候補
- 各反復でのステップ長の決定に利用可能
特に、非線形最適化問題では、ラグランジアン自体を進行度の測定に使用できない理由があります：
- 最適解でのラグランジアンの値が事前にわからない（現在値より大きくも小さくもなり得る）
- 中間段階で実行不可能な解が生成される可能性がある
そのため、目的関数と制約条件の両方を考慮したmerit functionが必要になります。代表的なものとして：
\phi_1(x, \mu) = f(x) + \mu \|g(x)\|_1 \quad \text{（l1 merit function）}
\phi_2(x, \mu) = f(x) + \mu \|g(x)\|_2 \quad \text{（l2 merit function）}
最適性条件（KKT条件）
KKT（Karush-Kuhn-Tucker）条件は、適切な制約想定（正則性条件）の下で、非線形最適化問題における局所的最適解の必要条件を与える定理です。等式制約付き最適化問題の場合、以下のように表されます：
\begin{cases}
\frac{\partial \mathcal{L}}{\partial x} = \frac{\partial f}{\partial x} - \lambda^T \frac{\partial g}{\partial x} = 0 & \text{（停留点条件）}
g(x) = 0 & \text{（実行可能性条件）}
\end{cases}
これらの条件は、最適解が満たすべき必要条件となります。第1式は目的関数の勾配と制約条件の勾配が平行であることを示し、第2式は制約を満たすことを要求します。この条件は、William Karush、Harold W. Kuhn、Albert W. Tuckerによって研究され、彼らの名を取ってKKT条件と呼ばれています。
3. 不等式制約付き最適化
問題設定
\begin{align*}
\text{minimize} & \quad f(x) \\
\text{subject to} & \quad g(x) = 0 \\
& \quad h(x) \leq 0
\end{align*}
拡張ラグランジアン
\mathcal{L}(x,\lambda,\mu) = f(x) - \lambda^T g(x) - \mu^T h(x)
ここで、$\lambda \in \mathbb{R}^m$ は等式制約に対するラグランジュ乗数、$\mu \in \mathbb{R}^p_+$ は不等式制約に対するラグランジュ乗数を表します。
拡大系での表現
変数 $p = (x^T, \lambda^T, \mu^T)^T$ として、更新式は：
dp = -[\nabla^2 \mathcal{L}(p)]^{-1} \nabla \mathcal{L}(p)
ここで、勾配とヘッセ行列の具体的な形は：
\nabla \mathcal{L}(p) =
\begin{pmatrix}
\nabla_x \mathcal{L} \\
-g(x) \\
-h(x)
\end{pmatrix}, \quad
\nabla^2 \mathcal{L}(p) =
\begin{pmatrix}
\nabla^2_{xx} \mathcal{L} & -\nabla g(x)^T & -\nabla h(x)^T \\
\nabla g(x) & 0 & 0 \\
\nabla h(x) & 0 & D(\mu/h(x))
\end{pmatrix}
ただし、$D(\mu/h(x))$ は対角行列であり、その $(i,i)$ 成分は $\mu_i/h_i(x)$ です。この行列は内点法における障壁項から導出されます。
KKT条件
KKT条件は、適切な制約想定（例：線形独立制約想定LICQ）の下で、局所的最適解が満たすべき一階の必要条件を与えます：
\begin{cases}
\nabla_x \mathcal{L}(x^*,\lambda^*,\mu^*) = 0 & \text{（停留点条件）} \\
g(x^*) = 0 & \text{（等式制約）} \\
h(x^*) \leq 0 & \text{（不等式制約）} \\
\mu^* \geq 0 & \text{（双対実行可能性）} \\
\mu^{*T} h(x^*) = 0 & \text{（相補性条件）}
\end{cases}
相補性条件は、各不等式制約について以下のいずれかが成り立つことを要求します：
- 制約が非有効（$h_i(x^) < 0$）ならば、対応する乗数は零（$\mu^_i = 0$）
- 制約が有効（$h_i(x^) = 0$）ならば、対応する乗数は非負（$\mu^_i \geq 0$）
実用的な解法（内点法）
内点法は、不等式制約付き最適化問題を解くための効率的なアルゴリズムです。その特徴は、実行可能領域の内部（内点）を通りながら最適解に近づいていく点にあります。
代表的な手法として、対数バリア法があります。これは不等式制約 $h(x) \leq 0$ の境界付近で発散する対数バリア関数を目的関数に加えることで、以下のような修正された問題を解きます：
\mathcal{L}_{\tau}(x,\lambda,\mu) = f(x) - \lambda^T g(x) - \mu^T h(x) - \tau \sum_{i=1}^m \log(-h_i(x))
ここで：
- $\tau > 0$ はバリアパラメータ
- $m$ は不等式制約の数
- $\log(-h_i(x))$ は制約境界 $h_i(x) = 0$ に近づくと発散する項
この手法が「内点法」と呼ばれる理由は、$\log(-h_i(x))$ の発散性により、常に実行可能領域の内部に解が保たれるためです。アルゴリズムは $\tau$ を徐々に小さくしながら反復を進め、最終的に元の問題の解に収束します。
補足：外点法について
内点法に対して、実行可能領域の外側から最適解に近づく手法を外点法と呼びます。代表的な例として罰金法があり、制約違反に対してペナルティ項を加えます：\mathcal{L}_{\rho}(x) = f(x) + \frac{\rho}{2}(\|g(x)\|^2 + \|\max(0,h(x))\|^2)ここで $\rho > 0$ は罰金パラメータです。内点法と異なり、実行可能性は最適化の過程で徐々に満たされていきます。