非线性规划中的原始-对偶对数壁垒法（Primal-Dual Logarithmic Barrier Method in Nonlinear Programming）
字数 4205 2025-12-20 21:51:00

非线性规划中的原始-对偶对数壁垒法（Primal-Dual Logarithmic Barrier Method in Nonlinear Programming）

好的，我将这个词条的知识从基础概念到方法细节，为你循序渐进地讲解。

第一步：从约束优化到“内部”思想的引入

  1. 问题回顾：我们考虑一个标准的非线性规划问题：

\[ \begin{aligned} \min_{x} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E}, \\ & c_i(x) \ge 0, \quad i \in \mathcal{I}, \end{aligned} \]

其中 \(f(x)\) 是目标函数，\(c_i(x)\) 是约束函数，\(\mathcal{E}\) 和 \(\mathcal{I}\) 分别是等式和不等式约束的指标集。我们的目标是找到满足所有约束并使目标函数最小的解 \(x^*\)。
2. 核心难点：在解 \(x^*\) 处，活跃的不等式约束（即 \(c_i(x^*) = 0\) 的那些约束）会像一堵“墙”一样阻止搜索路径。传统的可行方向法必须小心翼翼地在边界上“行走”，计算复杂。
3. 核心思想：能不能让搜索路径不必严格走在边界上，而是从一开始就呆在可行域“内部”，然后逐渐被“推”向边界上的最优解？这样，搜索过程就变成了一个在无约束或简单约束（等式）空间中的优化问题。这被称为内点法的核心哲学。

第二步：核心工具——对数壁垒函数

  1. 壁垒函数的作用：为了实现“呆在内部”的思想，我们需要一个函数来惩罚靠近约束边界的行为。当迭代点 \(x\) 在可行域内部（即对所有不等式约束有 \(c_i(x) > 0\)）时，这个惩罚很小；当点靠近边界（即某个 \(c_i(x) \to 0^+\)）时，这个惩罚会急剧增大，趋于无穷大，从而形成一道“壁垒”，阻止迭代点越界。
  2. 对数壁垒函数：最常用且具有优良数学性质的壁垒函数是对数壁垒函数。对于每一个不等式约束 \(c_i(x) \ge 0\)，我们引入惩罚项 \(-\mu \ln(c_i(x))\)，其中 \(\mu > 0\) 是一个称为壁垒参数的正数。
  3. 壁垒问题：将所有这些对数惩罚项加到原目标函数上，我们得到一个参数化的新问题，称为壁垒问题：

\[ \begin{aligned} \min_{x} \quad & B(x, \mu) = f(x) - \mu \sum_{i \in \mathcal{I}} \ln(c_i(x)) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E}. \end{aligned} \]

注意，原问题的不等式约束被吸收进了目标函数 \(B(x, \mu)\) 中，新问题只剩下等式约束。当 \(\mu\) 固定时，我们只在满足 \(c_i(x) > 0\) 的区域内最小化 \(B(x, \mu)\)，自然就停留在可行域内部。

第三步：原始-对偶框架的建立

  1. 纯障碍方法的局限：如果我们只求解上述壁垒问题，当 \(\mu \to 0\) 时，其解序列会逼近原问题的最优解。但每次更新 \(\mu\) 后，都需要重新求解一个带等式约束的优化问题，计算量很大。
  2. 引入对偶变量：为了高效求解，我们引入原始-对偶框架。首先，写出壁垒问题的拉格朗日函数（只包含等式约束的乘子 \(y\)）：

\[ L(x, y, \mu) = f(x) - \mu \sum_{i \in \mathcal{I}} \ln(c_i(x)) + \sum_{i \in \mathcal{E}} y_i c_i(x)。 \]

  1. 松弛互补条件：原问题的最优性条件（KKT条件）包含互补松弛条件：对于不等式约束，有 \(c_i(x^*) \ge 0, \lambda_i^* \ge 0, \lambda_i^* c_i(x^*) = 0\)。在壁垒法中，我们将其“松弛”了。我们引入松弛变量 \(s_i = c_i(x) > 0\) 和对应的对偶变量 \(z_i = \mu / s_i > 0\)。这个关系是关键：

