可行方向法 可行方向法是求解约束优化问题的一类重要迭代算法，其核心思想是在每一步迭代中，沿着一个既能改善目标函数值又不会违反约束的方向进行搜索。 基本概念与问题背景 约束优化问题 ：考虑一般形式的非线性规划问题：min f(x)，满足约束条件 g_ i(x) ≤ 0 (i=1,...,m) 和 h_ j(x) = 0 (j=1,...,p)。其中，x 是决策向量，f(x) 是目标函数，g_ i(x) 是不等式约束，h_ j(x) 是等式约束。 可行域 ：所有满足约束条件的点 x 的集合，记为 S。可行方向法的迭代点序列 {x_ k} 必须始终保持在可行域 S 内。 可行方向 ：在某个可行点 x 处，如果一个方向 d 满足：存在一个标量 δ > 0，使得对于所有步长 α ∈ (0, δ ]，新点 x + αd 仍然在可行域 S 内，那么方向 d 就被称为在点 x 处的可行方向。 下降方向 ：在点 x 处，如果一个方向 d 满足目标函数 f(x) 在该方向上的方向导数小于零，即 ∇f(x)^T d < 0，那么沿着方向 d 移动，目标函数值在初始时刻是下降的，d 被称为下降方向。 核心思想与算法框架 目标 ：可行方向法的目标是找到一个方向，它既是可行的（保证迭代点不违反约束），又是下降的（保证目标函数值得以改进）。 通用迭代格式 ： 初始化 ：选择一个初始可行点 x_ 0 ∈ S。设置迭代计数器 k = 0。 搜索方向计算 ：在当前迭代点 x_ k 处，求解一个子问题（例如，一个线性规划或二次规划问题），寻找一个可行的下降方向 d_ k。这个子问题的解需要满足： ∇f(x_ k)^T d_ k < 0 （下降性） 对于在 x_ k 处起作用的约束（即 g_ i(x_ k)=0 的约束），有 ∇g_ i(x_ k)^T d_ k ≤ 0 （可行性，防止立即违反这些紧约束） 对于等式约束 h_ j(x_ k)=0，有 ∇h_ j(x_ k)^T d_ k = 0 （可行性，保证始终在等式约束面上） 如果找不到这样的方向 d_ k（或者 d_ k 的模足够小），则当前点 x_ k 满足某种最优性条件（如 KKT 条件），算法终止。 步长选取 ：沿着方向 d_ k 进行一维搜索，确定一个步长 α_ k > 0。步长 α_ k 需要满足： x_ k + α_ k d_ k ∈ S （可行性） f(x_ k + α_ k d_ k) < f(x_ k) （函数值下降） 迭代更新 ：令 x_ {k+1} = x_ k + α_ k d_ k。 设置 k = k+1，返回步骤 2。 Zoutendijk 可行方向法 这是可行方向法中一个经典且重要的代表。 线性化思想 ：在当前点 x_ k，将目标函数和起作用的不等式约束进行线性近似（一阶泰勒展开）。寻找方向 d 的问题转化为一个线性规划问题。 方向寻找子问题 （一种常见形式）： min η s.t. ∇f(x_ k)^T d ≤ η ∇g_ i(x_ k)^T d ≤ η, 对于所有在 x_ k 处起作用的约束 g_ i ∇h_ j(x_ k)^T d = 0, 对于所有等式约束 h_ j -1 ≤ d_ l ≤ 1, l=1,...,n （规范化约束，防止方向 d 无限大） 这里 η 是一个辅助变量。如果求得的最优值 η < 0，则意味着我们找到了一个方向 d，使得目标函数和所有起作用约束在方向 d 上的变化率（近似值）都小于一个负数 η，从而保证了 d 是一个可行的下降方向。如果 η = 0，则说明当前点可能是一个稳定点（满足 KKT 条件）。 收敛性 ：在一定的约束规格（如约束函数可微、可行域非空等）下，Zoutendijk 法产生的序列的聚点满足 KKT 必要条件。 算法特点与应用 优点 ： 直观性强，物理意义明确：始终在可行域内移动，中间迭代解也是可行的，这在许多实际应用中非常重要（例如，迭代过程中方案必须可实施）。 对于线性约束问题非常有效。 缺点与挑战 ： “锯齿”现象 (Zigzagging) ：当迭代点接近约束边界时，算法可能在一些约束边界上来回振荡，导致收敛速度变慢。 约束规格 ：算法的收敛性依赖于约束规格（如线性无关约束规格LICQ）的满足。如果不满足，可能无法找到正确的搜索方向。 对于非线性约束 ，保证严格的可行性有时比较困难，步长选择需要小心处理。 与其他方法的关系 ：可行方向法是解决约束优化问题的一大类方法。投影梯度法可以看作是一种特殊的可行方向法，它通过将负梯度方向投影到可行域的切空间上来构造可行下降方向。序列二次规划 (SQP) 方法在思想上也与可行方向法有联系，它通过求解二次规划子问题来产生搜索方向。