制約付き最適化 — 知識ノート

制約のある問題を、実際にどう解くか。

方針は 3 つ#

1. 制約を目的関数に取り込む

ペナルティ法は違反量を罰として足す。

\tilde{f} (x) = f (x) + ρ \sum_{i} \max {(0, g_{i} (x))}^{2}

実装は最も簡単で、QUBO 化では標準。 $ρ$ が小さいと制約を破り、大きいと数値的に悪条件になる。拡張ラグランジュ法は乗数を併用してこの綱引きを緩和する。

2. 実行可能領域に留める

射影法は更新のたびに領域へ引き戻す。箱型制約 $l \leq x \leq u$ のように射影が簡単な場合に有効。実行可能解を常に保てるので、途中で打ち切っても使える。

3. 最適性条件を直接解く

KKT 条件を連立方程式として扱い、 Newton 法系の手法で解く。内点法と SQP がこの系統。

制約が厳しいと、実行可能解を 1 つ見つけるだけで難問になる。このとき「制約違反量の最小化」を先に解く（フェーズ 1）という段取りを踏む。

Jorge Nocedal, Stephen J. Wright. Numerical Optimization, 2nd ed. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5
Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/