非线性规划中的可行方向法（Feasible Direction Methods in Nonlinear Programming）
字数 4334 2025-12-20 00:42:39

非线性规划中的可行方向法（Feasible Direction Methods in Nonlinear Programming）

可行方向法是一类用于求解非线性规划问题的迭代算法。其核心思想是：在每次迭代中，从当前可行点出发，沿着一个能同时改进目标函数值并保持可行性的方向移动，从而逐步逼近问题的最优解。我们循序渐进地理解它。

第一步：问题形式与基本思路

考虑一个标准的约束优化问题：

\[\begin{aligned} \min \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \le 0, \quad i = 1, \ldots, m \\ & h_j(x) = 0, \quad j = 1, \ldots, p \\ & x \in \mathbb{R}^n \end{aligned} \]

其中，\(f, g_i, h_j\) 是连续可微函数。设问题的可行域为 \(S = \{ x \mid g_i(x) \le 0, h_j(x)=0 \}\)。

对于一个可行点 \(x_k \in S\)，我们想找到下一个点 \(x_{k+1} = x_k + \alpha_k d_k\)，其中 \(\alpha_k > 0\) 是步长，\(d_k\) 是搜索方向。为了使迭代有意义，方向 \(d_k\) 需要满足两个基本要求：

  1. 可行方向：存在 \(\bar{\alpha} > 0\)，使得对于所有 \(\alpha \in (0, \bar{\alpha})\)，都有 \(x_k + \alpha d_k \in S\)。这意味着沿此方向作微小移动不会离开可行域。
  2. 下降方向：满足 \(\nabla f(x_k)^\top d_k < 0\)，即目标函数值在此方向上能立即减少。

如果一个方向 \(d_k\) 同时满足这两个条件，就称其为可行下降方向。可行方向法的基本框架就是：在每一步，找到一个可行下降方向，然后沿此方向进行一维搜索（确定步长 \(\alpha_k\)），得到新的迭代点。

第二步：如何刻画可行方向？—— 线性化与可行锥

在迭代点 \(x_k\)，约束的可行性由其一阶近似（线性化）来控制。我们定义在 \(x_k\) 处的积极约束集 \(I_k = \{ i \mid g_i(x_k)=0 \}\)。对于一个可行点，所有等式约束 \(h_j(x_k)=0\) 自然总是积极的。

对于不等式约束 \(g_i(x) \le 0\)：

  • 如果 \(i \in I_k\)（\(g_i(x_k)=0\)），为了保持可行性，移动方向 \(d\) 必须满足 \(\nabla g_i(x_k)^\top d \le 0\)。这意味着不能“向内”违反约束（即 \(g_i(x_k + \alpha d) > 0\)）。
  • 如果 \(i \notin I_k\)（\(g_i(x_k) < 0\)），由于约束有余量，只要步长 \(\alpha\) 足够小，\(g_i(x_k + \alpha d)\) 依然会 \(\le 0\)。因此，非积极约束在局部不限制方向 \(d\) 的选择。

对于等式约束 \(h_j(x)=0\)，必须满足 \(\nabla h_j(x_k)^\top d = 0\)，以保证一阶近似下仍满足等式。

由此，我们可以定义在 \(x_k\) 处的线性化可行方向锥 \(F_k\)：

\[F_k = \{ d \mid \nabla g_i(x_k)^\top d \le 0, \forall i \in I_k; \quad \nabla h_j(x_k)^\top d = 0, \forall j \} \]

满足 \(d \in F_k\) 是方向 \(d\) 在 \(x_k\) 点成为可行方向的一阶必要条件（在合适的约束规格下，这也是充分条件）。

第三步：如何构造搜索方向？—— 核心子问题

给定当前点 \(x_k\)，我们希望找到一个方向 \(d\)，它既属于可行方向锥 \(F_k\)，又是一个下降方向（\(\nabla f(x_k)^\top d < 0\)）。这可以表述为求解一个线性规划或二次规划子问题来寻找“最优”的可行下降方向。

