查看“︁約束 (數學)”︁的源代码

{{noteTA
|G1=Math
|1=zh-tw:;zh-cn:;
}}

在[[數學]]中，'''約束'''（{{lang-en|Constraint}}）是一個[[最佳化]]問題的解需要符合的條件。約束可分為等式约束及不等式约束。符合所有約束的解的集合稱為[[可行集]]（feasible set）或是候選解（candidate solution）。

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

:<math>\min f(\mathbf x) = x_1^2+x_2^4 </math>

其拘束條件為

:<math> x_1 \ge 1 </math>

and

:<math> x_2 = 1, \, </math>

其中 <math>\mathbf x</math> 表示[[向量]] (''x''<sub>1</sub>, ''x''<sub>2</sub>)。

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

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

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

==硬約束以及軟約束==

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

== 全域約束 ==
全域約束（Global constraints）<ref>{{Cite book|title=Handbook of constraint programming|last1=Rossi|first1=Francesca|last2=Van Beek|first2=Peter|last3=Walsh|first3=Toby|date=2006|publisher=Elsevier|isbn=9780080463643|edition=1st|location=Amsterdam|chapter=7|oclc=162587579}}</ref>是將所有變數一起考慮的約束。像其中一個全域約束是<code>alldifferent</code>，可以用較簡單的語言寫成一連串原子約束的組合：''n''個變數的<code>alldifferent</code>約束，若將所有變數二二比較，都不相等，約束即成立。在語意上等價於以下許多不等式的交集：<math>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</math>。也有其他的全域約束，全域約束的出現擴展了約束架構可以可表達的範圍。在這些例子中，全域約束常會對應一種特殊組合問題的結構。例如[[确定有限状态自动机]]可以接受<code>Regular</code>（{{link-en|正則約束|Regular constraint}}）的約束。

全域約束有用在<ref>{{Cite book|title=Principles and Practice of Constraint Programming CP 2003 00 : 9th International Conference, CP 2003, Kinsale, Ireland, September 29 October 3, 2003. Proceedings|date=2003|publisher=Springer-Verlag Berlin Heidelberg|last=Rossi|first=Francesca|isbn=9783540451938|location=Berlin|oclc=771185146}}</ref>簡化[[約束滿足問題]]的建模，擴展了約束語言的表示範圍、也可以促進[[约束编程]]。將所有變數一起考慮，可以在求解過程比較早發現一些不可行的情形。

== 相關條目 ==
* {{link-en|約束幾何|Constraint algebra}}
* [[卡羅需－庫恩－塔克條件]]
* [[拉格朗日乘數]]
* [[水平集]]
* [[线性规划]]
* [[非线性规划]]
* [[限制 (數學)]]
* {{link-en|可滿足性模理論|Satisfiability modulo theories}}

== 外部連結 ==
*[https://web.archive.org/web/20090217084003/http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html Nonlinear programming FAQ]
*[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary] {{Wayback|url=http://glossary.computing.society.informs.org/ |date=20100328165516 }}

[[Category:數學最佳化]]

[[ca:Restricció]]