凸集合

任意の 2 点を結ぶ線分が、集合の中に収まる集合。

$$x,y\in C,\theta \in [\mathrm{0,1}]⟹\theta x+(1-\theta )y\in C$$

「へこみが無い」形。

例#

凸	凸でない
球、直方体、半空間	三日月形、ドーナツ
超平面、半正定値行列の全体	球面（表面だけ）
線形制約の実行可能領域	整数格子点

演算で保たれるか#

演算	凸性
積集合 $C_1\cap C_2$	保たれる
和集合 $C_1\cup C_2$	保たれない
アフィン変換 $AC+b$	保たれる

積集合で保たれることが実用上重要。 複数の凸制約を課しても、実行可能領域は凸のまま。 だから制約を足しても問題の難易度が跳ね上がらない。

一方、和集合で保たれないことが 「A または B」という条件の扱いにくさに直結する。 論理和の制約は整数変数を要し、 整数計画になって NP 困難化する。

参考文献#

• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.（全文公開） https://web.stanford.edu/~boyd/cvxbook/
• Sheldon Axler. Linear Algebra Done Right, 4th ed. Springer, 2024.（全文公開） https://linear.axler.net/