约束优化问题的积极集方法 约束优化问题的积极集方法是一种用于求解具有不等式约束的非线性优化问题的数值算法。其核心思想是通过识别在最优解处起作用的约束（即积极约束），将原问题转化为一个等式约束问题来迭代求解。 基本概念：积极约束 在约束优化问题中，不等式约束在最优解处可能有两种状态： 积极约束 ：在最优解处，约束取等号（即 g_ i(x* ) = 0）。这些约束像“墙壁”一样限制了变量的移动。 非积极约束 ：在最优解处，约束取严格不等号（即 g_ i(x* ) < 0）。这些约束在最优解附近不直接影响目标函数的优化。 方法原理：序列等式约束子问题 积极集方法通过迭代过程逐步估计积极约束集，并在每一步求解一个等式约束子问题： 在当前迭代点 x_ k，根据约束函数值和 Lagrange 乘子的估计，预测一个积极约束集 W_ k（称为工作集）。 将工作集 W_ k 中的不等式约束视为等式约束，而忽略非积极约束，形成一个等式约束优化子问题。 求解该子问题，得到搜索方向 d_ k 和新的 Lagrange 乘子估计。 沿搜索方向进行线搜索，确保新迭代点可行，并更新工作集 W_ k。 关键机制：工作集的管理 工作集 W_ k 的更新是算法的核心，通常遵循以下规则： 添加约束 ：当迭代点移动到某个非积极约束的边界时，将该约束加入工作集。 删除约束 ：当某个约束对应的 Lagrange 乘子估计为负时（表明该约束可能不是真正的积极约束），将其从工作集中移除。 算法步骤详解 初始化 ：给定一个初始可行点 x_ 0 和初始工作集 W_ 0（通常包含在 x_ 0 处积极的约束）。 子问题构造 ：在当前点 x_ k，将工作集 W_ k 中的约束视为等式，构造子问题： min f(x) s.t. g_ i(x) = 0, i ∈ W_ k 求解子问题 ：计算子问题的搜索方向 d_ k（例如，通过求解一个等式约束的二次规划子问题）。 线搜索 ：沿 d_ k 方向进行线搜索，确定步长 α_ k，使得新点 x_ {k+1} = x_ k + α_ k d_ k 满足所有约束，且目标函数充分下降。 工作集更新 ： 如果线搜索遇到新的约束边界，将该约束加入 W_ k。 检查乘子符号，移除乘子为负的约束。 收敛判断 ：检查当前点是否满足 KKT 条件。若满足，停止；否则返回步骤 2。 应用与特点 积极集方法特别适用于求解中等规模的约束优化问题，其中积极约束的数量不多。 在二次规划中，该方法非常有效，因为子问题是简单的等式约束二次规划。 对于非线性问题，该方法通常与序列二次规划结合使用。 通过识别和管理积极约束集，该方法将复杂的不等式约束问题转化为一系列更简单的等式约束问题，逐步逼近最优解。