約束 (數學)

在數學中，約束（英語：Constraint）是一個最佳化問題的解需要符合的條件。約束可分為等式約束及不等式約束。符合所有約束的解的集合稱為可行集（feasible set）或是候選解（candidate solution）。

範例

以下是一個最佳化的問題：

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

其拘束條件為

$x_{1}\geq 1$

and

$x_{2}=1,\,$

其中 $\mathbf {x}$ 表示向量 (x₁, x₂)。

上例中，第一行定義要最佳化的函數（稱為目標或費用函數），第二、三行定義二個約束條件，一個是不等式約束，另一個是等式約束，這二個約束定義了候選解的範圍。

若沒有約束條件，最佳化的解為$(0,0)\,$，因此處的$f(\mathbf {x} )$有最小值，但這個值不符合約束條件。考慮約束條件的最佳化問題，其解為$\mathbf {x} =(1,1)$，是符合所有約束條件的解當中，使函數有最小值的解。

術語

• 若一約束條件在特定點時為一等式，稱為束縛約束，因為此點無法在約束的方向自由移動，就算往該方方向可能會讓目標函數有更好的結束，也無法移動。
• 若一約束條件在特定點時為一不等式，稱為非束縛約束，因為此點仍可以在約束的方向自由移動（不過有可能是因為移動後對目標函數沒有好的影響，因此不移動）。
• 若在特定點下，約束條件中有至少一個無法滿足，此點就稱為不可行。

硬約束以及軟約束

若問題中有要求所有的約束都要符合，這稱為「硬約束」（hard constraints），上述所提的都是硬約束。另外有一種約束問題，稱為flexible constraint satisfaction problems。有些約束希望可以滿足，但不強制。這類非強制的約束稱為軟約束，例如preference-based planning。在MAX-CSP的約束滿足問題問題中，可以允許違反一定數量的約束，會依滿足約束的數量來評估解的品質。

全域約束

全域約束（Global constraints）是將所有變數一起考慮的約束。像其中一個全域約束是alldifferent，可以用較簡單的語言寫成一連串原子約束的組合：n個變數的alldifferent約束，若將所有變數二二比較，都不相等，約束即成立。在語意上等價於以下許多不等式的交集：$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（正則約束）的約束。

全域約束有用在簡化約束滿足問題的建模，擴展了約束語言的表示範圍、也可以促進約束編程。將所有變數一起考慮，可以在求解過程比較早發現一些不可行的情形。

相關條目

• 約束幾何
• 卡羅需－庫恩－塔克條件
• 拉格朗日乘數
• 水平集
• 線性規劃
• 非線性規劃
• 限制 (數學)
• 可滿足性模理論

外部連結

• Nonlinear programming FAQ
• Mathematical Programming Glossary （頁面存檔備份，存於網際網路檔案館）