可行域 可行域是指数学规划问题中所有满足约束条件的决策变量取值构成的集合。它是优化问题的解空间，决定了问题的性质和求解难度。 第一步：可行域的基本定义 在优化问题中，我们通常需要最小化（或最大化）目标函数 \( f(x) \)，同时满足一组约束条件。例如，对于问题： \[ \min f(x) \quad \text{s.t.} \quad x \in S \] 其中 \( S = \{ x \in \mathbb{R}^n \mid g_ i(x) \leq 0, \, h_ j(x) = 0 \} \) 称为可行域。\( g_ i(x) \leq 0 \) 为不等式约束，\( h_ j(x) = 0 \) 为等式约束。可行域中的点称为可行解。 第二步：可行域的几何特征 凸性 ：若所有约束函数为凸函数，等式约束为线性，则可行域是凸集（即任意两点连线仍在域内）。凸可行域的性质简化了优化问题（如凸规划）。 有界性 ：可行域可能有界（如多边形区域）或无界（如半平面）。有界域通常保证最优解存在。 空集与无解 ：若约束矛盾（如 \( x \leq 1 \) 且 \( x \geq 2 \)），可行域为空，问题无解。 第三步：可行域与算法设计的关系 边界与最优解 ：线性规划的最优解总出现在可行域顶点（单纯形法依据）；非线性规划中，解可能在边界或内部（如梯度为零的内点）。 约束处理 ：算法需在搜索过程中保持解的可行性。例如： 投影梯度法：将迭代点投影回可行域。 罚函数法：将约束 violation 加入目标函数，放松可行性要求。 复杂性影响 ：非凸可行域（如整数规划）可能包含离散点集，导致问题为 NP-难。 第四步：特殊可行域的实例分析 多面体 ：线性规划的可行域是凸多面体，由线性不等式定义。例如： \[ \{ x \in \mathbb{R}^2 \mid x_ 1 + x_ 2 \leq 1, \, x_ 1 \geq 0, \, x_ 2 \geq 0 \} \] 是一个三角形区域，顶点为 \((0,0), (1,0), (0,1)\)。 锥约束 ：二阶锥规划中可行域为 \( \{ x \mid \|Ax + b\|_ 2 \leq c^T x + d \} \)，形如冰淇淋锥。 流形约束 ：若等式约束定义光滑流形（如 \( \|x\|_ 2 = 1 \)），可行域是曲面，需微分几何工具处理。 第五步：可行域的退化与敏感性 退化 ：在单纯形法中，可行域顶点对应过多活跃约束时，可能引起算法循环。 参数扰动 ：若约束右端参数变化，可行域形状可能剧变（如从有界变无界），影响最优解稳定性（鲁棒优化关注此现象）。 冗余约束 ：某些约束不影响可行域形状，但增加计算负担，需预处理剔除。 可行域是连接问题建模与算法求解的核心桥梁，其结构直接决定了优化策略的选择与效率。