一个经典而重要的方法是Zoutendijk可行方向法。其核心是求解如下方向寻找子问题：

\[\begin{aligned} \min \quad & \nabla f(x_k)^\top d \\ \text{s.t.} \quad & \nabla g_i(x_k)^\top d \le 0, \quad i \in I_k \\ & \nabla h_j(x_k)^\top d = 0, \quad j = 1, \ldots, p \\ & \|d\|_\infty \le 1 \quad \text{（或其它范数有界约束，保证问题有界）} \end{aligned} \]

子问题的直观解释：

  • 目标 \(\min \nabla f(x_k)^\top d\)：由于 \(\nabla f(x_k)^\top d\) 是 \(f\) 在 \(d\) 方向的方向导数，我们希望它尽可能小（即负得最多），以最大化局部下降率。
  • 约束 \(\nabla g_i(x_k)^\top d \le 0\) 和 \(\nabla h_j(x_k)^\top d = 0\)：确保 \(d\) 属于线性化可行方向锥 \(F_k\)。
  • 约束 \(\|d\|_\infty \le 1\)：这是一个规范化约束，防止目标值趋向负无穷（例如，如果 \(d\) 是可行下降方向，取 \(Md\) 会让目标值变为 \(M \nabla f(x_k)^\top d\)，当 \(M \to \infty\) 时目标趋向 \(-\infty\)）。它将搜索限制在一个有界集内，从而得到有限的最优解。

设子问题的最优解为 \(d_k\)，最优值为 \(\theta_k = \nabla f(x_k)^\top d_k\)。

第四步：最优性检验与算法步骤

求解方向子问题后，我们得到 \(\theta_k\)。它的值至关重要，是判断当前点 \(x_k\) 是否满足一阶最优性条件（即是否可能是局部极小点）的关键。

  • 如果 \(\theta_k < 0\)：说明找到了一个可行下降方向 \(d_k\)（因为 \(\nabla f(x_k)^\top d_k = \theta_k < 0\)，且 \(d_k\) 满足线性化可行约束）。此时，我们可以沿 \(d_k\) 进行一维搜索（线搜索），求步长 \(\alpha_k\)，使得新点 \(x_{k+1} = x_k + \alpha_k d_k\) 可行且目标函数 \(f\) 充分下降。
  • 如果 \(\theta_k = 0\)：说明在 \(x_k\) 点，不存在任何一个线性化可行方向能使得目标函数下降（即，对于所有满足线性化可行约束的 \(d\)，都有 \(\nabla f(x_k)^\top d \ge 0\)）。在合适的约束规格（如MFCQ）下，这恰好等价于KKT条件成立。因此，当 \(\theta_k = 0\) 时，算法可以终止，\(x_k\) 被认为是一个稳定点（可能是局部极小点）。

Zoutendijk可行方向法的基本步骤：

  1. 初始化：选取一个初始可行点 \(x_0 \in S\)，令 \(k=0\)。
  2. 确定积极集：在当前点 \(x_k\)，确定积极不等式约束集 \(I_k = \{ i \mid g_i(x_k)=0 \}\)。
  3. 求解方向子问题：求解上述线性规划子问题，得到最优方向 \(d_k\) 和最优值 \(\theta_k\)。
  4. 收敛性检验：如果 \(|\theta_k|\) 足够小（接近0），则停止迭代，输出 \(x_k\) 作为近似最优解。
  5. 线搜索：若 \(\theta_k < 0\)，沿方向 \(d_k\) 进行一维线搜索，确定步长 \(\alpha_k > 0\)，使得 \(x_{k+1} = x_k + \alpha_k d_k \in S\) 且 \(f(x_{k+1}) < f(x_k)\)。线搜索通常需要保证可行性，可能采用“最大可行步长”或“Armijo型”搜索。
  6. 更新：令 \(k = k+1\)，返回步骤2。

