约束 (数学)

在数学中，约束（英语：Constraint）是一个优化问题的解需要符合的条件。约束可分为等式约束及不等式约束。符合所有约束的解的集合称为可行集（feasible set）或是候选解（candidate solution）。

范例

以下是一个优化的问题：

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

其拘束条件为

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

and

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

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

上例中，第一行定义要优化的函数（称为目标或费用函数），第二、三行定义二个约束条件，一个是不等式约束，另一个是等式约束，这二个约束定义了候选解的范围。

若没有约束条件，优化的解为${\displaystyle (0,0)\,}$，因此处的${\displaystyle f(\mathbf {x} )}$有最小值，但这个值不符合约束条件。考虑约束条件的优化问题，其解为${\displaystyle \mathbf {x} =(1,1)}$，是符合所有约束条件的解当中，使函数有最小值的解。

术语

• 若一约束条件在特定点时为一等式，称为束缚约束，因为此点无法在约束的方向自由移动，就算往该方方向可能会让目标函数有更好的结束，也无法移动。
• 若一约束条件在特定点时为一不等式，称为非束缚约束，因为此点仍可以在约束的方向自由移动（不过有可能是因为移动后对目标函数没有好的影响，因此不移动）。
• 若在特定点下，约束条件中有至少一个无法满足，此点就称为不可行。

硬约束以及软约束

若问题中有要求所有的约束都要符合，这称为“硬约束”（hard constraints），上述所提的都是硬约束。另外有一种约束问题，称为flexible constraint satisfaction problems。有些约束希望可以满足，但不强制。这类非强制的约束称为软约束（英语：Constraint optimization），例如preference-based planning（英语：preference-based planning）。在MAX-CSP的约束满足问题问题中，可以允许违反一定数量的约束，会依满足约束的数量来评估解的品质。

全域约束

全域约束（Global constraints）^[1]是将所有变量一起考虑的约束。像其中一个全域约束是alldifferent，可以用较简单的语言写成一连串原子约束的组合：n个变量的alldifferent约束，若将所有变量二二比较，都不相等，约束即成立。在语意上等价于以下许多不等式的交集：${\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（正则约束（英语：Regular constraint））的约束。

全域约束有用在^[2]简化约束满足问题的建模，扩展了约束语言的表示范围、也可以促进约束编程。将所有变量一起考虑，可以在求解过程比较早发现一些不可行的情形。

相关条目

• 约束几何（英语：Constraint algebra）
• 卡罗需－库恩－塔克条件
• 拉格朗日乘数
• 水平集
• 线性规划
• 非线性规划
• 限制 (数学)
• 可满足性模理论（英语：Satisfiability modulo theories）