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$ はラグランジュ乗数と呼ばれ、制約条件の感度を表す双対変数として解釈できます。
KKT残差へのニュートン
F(x,\lambda)=
\begin{pmatrix}
\nabla f(x)-J_g(x)^{\!\top}\lambda\\
g(x)
\end{pmatrix}
この残差にニュートン法を当てると、1ステップは次の対称不定のKKT線形系を解くことに等しくなります：
\begin{bmatrix}
\nabla_{xx}^2 \mathcal L(x,\lambda) & -J_g(x)^{\!\top}\\
J_g(x) & 0
\end{bmatrix}
\begin{bmatrix}\Delta x\\ \Delta\lambda\end{bmatrix}
=-
\begin{bmatrix}
\nabla f(x)-J_g(x)^{\!\top}\lambda\\
g(x)
\end{bmatrix}.
ここで $\nabla_{xx}^2 \mathcal L(x,\lambda)=\nabla^2 f(x)-\sum_{i=1}^m \lambda_i , \nabla^2 g_i(x)$、$J_g(x)=\frac{\partial g}{\partial x}$ です。数値的には LDL^T 分解や Schur 補行列で解くのが標準です。
この方法がうまくいく直感的な理由は、ラグランジアンの停留点が元の制約付き最適化問題の解と一致するためです。つまり：
- $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）}
実装では局所収束を安定化するためのグローバリゼーションが必要です：
- ラインサーチ（例：$\phi_1$）
- トラストリージョン
- フィルタ法
最適性条件（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_+$ は不等式制約に対するラグランジュ乗数を表します。
スラック導入とPDIPMのニュートン線形化
不等式 $h(x)\le0$ に対してスラック変数 $s\ge0$ を導入して $h(x)+s=0$ とします。KKT（原始‐双対‐相補性）は：
\begin{cases}
\nabla f(x) - J_g(x)^{\!\top}\lambda - J_h(x)^{\!\top}\mu = 0,\\
g(x)=0,\quad h(x)+s=0,\\
S\mu=0,\quad s\ge0,\ \mu\ge0,
\end{cases}
内点法（PDIPM）では相補性を $S\mu=\tau\mathbf 1$ に置き換え、残差にニュートンを当てると：
\begin{bmatrix}
\nabla_{xx}^2 \mathcal L & -J_g^{\!\top} & -J_h^{\!\top} & 0\\
J_g & 0 & 0 & 0\\
J_h & 0 & 0 & I\\
0 & 0 & S & M
\end{bmatrix}
\begin{bmatrix}\Delta x\\ \Delta\lambda\\ \Delta\mu\\ \Delta s\end{bmatrix}
=-
\begin{bmatrix}
r_{\mathrm{stat}}\\ r_g\\ r_h\\ S\mu-\tau\mathbf 1
\end{bmatrix},
ここで $S=\mathrm{diag}(s)$、$M=\mathrm{diag}(\mu)$、$r_{\mathrm{stat}}=\nabla f-J_g^{!\top}\lambda-J_h^{!\top}\mu$、$r_g=g$、$r_h=h+s$ です。$\Delta s$ を消去すると右下のブロックから対角行列 $D(\mu/s)=MS^{-1}$ が現れます。
KKT条件
KKT条件は、適切な制約想定（例：線形独立制約想定LICQ）の下で、局所的最適解が満たすべき一階の必要条件を与えます：
\begin{cases}
\nabla_x \mathcal{L}(x^*,\lambda^*,\mu^*) = 0 & \text{（停留点条件）} \\
g(x^*) = 0 & \text{（等式制約）} \\
h(x^*)+s^*=0,\ s^*\ge0,\ \mu^*\ge0 & \text{（不等式+スラック）} \\
S^*\mu^* = 0 & \text{（相補性条件）}
\end{cases}
ここで $s^=-h(x^)$ と置けば、従来の表現 $\mu^{T} h(x^)=0$ と同値になります。
実用的な解法（内点法）
内点法は、不等式制約付き最適化を解くために広く使われます。代表的な定式化は次の2つです：
- 原始バリア：
\min_x\ \ f(x)-\tau\sum_i \log(-h_i(x))\quad\text{s.t. } g(x)=0.
- 原始‐双対（PDIPM）：スラック $s$ と乗数 $\mu$ を持つKKTに対して、相補性を $S\mu=\tau\mathbf1$ としてニュートン反復を行う（$\tau$ は相補性にのみ現れる）。
補足：外点法について
内点法に対して、実行可能領域の外側から最適解に近づく手法を外点法と呼びます。代表的な例として罰金法があり、制約違反に対してペナルティ項を加えます：\mathcal{L}_{\rho}(x) = f(x) + \frac{\rho}{2}(\|g(x)\|^2 + \|\max(0,h(x))\|^2)ここで $\rho > 0$ は罰金パラメータです。内点法と異なり、実行可能性は最適化の過程で徐々に満たされていきます。
二次の十分条件（SOSC）
LICQ が成り立つとき、可行方向 $d$（$J_g(x)d=0$、アクティブ集合の接線条件を満たす）に対して
$$d^{\top}\nabla_{xx}^2\mathcal L(x,\lambda,\mu),d>0$$
であれば、その点は局所極小です。