制約（数学）

数学において、制約とは、最適化問題の解が満たさなければならない条件のことです。制約にはいくつかの種類があり、主に等式制約、不等式制約、整数制約があります。すべての制約を満たす候補解の集合は、実行可能集合と呼ばれます。^{[ 1 ]}

以下は単純な最適化問題です。

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

対象

${\displaystyle x_{1}\geq 1}$

そして

${\displaystyle x_{2}=1,}$

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

この例では、最初の行で最小化すべき関数（目的関数、損失関数、またはコスト関数と呼ばれる）を定義しています。2行目と3行目では2つの制約を定義しており、1つ目は不等式制約、2つ目は等式制約です。これらの2つの制約は厳密な制約であり、満たされることが必須です。つまり、実行可能な候補解の集合を定義します。

制約がない場合、解は（0,0）となり、${\displaystyle f(\mathbf {x} )}$は最小値を持つ。しかし、この解は制約を満たさない。上記の制約付き最適化問題の解は${\displaystyle \mathbf {x} =(1,1)}$、これは の値が最小の点です${\displaystyle f(\mathbf {x} )}$これは2つの制約条件を満たしている。

• 不等式制約が最適点で等号を満たす場合、その制約は制約条件により、目的関数の値が改善される場合でも、制約の方向に点をことはできません
• 不等式制約が最適点において厳密な不等式として成り立つ場合（つまり、等式が成り立たない場合）、その制約は制約条件が非拘束的である場合、制約条件の方向に点ことは可能ですが、そうすることが最適解となるわけではありません。凸最適化などの特定の条件下では、制約条件が非拘束的であれば、その制約条件が存在しない場合でも最適化問題の解は同じになります。
• ある地点で制約条件が満たされない場合、その地点は実行不可能であると言われます。

問題が制約を満たすことを必須としている場合（上記の議論のように）、制約はハード制約と呼ばれることがあります。しかし、フレキシブル制約充足問題と呼ばれる問題では、特定の制約を満たすことが望ましいものの必須ではありません。このような必須ではない制約はソフト制約と呼ばれます。ソフト制約は、例えば、選好に基づく計画策定などで発生します。MAX -CSP問題では、いくつかの制約が違反されても許容され、解の質は満たされた制約の数によって評価されます。

グローバル制約^{[ 2 ]}は、複数の変数全体に対する特定の関係を表す制約です。alldifferent制約の中には、例えば、より単純な言語で原子制約の論理積として書き直すことができるものもあります。制約はn個の変数alldifferentに対して成り立ちます。${\displaystyle x_{1}...x_{n}}$、そして、変数が互いに異なる値をとる場合に満たされる。これは意味的に不等式の連言と同等である。${\displaystyle x_{1}\neq x_{2},x_{1}\neq x_{3}...,x_{2}\neq x_{3},x_{2}\neq x_{4}...x_{n-1}\neq x_{n}}$その他のグローバル制約は、制約フレームワークの表現力を拡張します。この場合、それらは通常、組み合わせ問題の典型的な構造を捉えます。たとえば、regular制約は、変数のシーケンスが決定性有限オートマトンによって受理されることを表します。

グローバル制約は、制約充足問題のモデリングを簡素化し、制約言語の表現力を拡張し、制約解決を改善するために使用されています^{[ 3 ]}。実際、変数をまとめて考慮することで、解決プロセスの早い段階で実行不可能な状況を把握できます。多くのグローバル制約は、オンラインカタログで参照されています。

• Beveridge, Gordon SG; Schechter, Robert S. (1970). 「最適化における本質的特徴」 .最適化：理論と実践. ニューヨーク：McGraw-Hill. pp. 5–8 . ISBN  0-07-005128-3。

• 非線形計画法に関するよくある質問（ 2019年10月30日時点のアーカイブ）
• 数理計画法用語集（2010年3月28日時点のアーカイブ）