制約条件

決定変数が満たさなければならない条件。 これが実行可能領域を決める。

$$g_i(x)\le 0(\text{不等式制約}),h_j(x)=0(\text{等式制約})$$

扱い方は 3 通り#

制約付きの問題を解くとき、実際には次のどれかを選ぶ。

1. ペナルティ法 — 制約を破った分だけ目的関数に罰を足し、制約なし問題に変える。 実装が簡単で、QUBO 化ではこれが標準。 罰の重みが小さいと制約を破り、大きいと探索が硬くなる。
2. 射影法 — 更新のたびに実行可能領域へ引き戻す。領域が単純（箱型など）なら有効。
3. 双対を使う — ラグランジュ未定乗数法で 制約を目的関数に組み込み、KKT 条件で最適性を特徴づける。

変数の型も制約#

$x_i\in \{0,1\}$ のような条件も制約の一種で、これが入ると問題は 整数計画になり、一般に NP 困難になる。 連続緩和して解いてから丸める、という近似がよく使われる。

参考文献#

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