← 数理最適化 一覧

🎓 レベル：発展　|　重要度：B（標準）

📎 前提：シンプレックス法・線形計画の双対性　|　関連：ペナルティ法・障壁法

要点（BLUF）

• 内点法は、実行可能領域の 内部を通って最適に近づく（シンプレックスは頂点を辿る）。
• 対数バリア関数で境界に「壁」を作り、無制約に近い問題へ変換して解く。
• バリアの強さ $\mu$ を $0$ に近づけると解は 中心パスを辿って最適頂点へ。LP を 多項式時間で解ける。

概念 ── 頂点を通らずに最適へ

シンプレックス法（シンプレックス法）は凸多面体の角を渡り歩く。内点法は発想が逆で、領域の 真ん中を突っ切って最適点へ滑り込む。Karmarkar（1984）以降、大規模 LP や凸計画（凸最適化 章目次）の主力になった。

対数バリア関数

不等式制約 $g_i(x) \le 0$ を目的に織り込む。境界に近づくと急激に大きくなる 対数バリアを足す：

$-g_i(x) > 0$（領域内部）でのみ定義され、境界 $g_i \to 0$ で $\ln \to -\infty$、すなわちバリア項 $\to +\infty$。だから最小化する解は 内部に押し込まれる。$\mu > 0$ はバリアの強さ。

中心パスと収束

各 $\mu$ に対しバリア問題の解 $x(\mu)$ が定まる。$\mu$ を大きくすると領域の「重心」付近、$\mu \to 0$ にすると元の LP の最適頂点へ近づく。この軌跡 $\{x(\mu)\}$ を 中心パス（central path） という。

graph LR
  A["大きな mu: 領域の中心付近"] --> B["mu を徐々に小さく"]
  B --> C["中心パスを辿る"]
  C --> D["mu -> 0: 最適頂点へ収束"]

内点法は $\mu$ を段階的に下げながら、各段でニュートン法（ニュートン法・準ニュートン法）的に1〜数歩進む。理論的には反復ごとに双対ギャップが一定割合で縮み、$O(\sqrt{n}\,\log(1/\epsilon))$ 反復で精度 $\epsilon$ に達する ── 多項式時間保証。

バリア問題の最適性条件＝摂動 KKT

バリア問題の停留条件を書くと、元の LP の KKT 条件（最適性条件の地図）の 相補性 $\lambda_i g_i = 0$ が、$\lambda_i (-g_i) = \mu$ という 緩めた相補性に置き換わる。$\mu \to 0$ で本来の相補性に戻る。中心パスとは「相補性をどれだけ緩めるか（$\mu$）」をパラメータにした最適解の連続的な道、というのが数理的な正体。

Pythonで内点法を確認

scipy の linprog(method="highs-ipm") が内点法（HiGHS の IPM）。生産計画 LP をシンプレックスと内点法の両方で解き、同じ最適に達することを見る。

from scipy.optimize import linprog

c = [-40, -30]
A_ub = [[2, 1], [1, 1]]
b_ub = [120, 100]
bounds = [(0, None), (0, None)]

res_sx  = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method="highs-ds")   # シンプレックス
res_ipm = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method="highs-ipm")  # 内点法

print(f"シンプレックス: xA={res_sx.x[0]:.1f},  xB={res_sx.x[1]:.1f},  利益={-res_sx.fun:.1f}")
print(f"内点法        : xA={res_ipm.x[0]:.4f}, xB={res_ipm.x[1]:.4f}, 利益={-res_ipm.fun:.4f}")

実行結果：

シンプレックス: xA=20.0,  xB=80.0,  利益=3200.0
内点法        : xA=20.0000, xB=80.0000, 利益=3200.0000

両者とも同じ最適 $(20,80)$、利益 3200。違いは 経路：シンプレックスは頂点 $(0,0)\to(0,100)\to(20,80)$ と角を渡り、内点法は領域内部を滑って頂点 $(20,80)$ に収束する。最適解が辺・面で連続的（複数最適）なときは、内点法は中心パスの極限として相対的内部の解に収束する傾向がある点も実務的な違い。

シンプレックス vs 内点法

数式の直観的意味

対数バリアの効果は「制約を硬い壁から、近づくほど反発する柔らかい壁に変える」こと。これで境界付き問題を 実質的に無制約にし、滑らかなニュートン法が使えるようになる。$\mu$ はその壁の柔らかさで、徐々に硬く（$\mu\to0$）していくと、解は本来の角に押し付けられる。シンプレックスが「離散的に角を跳ぶ」のに対し、内点法は「連続的に中心パスを滑る」── 同じ最適へ向かう2つの幾何。バリア法の一般論は非線形でも使え、ペナルティ法・障壁法 で再登場する。

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

• 内点法は厳密な頂点解を返しにくい：内部から近づくため、純粋な基底解が要る用途（整数計画の分枝、分枝限定法）ではクロスオーバーで頂点に丸める。
• 初期点は領域内部でなければならない（厳密内点）。実行不能なら不可行内点法など工夫が要る。
• 多項式時間でも常に速いとは限らない：小規模・温かいスタート（再最適化）ではシンプレックスが有利。
• バリアパラメータ $\mu$ の下げ方が雑だと数値的に不安定。実装はステップ幅と中心化を慎重に制御する。

関連ノート

• 比較対象：シンプレックス法
• バリア法の一般論：ペナルティ法・障壁法
• 凸計画への展開：錐計画（SOCP・SDP）入門
• ニュートンステップ：ニュートン法・準ニュートン法
• 章のハブ：線形計画 章目次