\[ z_i s_i = \mu。 \]

当 \(\mu \to 0\) 时，这个关系就趋向于经典的互补松弛条件 \(z_i s_i = 0\)。这里的 \(z_i\) 可以理解为不等式约束 \(c_i(x) \ge 0\) 对应的拉格朗日乘子（符号被吸收进定义）。

第四步：原始-对偶系统的推导与牛顿步

  1. KKT系统：现在，我们可以写出壁垒问题在原始-对偶变量 \((x, s, y, z)\) 空间中的一阶最优性条件（KKT条件）：

\[ \begin{aligned} \nabla f(x) + A_E(x)^T y - A_I(x)^T z &= 0 \quad &\text{(拉格朗日函数梯度为零)} \\ c_i(x) - s_i &= 0, \quad i \in \mathcal{I} \quad &\text{(松弛变量定义)} \\ c_i(x) &= 0, \quad i \in \mathcal{E} \quad &\text{(等式约束)} \\ z_i s_i &= \mu, \quad i \in \mathcal{I} \quad &\text{(修正的互补松弛条件)} \end{aligned} \]

其中 \(A_E(x)\) 和 \(A_I(x)\) 分别是等式和不等式约束的雅可比矩阵。
2. 牛顿法应用：上述是一个关于变量 \((x, s, y, z)\) 的非线性方程组。我们可以用牛顿法求解。牛顿法的每一步，我们需要求解一个线性系统（牛顿方程），以获得搜索方向 \((\Delta x, \Delta s, \Delta y, \Delta z)\)。
3. 对称化：在推导牛顿方程时，修正的互补松弛条件 \(z_i s_i = \mu\) 会引入非线性项。通过一些代数变换（例如，用 \(Z \Delta s + S \Delta z = \mu e - ZSe\) 代替，其中 \(Z, S\) 是以 \(z_i, s_i\) 为对角元的对角矩阵，\(e\) 是全1向量），我们可以得到一个对称的线性系统，便于数值求解。这个系统的系数矩阵通常被称为缩减KKT矩阵。

第五步：算法流程与中心路径

  1. 算法框架：
  • 初始化：选择一个初始点 \((x^0, s^0, y^0, z^0)\)，其中 \(s^0 > 0, z^0 > 0\)，且满足初始可行性（等式约束和 \(c_i(x^0)=s^0_i\)）。
  • 迭代循环（对于 \(k = 0, 1, 2, ...\)）：
  1. 选择壁垒参数：设置当前的 \(\mu^k = \sigma \cdot ( (z^k)^T s^k ) / m\)，其中 \(m\) 是不等式约束个数，\(\sigma \in (0, 1)\) 是“中心参数”，用于控制向边界趋近的速度。\((z^k)^T s^k\) 是当前对偶间隙的估计。
  2. 计算牛顿方向：求解当前迭代点处的牛顿方程，得到搜索方向 \((\Delta x^k, \Delta s^k, \Delta y^k, \Delta z^k)\)。
  3. 计算步长：由于需要保持 \(s_i > 0, z_i > 0\)，步长 \(\alpha^k\) 不能为1。通常采用回退线搜索，选择一个尽可能大但能保证新迭代点 \((x^{k+1}, s^{k+1}, ...) = (x^k, s^k, ...) + \alpha^k (\Delta x^k, \Delta s^k, ...)\) 仍然满足 \(s_i > 0, z_i > 0\) 的步长。
    4. 更新迭代点：应用步长，得到新的迭代点。
    5. 检查收敛：判断原始可行性误差、对偶可行性误差和对偶间隙是否都小于预设的容差。若是，则停止。
  4. 中心路径：当 \(\mu\) 从一个正数逐渐减小到0时，壁垒问题的最优解轨迹 \((x^*(\mu), s^*(\mu), y^*(\mu), z^*(\mu))\) 在原始-对偶空间里形成一条光滑的路径，称为中心路径。算法的迭代过程可以看作是沿着这条路径，从内部（较大的 \(\mu\)，点更靠近可行域“中心”）走向边界上的最优解（\(\mu=0\)）。中心参数 \(\sigma\) 控制了迭代点是紧紧跟随中心路径（\(\sigma\) 小）还是更激进地减小对偶间隙（\(\sigma\) 大）。