第五步：方法的特点、扩展与意义

  • 几何直观：该方法有很强的几何意义。每一步都是在当前点，用约束的切平面（或半空间）来近似可行域，然后在这个局部近似多面体内找一个最速下降方向。
  • 与KKT条件的关系：算法终止准则 \(\theta_k=0\) 本质上是KKT条件的另一种表达。方向子问题的对偶变量，在 \(\theta_k=0\) 时，恰好可以构造出满足KKT条件的拉格朗日乘子。
  • 约束规格的重要性：算法的收敛性分析（即证明算法产生的稳定点满足KKT条件）依赖于约束规格。常用的如Mangasarian-Fromovitz约束规格（MFCQ） 能保证 \(\theta_k=0\) 时，KKT条件必然成立。
  • 主要变体：
  • Topkis-Veinott法：将方向子问题中的不等式约束 \(\nabla g_i(x_k)^\top d \le 0\) 修改为 \(\nabla g_i(x_k)^\top d + \beta \eta \le 0\)，并增加约束 \(\nabla f(x_k)^\top d \le -\eta\)，其中 \(\eta\) 是一个变量，\(\beta > 0\) 是参数。这样做的好处是能保证每次迭代都能找到一个“严格可行”的下降方向，并放宽了对初始点严格满足约束的要求（允许从可行域内部开始）。
    • 梯度投影法：可以看作是可行方向法的一个特例，它将负梯度投影到线性化可行锥上得到搜索方向，特别适用于简单约束（如变量边界约束）。
  • 优点与局限：
    • 优点：概念清晰，几何直观，能直接处理非线性约束，且每一步迭代只需求解一个线性规划（或简单的二次规划），计算相对容易。
  • 局限：收敛速度通常是线性的，可能较慢。对于高度非线性的约束，线性近似可能很粗糙，导致可行步长非常小，算法进展缓慢（“锯齿现象”）。此外，确定精确的积极约束集 \(I_k\) 在数值上可能敏感。

总之，可行方向法是非线性优化中一类基础且重要的算法。它将复杂的非线性约束优化问题，转化为一系列利用局部一阶信息的、易于求解的线性子问题，为理解约束优化的一阶最优性条件和设计迭代算法提供了经典的范本。

