制約 (数学)

制約（せいやく、制約条件、せいやくじょうけん、英: Constraint）とは、数学の最適化問題において解が満たさなければならない条件を指す。制約にはいくつか種類が存在し、主に等式、不等式、整数制約が多用されている。与えられたすべての制約を満たす許容解の集合を実行可能集合という^[1]。

例

以下の最適化問題を例に挙げる:

\min f(\mathbf {x} )=x_{1}^{2}+x_{2}^{4}

subject to

x_{1}\geq 1

and

x_{2}=1,

ここで $\mathbf {x}$ はベクトル (x₁, x₂) を表す。

この問題では、最初の行に記されている関数が最小となる解を求める（これは目的関数、または損失関数、費用関数と呼ばれる。）。2つ目および3つ目の行は制約を表し、一つ目の制約を不等式制約と呼び、二つ目の制約は等式制約と呼ばれる。これら二つの制約は、この問題において解が絶対に制約を満たさなければならないという意味でハード制約（英語版）に分類される。

この問題に制約がない場合は、目的関数 $f(\mathbf {x} )$ が最小となる解は $(0,0)$ である。しかしこの解は制約を満たしていない。2つの制約を考慮した制約付き最適化（英語版）問題としての解は、 $\mathbf {x} =(1,1)$ のとき、2つの制約を満たしつつ目的関数 $f(\mathbf {x} )$ を最も小さくする解である。

用語

最適点において不等式制約について等号が成り立つ場合、その制約は束縛制約である。これは、目的関数の値を改善される方向に移動しようとしても、束縛制約によって最適点以上に改善する点が存在しないことを意味する。
一方、最適点において不等式制約が厳密に不等式として成り立つ場合（等号が成り立たない場合）、その制約は束縛制約でない。これは、束縛制約でない制約の方向に変動させることが可能であることを意味するが、最適性の観点からはその変更が望ましくない。凸最適化の場合では、ある制約が束縛制約でなければ、その制約が存在しなくても最適解の決定に起因しない。
その点がすべての制約を満たすものでない場合、実行不能である。

ハード制約・ソフト制約

最適化問題において制約の違反が許されない場合、これらの制約はハード制約と呼ばれる。しかし、問題によってはすべての制約を必ずしも満たす必要はなく、可能な限り満たすことが望ましいが必須ではない制約を設けることがある。このような制約をソフト制約（英語版）と呼び、それらを扱う問題はフレキシブル制約充足問題（flexible constraint satisfaction problem）と呼ばれる。ソフト制約を用いる問題として、preference-based planning の分野が挙げられる。最大制約充足問題（英語版）では、いくつかの制約の違反を許容し、評価尺度として満たされた制約の数を評価する。