好的，根据你提供的已讲题目列表，我随机选择一个尚未出现过的算法进行讲解。
非线性规划中的原始-对偶内点路径跟踪法（Primal-Dual Interior-Point Path-Following Method）基础题
1. 问题描述
假设我们有一个标准的非线性规划问题，形式如下：
最小化目标函数：\(f(\mathbf{x})\)
满足约束条件：
\[\begin{aligned} & g_i(\mathbf{x}) = 0, \quad i = 1, \dots, m, \\ & h_j(\mathbf{x}) \ge 0, \quad j = 1, \dots, p. \end{aligned} \]
其中，\(\mathbf{x} \in \mathbb{R}^n\)， \(f, g_i, h_j\) 都是二阶连续可微的函数。我们要求解这个优化问题，并重点关注其 不等式约束 \(h_j(\mathbf{x}) \ge 0\)。
直接处理不等式约束是困难的，因为它在最优点可能处于边界（等式成立，\(h_j = 0\)）或内部（严格不等式，\(h_j > 0\)）。外点罚函数法通过惩罚违反的约束来处理，但迭代点可能不可行。内点法 的核心思想是构造一条从可行域内部通向最优点的“路径”，并始终保持在可行域内部（\(h_j(\mathbf{x}) > 0\)），从而规避了处理边界激活的复杂性。原始-对偶路径跟踪法是其中最主流、高效的一类。
2. 核心思想与转化
为了将不等式约束转化为易于处理的等式形式，我们引入 松弛变量 \(s_j\) 和 对数障碍函数。
- 引入松弛变量：将不等式约束 \(h_j(\mathbf{x}) \ge 0\) 改写为 \(h_j(\mathbf{x}) - s_j = 0\)，并强制要求 \(s_j \ge 0\)。这个新的 \(s_j\) 被称为松弛变量，它代表了约束 \(h_j\) 的“松弛度”。只要 \(s_j > 0\)，原不等式 \(h_j(\mathbf{x}) > 0\) 就成立，我们就在可行域内部。
- 使用对数障碍函数：为了在优化过程中自然地强制 \(s_j > 0\)，我们在目标函数中加入一个惩罚项 \(-\mu \sum_{j=1}^{p} \ln(s_j)\)，其中 \(\mu > 0\) 称为障碍参数。当 \(s_j\) 接近 0（即接近边界）时，\(-\ln(s_j) \to +\infty\)，这会“阻止”迭代点触碰边界，从而保证内点性。当 \(\mu \to 0^+\) 时，这个惩罚的影响越来越小，障碍问题的解就逼近原问题的解。
于是，我们得到 障碍问题（Barrier Problem）：
最小化：
\[B_\mu(\mathbf{x}, \mathbf{s}) = f(\mathbf{x}) - \mu \sum_{j=1}^{p} \ln(s_j) \]
满足：
\[\begin{aligned} & g_i(\mathbf{x}) = 0, \quad i = 1, \dots, m, \\ & h_j(\mathbf{x}) - s_j = 0, \quad j = 1, \dots, p, \\ & s_j > 0. \end{aligned} \]
这是一个仅含等式约束和简单正定界的问题，我们可以使用拉格朗日乘子法来求解它的一阶最优性条件。
3. 构建拉格朗日函数与KKT条件
为障碍问题构造增广拉格朗日函数：
\[\mathcal{L}_\mu(\mathbf{x}, \mathbf{s}, \mathbf{y}, \mathbf{z}) = f(\mathbf{x}) - \mu \sum_{j=1}^{p} \ln(s_j) + \sum_{i=1}^{m} y_i g_i(\mathbf{x}) + \sum_{j=1}^{p} z_j (h_j(\mathbf{x}) - s_j). \]
其中，\(\mathbf{y} \in \mathbb{R}^m\) 是对应等式约束 \(g_i = 0\) 的拉格朗日乘子（或称对偶变量），\(\mathbf{z} \in \mathbb{R}^p\) 是对应等式化后不等式约束 \(h_j - s_j = 0\) 的拉格朗日乘子，并且 \(z_j \ge 0\)（对于最小化问题，不等式约束为 \(\ge 0\) 时，其乘子非负）。
根据一阶最优性条件（KKT条件），在最优解 \((\mathbf{x}^*, \mathbf{s}^*, \mathbf{y}^*, \mathbf{z}^*)\) 处，梯度应为零，且 \(s_j, z_j > 0\)（互补松弛条件在 \(\mu > 0\) 时表现为 \(z_j s_j = \mu\)）。具体写出：
\[\begin{aligned} \text{(1) 对 } \mathbf{x} &: \nabla f(\mathbf{x}) + \sum_{i=1}^{m} y_i \nabla g_i(\mathbf{x}) + \sum_{j=1}^{p} z_j \nabla h_j(\mathbf{x}) = 0, \\ \text{(2) 对 } \mathbf{s} &: -\mu S^{-1} \mathbf{e} - \mathbf{z} = 0, \quad \text{即 } \mathbf{z} = -\mu S^{-1} \mathbf{e}, \\ \text{(3) 对 } \mathbf{y} &: g_i(\mathbf{x}) = 0, \quad i = 1, \dots, m, \\ \text{(4) 对 } \mathbf{z} &: h_j(\mathbf{x}) - s_j = 0, \quad j = 1, \dots, p. \end{aligned} \]
其中，\(S = \text{diag}(s_1, \dots, s_p)\)， \(\mathbf{e} = [1, \dots, 1]^T\)， \(Z = \text{diag}(z_1, \dots, z_p)\)。由条件(2)可得 \(Z S \mathbf{e} = \mu \mathbf{e}\)，这被称为中心路径条件（Central Path Condition）。
4. 中心路径与路径跟踪策略
对于每一个 \(\mu > 0\)，障碍问题都有一个最优解，记为 \((\mathbf{x}(\mu), \mathbf{s}(\mu), \mathbf{y}(\mu), \mathbf{z}(\mu))\)。所有这些解的集合形成了一条光滑的曲线，称为 中心路径（Central Path）。当 \(\mu \to 0\) 时，中心路径的端点 \((\mathbf{x}^*, \mathbf{s}^*, \mathbf{y}^*, \mathbf{z}^*)\) 就是原问题的最优解，并且满足严格的互补性 \(s_j^* z_j^* = 0\)。
路径跟踪法 的策略是：不直接求解 \(\mu = 0\) 时的原问题KKT系统（那可能病态），而是从一个较大的 \(\mu\) 开始，求解对应障碍问题的近似KKT系统（上述(1)-(4)式），得到一个在中心路径附近的点。然后 逐渐减小 \(\mu\)（例如，令 \(\mu_{k+1} = \sigma \mu_k\)， \(\sigma \in (0, 1)\)），并跟踪中心路径向原问题的最优点逼近。这样，整个过程都是在可行域内部稳定进行的。
5. 牛顿迭代求解近似KKT系统
对于给定的当前迭代点 \((\mathbf{x}_k, \mathbf{s}_k, \mathbf{y}_k, \mathbf{z}_k)\) 和当前的障碍参数 \(\mu_k\)，我们需要求解上述非线性方程组(1)-(4)来获得下一个中心路径点。我们使用 牛顿法 来近似求解这个系统。
令当前点的扰动为 \((\Delta \mathbf{x}, \Delta \mathbf{s}, \Delta \mathbf{y}, \Delta \mathbf{z})\)。我们在当前点对KKT条件进行一阶泰勒展开（线性化）。线性化后的系统（牛顿方程）为：
\[\begin{bmatrix} H & 0 & J_g^T & J_h^T \\ 0 & \Sigma & 0 & -I \\ J_g & 0 & 0 & 0 \\ J_h & -I & 0 & 0 \end{bmatrix} \begin{bmatrix} \Delta \mathbf{x} \\ \Delta \mathbf{s} \\ \Delta \mathbf{y} \\ \Delta \mathbf{z} \end{bmatrix} = - \begin{bmatrix} \nabla f + J_g^T \mathbf{y} + J_h^T \mathbf{z} \\ \mathbf{z} - \mu S^{-1} \mathbf{e} \\ \mathbf{g}(\mathbf{x}) \\ \mathbf{h}(\mathbf{x}) - \mathbf{s} \end{bmatrix}. \]
其中：
- \(H = \nabla_{xx}^2 \mathcal{L}_0(\mathbf{x}, \mathbf{y}, \mathbf{z}) = \nabla^2 f(\mathbf{x}) + \sum y_i \nabla^2 g_i(\mathbf{x}) + \sum z_j \nabla^2 h_j(\mathbf{x})\) 是拉格朗日函数的Hessian矩阵（相对于 \(\mathbf{x}\)）。
- \(\Sigma = \text{diag}(\frac{z_1}{s_1}, \dots, \frac{z_p}{s_p})\) 是由条件(2)线性化 \(\Delta z_j + (z_j / s_j) \Delta s_j\) 得到的对角矩阵。
- \(J_g, J_h\) 分别是 \(\mathbf{g}, \mathbf{h}\) 的雅可比矩阵（约束的梯度矩阵）。
- 等式右边的向量就是当前点不满足KKT条件的残差。
6. 算法步骤
原始-对偶路径跟踪法的一个基本框架如下：
步骤0：初始化
- 给定初始点 \(\mathbf{x}_0\) 满足 \(h_j(\mathbf{x}_0) > 0\)。
- 设置初始松弛变量 \(\mathbf{s}_0 = \mathbf{h}(\mathbf{x}_0) > 0\)。
- 初始化对偶变量 \(\mathbf{y}_0, \mathbf{z}_0 > 0\)。
- 选择初始障碍参数 \(\mu_0 > 0\)，衰减因子 \(\sigma \in (0, 1)\)（如0.2），容差 \(\epsilon > 0\)，初始步长缩放因子。
- 令迭代计数器 \(k = 0\)。
步骤1：检查收敛
- 计算原问题可行性误差 \(\| \mathbf{g}(\mathbf{x}_k) \|_\infty + \| \min(\mathbf{h}(\mathbf{x}_k), 0) \|_\infty\) 和对偶可行性误差 \(\| \nabla_{\mathbf{x}} \mathcal{L}_0 \|_\infty\)。
- 计算互补间隙 \(\eta_k = \mathbf{s}_k^T \mathbf{z}_k / p\)。
- 如果这些误差和互补间隙都小于 \(\epsilon\)，则停止迭代，输出当前点作为近似最优解。
步骤2：设置障碍参数
- \(\mu_k = \sigma \cdot \eta_k\)。（一种常见策略是让障碍参数与当前互补间隙成比例，这能实现自适应调整）
步骤3：求解牛顿方程
- 构建并求解第5部分中的线性方程组，得到搜索方向 \((\Delta \mathbf{x}_k, \Delta \mathbf{s}_k, \Delta \mathbf{y}_k, \Delta \mathbf{z}_k)\)。
步骤4：计算步长
- 为了保持 \(\mathbf{s} > 0\) 和 \(\mathbf{z} > 0\)，我们需要进行阻尼牛顿步。
- 计算最大允许步长：
\[ \alpha_s^{\max} = \min(1, 0.99 \times \min_{j: \Delta s_j < 0} (-s_j / \Delta s_j)), \]
\[ \alpha_z^{\max} = \min(1, 0.99 \times \min_{j: \Delta z_j < 0} (-z_j / \Delta z_j)). \]
（系数0.99是为了避免直接触及边界，保留一个安全裕度）
- 选择实际步长 \(\alpha_k = \min(\alpha_s^{\max}, \alpha_z^{\max})\)。有时也会对原变量 \(\mathbf{x}, \mathbf{y}\) 取稍小的步长以保证下降。
步骤5：更新迭代点
- \(\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \Delta \mathbf{x}_k\)
- \(\mathbf{s}_{k+1} = \mathbf{s}_k + \alpha_k \Delta \mathbf{s}_k\)
- \(\mathbf{y}_{k+1} = \mathbf{y}_k + \alpha_k \Delta \mathbf{y}_k\)
- \(\mathbf{z}_{k+1} = \mathbf{z}_k + \alpha_k \Delta \mathbf{z}_k\)
步骤6：循环
- 令 \(k = k+1\)，返回步骤1。
7. 总结与特点
- 优势：原始-对偶路径跟踪法收敛速度快（具有多项式时间复杂性），数值稳定性好，尤其擅长处理大规模、具有大量不等式约束的问题。它通过中心路径引导，避免了在边界附近振荡。
- 关键点：算法成功依赖于一个好的初始内点，以及高效、稳定地求解大型稀疏（或特殊结构）的牛顿方程。实际软件中（如IPOPT， LOQO）会采用更复杂的策略，如滤波器线搜索、二阶校正、惯性控制等来增强鲁棒性。
- 与已讲内容的区别：之前讨论的“内点法”多为基础概念或与其他方法（如反射牛顿法、罚函数法）的结合。本题聚焦于最核心的原始-对偶路径跟踪框架，它系统地处理了不等式约束，并通过中心路径将原问题和对偶问题的求解统一在一个迭代过程中，是现代内点法的基石。