非线性规划中的可行方向法（Feasible Direction Methods in Nonlinear Programming） 可行方向法是一类用于求解 非线性规划 问题的迭代算法。其核心思想是：在每次迭代中，从当前可行点出发，沿着一个能同时 改进目标函数值 并 保持可行性 的方向移动，从而逐步逼近问题的最优解。我们循序渐进地理解它。 第一步：问题形式与基本思路 考虑一个标准的约束优化问题： $$ \begin{aligned} \min \quad & f(x) \\ \text{s.t.} \quad & g_ i(x) \le 0, \quad i = 1, \ldots, m \\ & h_ j(x) = 0, \quad j = 1, \ldots, p \\ & x \in \mathbb{R}^n \end{aligned} $$ 其中，$f, g_ i, h_ j$ 是连续可微函数。设问题的可行域为 $S = \{ x \mid g_ i(x) \le 0, h_ j(x)=0 \}$。 对于一个可行点 $x_ k \in S$，我们想找到下一个点 $x_ {k+1} = x_ k + \alpha_ k d_ k$，其中 $\alpha_ k > 0$ 是步长，$d_ k$ 是搜索方向。为了使迭代有意义，方向 $d_ k$ 需要满足两个基本要求： 可行方向 ：存在 $\bar{\alpha} > 0$，使得对于所有 $\alpha \in (0, \bar{\alpha})$，都有 $x_ k + \alpha d_ k \in S$。这意味着沿此方向作微小移动不会离开可行域。 下降方向 ：满足 $\nabla f(x_ k)^\top d_ k < 0$，即目标函数值在此方向上能立即减少。 如果一个方向 $d_ k$ 同时满足这两个条件，就称其为 可行下降方向 。可行方向法的基本框架就是：在每一步，找到一个可行下降方向，然后沿此方向进行一维搜索（确定步长 $\alpha_ k$），得到新的迭代点。 第二步：如何刻画可行方向？—— 线性化与可行锥 在迭代点 $x_ k$，约束的可行性由其一阶近似（线性化）来控制。我们定义在 $x_ k$ 处的 积极约束集 $I_ k = \{ i \mid g_ i(x_ k)=0 \}$。对于一个可行点，所有等式约束 $h_ j(x_ k)=0$ 自然总是积极的。 对于不等式约束 $g_ i(x) \le 0$： 如果 $i \in I_ k$（$g_ i(x_ k)=0$），为了保持可行性，移动方向 $d$ 必须满足 $\nabla g_ i(x_ k)^\top d \le 0$。这意味着不能“向内”违反约束（即 $g_ i(x_ k + \alpha d) > 0$）。 如果 $i \notin I_ k$（$g_ i(x_ k) < 0$），由于约束有余量，只要步长 $\alpha$ 足够小，$g_ i(x_ k + \alpha d)$ 依然会 $\le 0$。因此，非积极约束在局部不限制方向 $d$ 的选择。 对于等式约束 $h_ j(x)=0$，必须满足 $\nabla h_ j(x_ k)^\top d = 0$，以保证一阶近似下仍满足等式。 由此，我们可以定义在 $x_ k$ 处的 线性化可行方向锥 $F_ k$： $$ F_ k = \{ d \mid \nabla g_ i(x_ k)^\top d \le 0, \forall i \in I_ k; \quad \nabla h_ j(x_ k)^\top d = 0, \forall j \} $$ 满足 $d \in F_ k$ 是方向 $d$ 在 $x_ k$ 点成为可行方向的 一阶必要条件 （在合适的约束规格下，这也是充分条件）。 第三步：如何构造搜索方向？—— 核心子问题 给定当前点 $x_ k$，我们希望找到一个方向 $d$，它既属于可行方向锥 $F_ k$，又是一个下降方向（$\nabla f(x_ k)^\top d < 0$）。这可以表述为求解一个 线性规划 或 二次规划 子问题来寻找“最优”的可行下降方向。 一个经典而重要的方法是 Zoutendijk可行方向法 。其核心是求解如下方向寻找子问题： $$ \begin{aligned} \min \quad & \nabla f(x_ k)^\top d \\ \text{s.t.} \quad & \nabla g_ i(x_ k)^\top d \le 0, \quad i \in I_ k \\ & \nabla h_ j(x_ k)^\top d = 0, \quad j = 1, \ldots, p \\ & \|d\|_ \infty \le 1 \quad \text{（或其它范数有界约束，保证问题有界）} \end{aligned} $$ 子问题的直观解释 ： 目标 $\min \nabla f(x_ k)^\top d$：由于 $\nabla f(x_ k)^\top d$ 是 $f$ 在 $d$ 方向的方向导数，我们希望它尽可能小（即负得最多），以最大化局部下降率。 约束 $\nabla g_ i(x_ k)^\top d \le 0$ 和 $\nabla h_ j(x_ k)^\top d = 0$：确保 $d$ 属于线性化可行方向锥 $F_ k$。 约束 $\|d\|_ \infty \le 1$：这是一个规范化约束，防止目标值趋向负无穷（例如，如果 $d$ 是可行下降方向，取 $Md$ 会让目标值变为 $M \nabla f(x_ k)^\top d$，当 $M \to \infty$ 时目标趋向 $-\infty$）。它将搜索限制在一个有界集内，从而得到有限的最优解。 设子问题的最优解为 $d_ k$，最优值为 $\theta_ k = \nabla f(x_ k)^\top d_ k$。 第四步：最优性检验与算法步骤 求解方向子问题后，我们得到 $\theta_ k$。它的值至关重要，是判断当前点 $x_ k$ 是否满足一阶最优性条件（即是否可能是局部极小点）的关键。 如果 $\theta_ k < 0$ ：说明找到了一个可行下降方向 $d_ k$（因为 $\nabla f(x_ k)^\top d_ k = \theta_ k < 0$，且 $d_ k$ 满足线性化可行约束）。此时，我们可以沿 $d_ k$ 进行一维搜索（线搜索），求步长 $\alpha_ k$，使得新点 $x_ {k+1} = x_ k + \alpha_ k d_ k$ 可行且目标函数 $f$ 充分下降。 如果 $\theta_ k = 0$ ：说明在 $x_ k$ 点，不存在任何一个线性化可行方向能使得目标函数下降（即，对于所有满足线性化可行约束的 $d$，都有 $\nabla f(x_ k)^\top d \ge 0$）。在合适的约束规格（如MFCQ）下，这恰好等价于 KKT条件 成立。因此，当 $\theta_ k = 0$ 时，算法可以终止，$x_ k$ 被认为是一个稳定点（可能是局部极小点）。 Zoutendijk可行方向法的基本步骤 ： 初始化 ：选取一个初始可行点 $x_ 0 \in S$，令 $k=0$。 确定积极集 ：在当前点 $x_ k$，确定积极不等式约束集 $I_ k = \{ i \mid g_ i(x_ k)=0 \}$。 求解方向子问题 ：求解上述线性规划子问题，得到最优方向 $d_ k$ 和最优值 $\theta_ k$。 收敛性检验 ：如果 $|\theta_ k|$ 足够小（接近0），则停止迭代，输出 $x_ k$ 作为近似最优解。 线搜索 ：若 $\theta_ k < 0$，沿方向 $d_ k$ 进行一维线搜索，确定步长 $\alpha_ k > 0$，使得 $x_ {k+1} = x_ k + \alpha_ k d_ k \in S$ 且 $f(x_ {k+1}) < f(x_ k)$。线搜索通常需要保证 可行性 ，可能采用“最大可行步长”或“Armijo型”搜索。 更新 ：令 $k = k+1$，返回步骤2。 第五步：方法的特点、扩展与意义 几何直观 ：该方法有很强的几何意义。每一步都是在当前点，用约束的切平面（或半空间）来近似可行域，然后在这个局部近似多面体内找一个最速下降方向。 与KKT条件的关系 ：算法终止准则 $\theta_ k=0$ 本质上是KKT条件的另一种表达。方向子问题的对偶变量，在 $\theta_ k=0$ 时，恰好可以构造出满足KKT条件的拉格朗日乘子。 约束规格的重要性 ：算法的收敛性分析（即证明算法产生的稳定点满足KKT条件）依赖于约束规格。常用的如 Mangasarian-Fromovitz约束规格（MFCQ） 能保证 $\theta_ k=0$ 时，KKT条件必然成立。 主要变体 ： Topkis-Veinott法 ：将方向子问题中的不等式约束 $\nabla g_ i(x_ k)^\top d \le 0$ 修改为 $\nabla g_ i(x_ k)^\top d + \beta \eta \le 0$，并增加约束 $\nabla f(x_ k)^\top d \le -\eta$，其中 $\eta$ 是一个变量，$\beta > 0$ 是参数。这样做的好处是能保证每次迭代都能找到一个“严格可行”的下降方向，并放宽了对初始点严格满足约束的要求（允许从可行域内部开始）。 梯度投影法 ：可以看作是可行方向法的一个特例，它将负梯度投影到线性化可行锥上得到搜索方向，特别适用于简单约束（如变量边界约束）。 优点与局限 ： 优点：概念清晰，几何直观，能直接处理非线性约束，且每一步迭代只需求解一个线性规划（或简单的二次规划），计算相对容易。 局限：收敛速度通常是线性的，可能较慢。对于高度非线性的约束，线性近似可能很粗糙，导致可行步长非常小，算法进展缓慢（“锯齿现象”）。此外，确定精确的积极约束集 $I_ k$ 在数值上可能敏感。 总之，可行方向法是非线性优化中一类基础且重要的算法。它将复杂的非线性约束优化问题，转化为一系列利用局部一阶信息的、易于求解的线性子问题，为理解约束优化的一阶最优性条件和设计迭代算法提供了经典的范本。