可行方向法

字数 4058 2025-11-17 04:57:18

可行方向法

可行方向法是一类用于求解约束优化问题的迭代算法。其核心思想是：在每次迭代中，从当前可行点出发，沿着一个既能改善目标函数值、又能保持可行性的方向进行搜索。

基本概念与问题设定
首先，我们明确该方法要解决的问题。考虑一个带约束的非线性优化问题：

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

其中，\(f(\mathbf{x})\) 是目标函数，\(g_i(\mathbf{x})\) 是不等式约束，\(h_j(\mathbf{x})\) 是等式约束。所有满足约束的点的集合 \(S\) 称为可行域。可行方向法的目标是找到一个序列 \(\{\mathbf{x}^k\} \subset S\)，使得 \(f(\mathbf{x}^{k+1}) < f(\mathbf{x}^k)\)，并最终收敛到一个局部最优点。

可行方向与下降方向
算法的关键在于找到“可行下降方向”。

可行方向：在点 \(\mathbf{x} \in S\)，一个方向 \(\mathbf{d}\) 被称为可行方向，如果存在一个标量 \(\bar{\alpha} > 0\)，使得对于所有步长 \(\alpha \in (0, \bar{\alpha}]\)，都有 \(\mathbf{x} + \alpha \mathbf{d} \in S\)。这意味着从 \(\mathbf{x}\) 出发，沿着 \(\mathbf{d}\) 移动一个足够小的步长，不会违反任何约束。
下降方向：在点 \(\mathbf{x}\)，一个方向 \(\mathbf{d}\) 被称为下降方向，如果存在一个标量 \(\bar{\alpha} > 0\)，使得对于所有步长 \(\alpha \in (0, \bar{\alpha}]\)，都有 \(f(\mathbf{x} + \alpha \mathbf{d}) < f(\mathbf{x})\)。这意味着从 \(\mathbf{x}\) 出发，沿着 \(\mathbf{d}\) 移动一个足够小的步长，目标函数值会减小。

因此，一个理想的搜索方向 \(\mathbf{d}\) 必须同时是可行方向和下降方向。

可行下降方向的数学刻画
为了在算法中系统地寻找这样的方向，我们需要用数学条件来描述它。

下降条件的线性化：如果 \(f\) 在 \(\mathbf{x}\) 处可微，那么 \(\mathbf{d}\) 是下降方向的一个充分条件是 \(\nabla f(\mathbf{x})^\top \mathbf{d} < 0\)。这表示方向 \(\mathbf{d}\) 与负梯度方向（最速下降方向）的夹角小于90度。
可行条件的线性化：对于约束，我们通常考虑在 \(\mathbf{x}\) 处“起作用”的约束。对于不等式约束 \(g_i(\mathbf{x}) \leq 0\)，如果 \(g_i(\mathbf{x}) = 0\)，则该约束在 \(\mathbf{x}\) 处起作用。对于等式约束 \(h_j(\mathbf{x}) = 0\)，它们总是在 \(\mathbf{x}\) 处起作用。如果所有约束函数在 \(\mathbf{x}\) 处可微，那么 \(\mathbf{d}\) 是可行方向的一个必要条件是：

\[ \nabla g_i(\mathbf{x})^\top \mathbf{d} \leq 0 \quad \text{对于所有起作用的 } g_i \]

\[ \nabla h_j(\mathbf{x})^\top \mathbf{d} = 0 \quad \text{对于所有 } h_j \]

这些条件确保了沿着 \(\mathbf{d}\) 移动一个无穷小步长，不会立即违反任何起作用约束。

寻找可行下降方向的线性规划模型
基于上述线性化条件，一个常见的策略是通过求解一个辅助的线性规划（LP）或二次规划（QP）来寻找搜索方向 \(\mathbf{d}\)。
一个典型的模型是：

