ペナルティ法・障壁法

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

📎 前提：不等式制約とKKT条件　|　関連：内点法入門

要点（BLUF）

ペナルティ法・障壁法は 制約を目的関数へ織り込み、無制約問題に変換して解く。
ペナルティ法：制約違反に罰金を課す。罰則 $\mu \to \infty$ で解が外側から実行可能領域へ収束。
障壁法：境界に壁を作り、内部から近づく。 $\mu \to 0$ で解が境界へ収束（内点法の原理、内点法入門）。

概念 ── 制約を「罰」に変える

制約付き問題は KKT（不等式制約とKKT条件）で解けるが、無制約最適化（無制約最適化・ニュートン法・準ニュートン法）の道具がそのまま使えると便利。そこで制約を 目的に足し込んで無制約化する。足し方が「外から」か「内から」かで2系統に分かれる。

ペナルティ法（外点法）

制約 $g_i(x)\le0$ の 違反量に罰金を課す。二次ペナルティの例：

P_\mu(x) = f(x) + \mu \sum_i \max\bigl(0,\ g_i(x)\bigr)^2

実行可能（ $g_i\le0$ ）なら罰金ゼロ、違反すると罰金が増える。 $\mu$ を大きくするほど違反が割に合わなくなり、最小化解は 実行可能領域の外側から境界へ近づく。 $\mu \to \infty$ で元問題の解に収束。

障壁法（内点法）

逆に、境界に近づくと急増する 障壁（バリア） を内部に張る。対数障壁：

B_\mu(x) = f(x) - \mu \sum_i \ln\bigl(-g_i(x)\bigr)

$-g_i(x)>0$ （領域内部）でのみ定義され、境界 $g_i\to0$ で $\to+\infty$ 。だから解は 内部に留まり、 $\mu\to0$ で境界の最適へ。これが内点法（内点法入門）そのもの。ペナルティが外から、障壁が内から境界に迫る対の関係。

graph LR
  A["制約付き min f s.t. g<=0"] --> B["ペナルティ: f + mu*違反^2 (外から)"]
  A --> C["障壁: f - mu*ln(-g) (内から)"]
  B --> D["mu -> 無限大 で境界へ収束"]
  C --> E["mu -> 0 で境界へ収束"]

Pythonでペナルティ法を見る

$\min x^2$ s.t. $x \ge 1$ （最適は境界 $x=1$ 、最適値1）。二次ペナルティ $x^2 + \mu(1-x)_+^2$ の停留点は、違反領域 $x<1$ で $2x - 2\mu(1-x)=0$ すなわち $x^\star = \mu/(1+\mu)$ 。 $\mu$ を強めると $x^\star \to 1$ 。

print("min x^2 s.t. x>=1  (最適 x=1)")
print("ペナルティ f(x)=x^2 + mu*max(0,1-x)^2 の停留点 x*=mu/(1+mu)")
for mu in [1, 10, 100, 1000]:
    x_star = mu / (1 + mu)           # 違反側の停留点
    print(f"  mu={mu:>4}: x*={x_star:.4f}  (制約境界1へ外側=1未満から接近)")

実行結果：

min x^2 s.t. x>=1  (最適 x=1)
ペナルティ f(x)=x^2 + mu*max(0,1-x)^2 の停留点 x*=mu/(1+mu)
  mu=   1: x*=0.5000  (制約境界1へ外側=1未満から接近)
  mu=  10: x*=0.9091  (制約境界1へ外側=1未満から接近)
  mu= 100: x*=0.9901  (制約境界1へ外側=1未満から接近)
  mu=1000: x*=0.9990  (制約境界1へ外側=1未満から接近)

罰則 $\mu$ を $1\to1000$ と強めると、解は $0.5 \to 0.909 \to 0.990 \to 0.999$ と 実行不能側（ $x<1$ ）から境界 $x=1$ へ収束。有限の $\mu$ では厳密には実行可能にならない（少し違反が残る）のがペナルティ法（外点法）の性質。これを嫌う場面では障壁法（常に実行可能）や 拡張ラグランジュ法を使う。

拡張ラグランジュ法（補足）

単純ペナルティは $\mu\to\infty$ が必要で、大きな $\mu$ は 数値的に不安定（ヘッセの条件数が悪化）。**拡張ラグランジュ法（ALM）**はペナルティにラグランジュ乗数項を加え、 $\mu$ を有限に保ったまま乗数を更新して厳密な実行可能解へ収束させる。実務の制約付きソルバーの主力の一つ。

数式の直観的意味

ペナルティ法と障壁法は、KKT 条件（不等式制約とKKT条件）を「連続変形」で近似していると見ると本質が見える。障壁問題の停留条件を書くと、相補性 $\lambda_i g_i=0$ が $\lambda_i(-g_i)=\mu$ に緩み、 $\mu\to0$ で本来の相補性に戻る ── つまり $\mu$ は「相補性をどれだけ緩めるか」のパラメータで、その解の軌跡が 中心パス（内点法入門）。ペナルティ法も同様に、 $\mu\to\infty$ の極限で乗数 $\lambda_i = 2\mu \max(0,g_i)$ が KKT 乗数に収束する。だから両手法は「難しい制約を、解きやすい無制約問題の列で挟み込み、極限で真の最適へ」という緩和の思想（整数計画とは・LP緩和とも通じる）の連続版。

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

単純ペナルティは厳密な実行可能解を返さない（有限 $\mu$ では違反が残る）。厳密さが要るなら障壁法か拡張ラグランジュ法。
$\mu$ を最初から極端に大きく/小さくしない：条件数が悪化して無制約ソルバーが不安定に。段階的に強める。
障壁法は初期点が領域内部でないと始められない（厳密内点）。
ペナルティの形（二次・絶対値）で性質が変わる。絶対値ペナルティ（ $\ell_1$ ）は有限 $\mu$ で厳密になり得る（exact penalty）が非平滑。