可行集

在数学优化中，可行集是满足所有约束且属于指定定义域的决策变量取值所组成的集合。其元素称为可行点或可行解。可行集描述哪些取值是允许的，而目标函数则决定如何评价这些取值的优劣。可行点不一定是最优点：最优性还要求该点在所有允许的取值中达到最佳的目标函数值。(stanford.edu)

数学定义

考虑如下问题：

其中，$x$ 是决策变量向量，$f$ 是目标函数，$D$ 指定变量的基本取值域。可行集为

定义域还必须满足使各函数有定义所需的限制。因此，如果某个函数在给定点处无定义，仅满足上述不等式并不足以使该点成为可行点。(stanford.edu)

在有限维连续优化中，$D$ 通常是实数向量空间 $\mathbb R^n$ 的子集。在整数规划中，则要求部分或全部坐标取整数值。即使其他代数约束完全相同，这一区别也会改变允许的取值点。(mit.edu)

可行集也可以等价地看作各个约束对应集合的交集。因此，增加约束只会缩小可行集或使其保持不变。冗余约束不会改变可行集，因为其余限制条件已经蕴含了这一约束。这些结论都可以直接从定义得出。(stanford.edu)

可行性与最优性

当 $F\neq\varnothing$ 时，问题是可行的；当 $F=\varnothing$ 时，问题是不可行的。可行性问题只要求找到 $F$ 中的一个元素，或判定这样的元素不存在。它可以表示为目标函数为常数的优化问题，因为此时所有可行点的目标函数值都相同。(docs.gurobi.com)

对于最小化问题，最优值为

只有当某个可行点确实达到这一值时，最优解 $x^\star$ 才存在。因此，必须区分三种不同的情况：约束相互矛盾、目标函数在可行集上无下界，以及下确界有限但无法达到。(stanford.edu)

可行集无界并不意味着目标函数无界。例如，在 $F=\mathbb R$ 上最小化 $x^2$，可以达到最小值 $0$。另一方面，在 $F=(0,1)$ 上最小化 $x$，其下确界为 $0$，却不存在最优解。这些例子说明，可行性、有界性以及最优值能否达到是不同的性质。(mit.edu)

几何与凸性

在线性规划中，可行集由仿射等式和不等式描述。非平凡的仿射等式定义一个超平面，仿射不等式则定义一个半空间。它们的有限交集是一个多面体，可能为空、有界、无界，或具有较低的维数。用矩阵记号表示，一种典型的描述为

这一表示将约束系统与其几何解释联系起来。(courses.csail.mit.edu)

凸集包含连接其中任意两点的整条线段。因此，可行集是凸集，当且仅当对任意 $x,y\in F$ 和 $0\leq\theta\leq1$，都有

这一表达式是一个凸组合。凸集的交集仍然是凸集，这也解释了多面体可行域为何具有凸性。(courses.csail.mit.edu)

更一般地，在凸定义域上施加由凸函数构成的不等式约束和由仿射函数构成的等式约束，所得可行集是凸集。如果目标函数也是凸函数，该问题就是凸优化问题。仅有可行集的凸性，并不足以保证整个优化问题具有凸性。(stanford.edu)

边界与解的存在性

对于不等式 $g_i(x)\leq0$，若在某个可行点处有 $g_i(x)=0$，则称该约束在该点处是起作用的；否则称其为不起作用的约束。起作用的约束表明哪些限制条件在该点处恰好取到等号。严格可行是指所有不等式约束都严格成立，同时等式约束仍然得到满足。(courses.csail.mit.edu)

不应将严格可行与在整个环境空间中具有非空内部混为一谈。例如，$x_1+x_2=1$ 与 $x_1,x_2\geq0$ 一起在 $\mathbb R^2$ 中定义了一条线段。两个坐标都为正的点严格满足这些不等式，但这条线段没有二维内部。其相对内部是在它的仿射包中定义的。(stanford.edu)

拓扑学性质对于最优值能否达到十分重要。最值定理保证，连续函数作为实值目标函数时，会在非空的紧空间可行集上达到最小值。在 $\mathbb R^n$ 中，紧性等价于闭且有界。这些是充分条件，而非必要条件：无界的可行集也可能包含最优解。(mit.edu)

松弛与数值可行性

松弛是用一个更大的集合 $R\supseteq F$ 替代 $F$。对于最小化问题，由于可供选择的取值更多，松弛问题的最优值不会超过原问题的最优值。去除整数性要求就是一个常见例子；松弛问题的解不一定满足原问题的约束。(underactuated.csail.mit.edu)

计算中的可行性不同于数学意义上严格属于可行集。采用浮点运算的求解器通常允许在指定容差范围内轻微违反约束。因此，求解器报告为可行的解，可能略微落在精确可行集之外。缩放和容差会影响这种数值解释，但不会改变可行集的抽象定义。(docs.gurobi.com)