\[ \begin{align*} \min_{\mathbf{d}, \beta} \quad & \beta \\ \text{s.t.} \quad & \nabla f(\mathbf{x})^\top \mathbf{d} \leq \beta \\ & \nabla g_i(\mathbf{x})^\top \mathbf{d} \leq \beta, \quad \text{对于所有起作用的 } g_i \\ & \nabla h_j(\mathbf{x})^\top \mathbf{d} = 0, \quad \text{对于所有 } h_j \\ & \|\mathbf{d}\|_\infty \leq 1 \quad \text{(规范化约束，防止无界解)} \end{align*} \]

在这个模型中：

目标是最小化一个辅助变量 \(\beta\)。
第一个约束 \(\nabla f(\mathbf{x})^\top \mathbf{d} \leq \beta\) 与下降性相关。如果我们能找到 \(\mathbf{d}\) 使得 \(\beta < 0\)，那么就有 \(\nabla f(\mathbf{x})^\top \mathbf{d} \leq \beta < 0\)，即 \(\mathbf{d}\) 是下降方向。
第二组约束 \(\nabla g_i(\mathbf{x})^\top \mathbf{d} \leq \beta\) 保证了对于起作用的不等式约束，其线性化变化量不超过 \(\beta\)。如果 \(\beta < 0\)，则意味着 \(\nabla g_i(\mathbf{x})^\top \mathbf{d} < 0\)，这比可行性必要条件的 \(\leq 0\) 更严格，有助于在非线性约束下保持可行性。
- 第三组约束处理等式约束。
如果这个LP的最优值 \(\beta^* < 0\)，那么我们就找到了一个可行的下降方向 \(\mathbf{d}^*\)。如果 \(\beta^* = 0\)，则当前点 \(\mathbf{x}\) 通常满足某种形式的最优性条件（如一阶必要条件）。

线搜索与迭代过程
一旦找到了一个可行的下降方向 \(\mathbf{d}^k\)，下一步是确定步长 \(\alpha^k\)。

\[ \mathbf{x}^{k+1} = \mathbf{x}^k + \alpha^k \mathbf{d}^k \]

步长 \(\alpha^k\) 需要通过线搜索来确定，以确保：

可行性：\(\mathbf{x}^{k+1} \in S\)。
目标函数下降：\(f(\mathbf{x}^{k+1}) < f(\mathbf{x}^k)\)。
常用的线搜索方法是“Armijo型”可行方向搜索或“精确线搜索”在可行方向上的变体。由于约束的存在，步长选择需要额外小心，以避免“越界”。

算法框架与收敛性
综合以上步骤，可行方向法的基本框架如下：
初始化：选择一个初始可行点 \(\mathbf{x}^0 \in S\)，设定容忍度 \(\epsilon > 0\)，令 \(k = 0\)。
方向寻找：在当前点 \(\mathbf{x}^k\)，构造并求解方向寻找子问题（如步骤4中的LP）。设其解为 \((\mathbf{d}^k, \beta^k)\)。
收敛性检验：如果 \(|\beta^k| < \epsilon\)（或 \(\beta^k \ge 0\)），则算法停止，\(\mathbf{x}^k\) 被认为是一个近似驻点。否则，转到步骤4。
线搜索：沿着方向 \(\mathbf{d}^k\) 进行线搜索，找到一个步长 \(\alpha^k > 0\)，使得 \(\mathbf{x}^{k+1} = \mathbf{x}^k + \alpha^k \mathbf{d}^k \in S\) 且 \(f(\mathbf{x}^{k+1}) < f(\mathbf{x}^k)\)。
迭代：令 \(k = k+1\)，返回步骤2。

在适当的约束规格（如Mangasarian-Fromovitz约束规格）下，该算法产生的序列的极限点满足KKT一阶最优性条件。
方法特点与应用场景
- 优点：概念直观，对于线性约束问题尤其有效，因为线性约束的可行方向可以精确刻画。
- 缺点：对于非线性约束，由于线性化近似只在当前点的小邻域内有效，算法可能只能采取很小的步长，导致效率低下（“锯齿现象”）。此外，方向寻找子问题的求解本身也是一个优化问题，计算成本可能较高。
- 应用：它是许多更高级算法（如序列线性规划SLP、梯度投影法）的基础思想，在工程设计、经济均衡等具有复杂约束的优化问题中有其应用价值。