第六步：方法特性与总结

  1. 优点：
    • 多项式时间复杂性：对于凸优化问题（如线性规划、凸二次规划），原始-对偶对数壁垒法在理论上被证明具有多项式时间收敛性。
    • 数值稳健：与单纯形法（可能遍历许多顶点）相比，内点法经历的迭代次数对问题规模相对不敏感，迭代次数通常较少（几十到几百次）。
    • 统一框架：该方法为线性、二次、半定规划以及一般的平滑非线性凸规划提供了一个统一的算法框架。
  2. 挑战：
    • 初始点：需要一个严格可行的初始点（即满足所有等式约束，且不等式约束严格大于零）。寻找这样的点本身可能就是一个非平凡问题，通常通过“两阶段法”或“不可行内点法”解决。
    • 非凸问题：对于非凸问题，该方法只能找到满足一阶必要条件的稳定点（可能是局部极小、鞍点等），且收敛性理论更复杂。
    • 海森矩阵：每一步都需要计算或近似拉格朗日函数的二阶导数（海森矩阵），对于大规模问题，这可能成为计算瓶颈。

总而言之，非线性规划中的原始-对偶对数壁垒法是一种强大的内点法。它通过引入对数壁垒函数将不等式约束“软化”为目标函数的一部分惩罚，并在原始变量和对偶变量构成的扩展空间中使用牛顿法迭代。通过驱动壁垒参数 \(\mu\) 趋近于零，算法沿着中心路径从可行域内部逼近边界上的最优解，兼具理论上的优良性质和实际中的高效性能。