可行方向法可行方向法是一类用于求解约束优化问题的迭代算法。其核心思想是：在每次迭代中，从当前可行点出发，沿着一个既能改善目标函数值、又能保持可行性的方向进行搜索。基本概念与问题设定首先，我们明确该方法要解决的问题。考虑一个带约束的非线性优化问题： \[ \begin{align* } \min_ {\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_ i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m \\ & h_ j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \\ & \mathbf{x} \in \mathbb{R}^n \end{align* } \] 其中，\( f(\mathbf{x}) \) 是目标函数，\( g_ i(\mathbf{x}) \) 是不等式约束，\( h_ j(\mathbf{x}) \) 是等式约束。所有满足约束的点的集合 \( S \) 称为可行域。可行方向法的目标是找到一个序列 \( \{\mathbf{x}^k\} \subset S \)，使得 \( f(\mathbf{x}^{k+1}) < f(\mathbf{x}^k) \)，并最终收敛到一个局部最优点。可行方向与下降方向算法的关键在于找到“可行下降方向”。可行方向：在点 \( \mathbf{x} \in S \)，一个方向 \( \mathbf{d} \) 被称为可行方向，如果存在一个标量 \( \bar{\alpha} > 0 \)，使得对于所有步长 \( \alpha \in (0, \bar{\alpha} ] \)，都有 \( \mathbf{x} + \alpha \mathbf{d} \in S \)。这意味着从 \( \mathbf{x} \) 出发，沿着 \( \mathbf{d} \) 移动一个足够小的步长，不会违反任何约束。下降方向：在点 \( \mathbf{x} \)，一个方向 \( \mathbf{d} \) 被称为下降方向，如果存在一个标量 \( \bar{\alpha} > 0 \)，使得对于所有步长 \( \alpha \in (0, \bar{\alpha}] \)，都有 \( f(\mathbf{x} + \alpha \mathbf{d}) < f(\mathbf{x}) \)。这意味着从 \( \mathbf{x} \) 出发，沿着 \( \mathbf{d} \) 移动一个足够小的步长，目标函数值会减小。因此，一个理想的搜索方向 \( \mathbf{d} \) 必须同时是可行方向和下降方向。可行下降方向的数学刻画为了在算法中系统地寻找这样的方向，我们需要用数学条件来描述它。下降条件的线性化：如果 \( f \) 在 \( \mathbf{x} \) 处可微，那么 \( \mathbf{d} \) 是下降方向的一个充分条件是 \( \nabla f(\mathbf{x})^\top \mathbf{d} < 0 \)。这表示方向 \( \mathbf{d} \) 与负梯度方向（最速下降方向）的夹角小于90度。可行条件的线性化：对于约束，我们通常考虑在 \( \mathbf{x} \) 处“起作用”的约束。对于不等式约束 \( g_ i(\mathbf{x}) \leq 0 \)，如果 \( g_ i(\mathbf{x}) = 0 \)，则该约束在 \( \mathbf{x} \) 处起作用。对于等式约束 \( h_ j(\mathbf{x}) = 0 \)，它们总是在 \( \mathbf{x} \) 处起作用。如果所有约束函数在 \( \mathbf{x} \) 处可微，那么 \( \mathbf{d} \) 是可行方向的一个必要条件是： \[ \nabla g_ i(\mathbf{x})^\top \mathbf{d} \leq 0 \quad \text{对于所有起作用的 } g_ i \] \[ \nabla h_ j(\mathbf{x})^\top \mathbf{d} = 0 \quad \text{对于所有 } h_ j \] 这些条件确保了沿着 \( \mathbf{d} \) 移动一个无穷小步长，不会立即违反任何起作用约束。寻找可行下降方向的线性规划模型基于上述线性化条件，一个常见的策略是通过求解一个辅助的线性规划（LP）或二次规划（QP）来寻找搜索方向 \( \mathbf{d} \)。一个典型的模型是： \[ \begin{align* } \min_ {\mathbf{d}, \beta} \quad & \beta \\ \text{s.t.} \quad & \nabla f(\mathbf{x})^\top \mathbf{d} \leq \beta \\ & \nabla g_ i(\mathbf{x})^\top \mathbf{d} \leq \beta, \quad \text{对于所有起作用的 } g_ i \\ & \nabla h_ j(\mathbf{x})^\top \mathbf{d} = 0, \quad \text{对于所有 } h_ j \\ & \|\mathbf{d}\|_ \infty \leq 1 \quad \text{(规范化约束，防止无界解)} \end{align* } \] 在这个模型中：目标是最小化一个辅助变量 \( \beta \)。第一个约束 \( \nabla f(\mathbf{x})^\top \mathbf{d} \leq \beta \) 与下降性相关。如果我们能找到 \( \mathbf{d} \) 使得 \( \beta < 0 \)，那么就有 \( \nabla f(\mathbf{x})^\top \mathbf{d} \leq \beta < 0 \)，即 \( \mathbf{d} \) 是下降方向。第二组约束 \( \nabla g_ i(\mathbf{x})^\top \mathbf{d} \leq \beta \) 保证了对于起作用的不等式约束，其线性化变化量不超过 \( \beta \)。如果 \( \beta < 0 \)，则意味着 \( \nabla g_ i(\mathbf{x})^\top \mathbf{d} < 0 \)，这比可行性必要条件的 \( \leq 0 \) 更严格，有助于在非线性约束下保持可行性。第三组约束处理等式约束。如果这个LP的最优值 \( \beta^* < 0 \)，那么我们就找到了一个可行的下降方向 \( \mathbf{d}^* \)。如果 \( \beta^* = 0 \)，则当前点 \( \mathbf{x} \) 通常满足某种形式的最优性条件（如一阶必要条件）。线搜索与迭代过程一旦找到了一个可行的下降方向 \( \mathbf{d}^k \)，下一步是确定步长 \( \alpha^k \)。 \[ \mathbf{x}^{k+1} = \mathbf{x}^k + \alpha^k \mathbf{d}^k \] 步长 \( \alpha^k \) 需要通过线搜索来确定，以确保：可行性：\( \mathbf{x}^{k+1} \in S \)。目标函数下降：\( f(\mathbf{x}^{k+1}) < f(\mathbf{x}^k) \)。常用的线搜索方法是“Armijo型”可行方向搜索或“精确线搜索”在可行方向上的变体。由于约束的存在，步长选择需要额外小心，以避免“越界”。算法框架与收敛性综合以上步骤，可行方向法的基本框架如下：初始化：选择一个初始可行点 \( \mathbf{x}^0 \in S \)，设定容忍度 \( \epsilon > 0 \)，令 \( k = 0 \)。方向寻找：在当前点 \( \mathbf{x}^k \)，构造并求解方向寻找子问题（如步骤4中的LP）。设其解为 \( (\mathbf{d}^k, \beta^k) \)。收敛性检验：如果 \( |\beta^k| < \epsilon \)（或 \( \beta^k \ge 0 \)），则算法停止，\( \mathbf{x}^k \) 被认为是一个近似驻点。否则，转到步骤4。线搜索：沿着方向 \( \mathbf{d}^k \) 进行线搜索，找到一个步长 \( \alpha^k > 0 \)，使得 \( \mathbf{x}^{k+1} = \mathbf{x}^k + \alpha^k \mathbf{d}^k \in S \) 且 \( f(\mathbf{x}^{k+1}) < f(\mathbf{x}^k) \)。迭代：令 \( k = k+1 \)，返回步骤2。在适当的约束规格（如Mangasarian-Fromovitz约束规格）下，该算法产生的序列的极限点满足KKT一阶最优性条件。方法特点与应用场景优点：概念直观，对于线性约束问题尤其有效，因为线性约束的可行方向可以精确刻画。缺点：对于非线性约束，由于线性化近似只在当前点的小邻域内有效，算法可能只能采取很小的步长，导致效率低下（“锯齿现象”）。此外，方向寻找子问题的求解本身也是一个优化问题，计算成本可能较高。应用：它是许多更高级算法（如序列线性规划SLP、梯度投影法）的基础思想，在工程设计、经济均衡等具有复杂约束的优化问题中有其应用价值。