非线性规划中的原始-对偶对数壁垒法（Primal-Dual Logarithmic Barrier Method in Nonlinear Programming） 好的，我将这个词条的知识从基础概念到方法细节，为你循序渐进地讲解。 第一步：从约束优化到“内部”思想的引入 问题回顾 ：我们考虑一个标准的非线性规划问题： \[ \begin{aligned} \min_ {x} \quad & f(x) \\ \text{s.t.} \quad & c_ i(x) = 0, \quad i \in \mathcal{E}, \\ & c_ i(x) \ge 0, \quad i \in \mathcal{I}, \end{aligned} \] 其中 \(f(x)\) 是目标函数，\(c_ i(x)\) 是约束函数，\(\mathcal{E}\) 和 \(\mathcal{I}\) 分别是等式和不等式约束的指标集。我们的目标是找到满足所有约束并使目标函数最小的解 \(x^* \)。 核心难点 ：在解 \(x^ \) 处，活跃的不等式约束（即 \(c_ i(x^ ) = 0\) 的那些约束）会像一堵“墙”一样阻止搜索路径。传统的可行方向法必须小心翼翼地在边界上“行走”，计算复杂。 核心思想 ：能不能让搜索路径不必严格走在边界上，而是从一开始就呆在可行域“内部”，然后逐渐被“推”向边界上的最优解？这样，搜索过程就变成了一个在无约束或简单约束（等式）空间中的优化问题。这被称为 内点法 的核心哲学。 第二步：核心工具——对数壁垒函数 壁垒函数的作用 ：为了实现“呆在内部”的思想，我们需要一个函数来惩罚靠近约束边界的行为。当迭代点 \(x\) 在可行域内部（即对所有不等式约束有 \(c_ i(x) > 0\)）时，这个惩罚很小；当点靠近边界（即某个 \(c_ i(x) \to 0^+\)）时，这个惩罚会急剧增大，趋于无穷大，从而形成一道“壁垒”，阻止迭代点越界。 对数壁垒函数 ：最常用且具有优良数学性质的壁垒函数是 对数壁垒函数 。对于每一个不等式约束 \(c_ i(x) \ge 0\)，我们引入惩罚项 \(-\mu \ln(c_ i(x))\)，其中 \(\mu > 0\) 是一个称为 壁垒参数 的正数。 壁垒问题 ：将所有这些对数惩罚项加到原目标函数上，我们得到一个参数化的新问题，称为 壁垒问题 ： \[ \begin{aligned} \min_ {x} \quad & B(x, \mu) = f(x) - \mu \sum_ {i \in \mathcal{I}} \ln(c_ i(x)) \\ \text{s.t.} \quad & c_ i(x) = 0, \quad i \in \mathcal{E}. \end{aligned} \] 注意，原问题的不等式约束被吸收进了目标函数 \(B(x, \mu)\) 中，新问题只剩下等式约束。当 \(\mu\) 固定时，我们只在满足 \(c_ i(x) > 0\) 的区域内最小化 \(B(x, \mu)\)，自然就停留在可行域内部。 第三步：原始-对偶框架的建立 纯障碍方法的局限 ：如果我们只求解上述壁垒问题，当 \(\mu \to 0\) 时，其解序列会逼近原问题的最优解。但每次更新 \(\mu\) 后，都需要重新求解一个带等式约束的优化问题，计算量很大。 引入对偶变量 ：为了高效求解，我们引入 原始-对偶 框架。首先，写出壁垒问题的拉格朗日函数（只包含等式约束的乘子 \(y\)）： \[ L(x, y, \mu) = f(x) - \mu \sum_ {i \in \mathcal{I}} \ln(c_ i(x)) + \sum_ {i \in \mathcal{E}} y_ i c_ i(x)。 \] 松弛互补条件 ：原问题的最优性条件（KKT条件）包含互补松弛条件：对于不等式约束，有 \(c_ i(x^ ) \ge 0, \lambda_ i^ \ge 0, \lambda_ i^* c_ i(x^* ) = 0\)。在壁垒法中，我们将其“松弛”了。我们引入 松弛变量 \(s_ i = c_ i(x) > 0\) 和对应的 对偶变量 \(z_ i = \mu / s_ i > 0\)。这个关系是关键： \[ z_ i s_ i = \mu。 \] 当 \(\mu \to 0\) 时，这个关系就趋向于经典的互补松弛条件 \(z_ i s_ i = 0\)。这里的 \(z_ i\) 可以理解为不等式约束 \(c_ i(x) \ge 0\) 对应的拉格朗日乘子（符号被吸收进定义）。 第四步：原始-对偶系统的推导与牛顿步 KKT系统 ：现在，我们可以写出壁垒问题在原始-对偶变量 \((x, s, y, z)\) 空间中的一阶最优性条件（KKT条件）： \[ \begin{aligned} \nabla f(x) + A_ E(x)^T y - A_ I(x)^T z &= 0 \quad &\text{(拉格朗日函数梯度为零)} \\ c_ i(x) - s_ i &= 0, \quad i \in \mathcal{I} \quad &\text{(松弛变量定义)} \\ c_ i(x) &= 0, \quad i \in \mathcal{E} \quad &\text{(等式约束)} \\ z_ i s_ i &= \mu, \quad i \in \mathcal{I} \quad &\text{(修正的互补松弛条件)} \end{aligned} \] 其中 \(A_ E(x)\) 和 \(A_ I(x)\) 分别是等式和不等式约束的雅可比矩阵。 牛顿法应用 ：上述是一个关于变量 \((x, s, y, z)\) 的非线性方程组。我们可以用牛顿法求解。牛顿法的每一步，我们需要求解一个线性系统（牛顿方程），以获得搜索方向 \((\Delta x, \Delta s, \Delta y, \Delta z)\)。 对称化 ：在推导牛顿方程时，修正的互补松弛条件 \(z_ i s_ i = \mu\) 会引入非线性项。通过一些代数变换（例如，用 \(Z \Delta s + S \Delta z = \mu e - ZSe\) 代替，其中 \(Z, S\) 是以 \(z_ i, s_ i\) 为对角元的对角矩阵，\(e\) 是全1向量），我们可以得到一个对称的线性系统，便于数值求解。这个系统的系数矩阵通常被称为 缩减KKT矩阵 。 第五步：算法流程与中心路径 算法框架 ： 初始化 ：选择一个初始点 \((x^0, s^0, y^0, z^0)\)，其中 \(s^0 > 0, z^0 > 0\)，且满足初始可行性（等式约束和 \(c_ i(x^0)=s^0_ i\)）。 迭代循环 （对于 \(k = 0, 1, 2, ...\)）： 选择壁垒参数 ：设置当前的 \(\mu^k = \sigma \cdot ( (z^k)^T s^k ) / m\)，其中 \(m\) 是不等式约束个数，\(\sigma \in (0, 1)\) 是“中心参数”，用于控制向边界趋近的速度。\((z^k)^T s^k\) 是当前对偶间隙的估计。 计算牛顿方向 ：求解当前迭代点处的牛顿方程，得到搜索方向 \((\Delta x^k, \Delta s^k, \Delta y^k, \Delta z^k)\)。 计算步长 ：由于需要保持 \(s_ i > 0, z_ i > 0\)，步长 \(\alpha^k\) 不能为1。通常采用 回退线搜索 ，选择一个尽可能大但能保证新迭代点 \((x^{k+1}, s^{k+1}, ...) = (x^k, s^k, ...) + \alpha^k (\Delta x^k, \Delta s^k, ...)\) 仍然满足 \(s_ i > 0, z_ i > 0\) 的步长。 更新迭代点 ：应用步长，得到新的迭代点。 检查收敛 ：判断原始可行性误差、对偶可行性误差和对偶间隙是否都小于预设的容差。若是，则停止。 中心路径 ：当 \(\mu\) 从一个正数逐渐减小到0时，壁垒问题的最优解轨迹 \((x^ (\mu), s^ (\mu), y^ (\mu), z^ (\mu))\) 在原始-对偶空间里形成一条光滑的路径，称为 中心路径 。算法的迭代过程可以看作是沿着这条路径，从内部（较大的 \(\mu\)，点更靠近可行域“中心”）走向边界上的最优解（\(\mu=0\)）。中心参数 \(\sigma\) 控制了迭代点是紧紧跟随中心路径（\(\sigma\) 小）还是更激进地减小对偶间隙（\(\sigma\) 大）。 第六步：方法特性与总结 优点 ： 多项式时间复杂性 ：对于凸优化问题（如线性规划、凸二次规划），原始-对偶对数壁垒法在理论上被证明具有多项式时间收敛性。 数值稳健 ：与单纯形法（可能遍历许多顶点）相比，内点法经历的迭代次数对问题规模相对不敏感，迭代次数通常较少（几十到几百次）。 统一框架 ：该方法为线性、二次、半定规划以及一般的平滑非线性凸规划提供了一个统一的算法框架。 挑战 ： 初始点 ：需要一个严格可行的初始点（即满足所有等式约束，且不等式约束严格大于零）。寻找这样的点本身可能就是一个非平凡问题，通常通过“两阶段法”或“不可行内点法”解决。 非凸问题 ：对于非凸问题，该方法只能找到满足一阶必要条件的稳定点（可能是局部极小、鞍点等），且收敛性理论更复杂。 海森矩阵 ：每一步都需要计算或近似拉格朗日函数的二阶导数（海森矩阵），对于大规模问题，这可能成为计算瓶颈。 总而言之， 非线性规划中的原始-对偶对数壁垒法 是一种强大的内点法。它通过引入对数壁垒函数将不等式约束“软化”为目标函数的一部分惩罚，并在原始变量和对偶变量构成的扩展空间中使用牛顿法迭代。通过驱动壁垒参数 \(\mu\) 趋近于零，算法沿着中心路径从可行域内部逼近边界上的最优解，兼具理论上的优良性质和实际中的高效性能。