好的，我将为您生成并讲解一个尚未出现在您已学习列表中的运筹学重要词条。
非线性规划中的原始-对偶内点法
这是一个将线性规划的内点法思想，成功拓展到求解非线性约束优化问题的强大算法框架。我将从核心思想开始，逐步展开其精妙之处。
第一步：重温核心问题与障碍函数思想
我们考虑一个标准的非线性规划问题：
最小化 f(x)
满足于 c_i(x) = 0, i ∈ E (等式约束)
c_i(x) ≥ 0, i ∈ I (不等式约束)
其中，f(x) 和 c_i(x) 是连续可微的，通常还要求二阶可微。目标是在满足所有约束的条件下，找到使目标函数最小的 x。
“内点法”的核心是要求迭代点始终保持在可行域内部。对于不等式约束 c_i(x) ≥ 0，如何保证迭代点不触碰边界（即 c_i(x)=0）？经典的方法是引入对数障碍函数：
B(x, μ) = f(x) - μ * Σ_{i∈I} ln(c_i(x))
这里，μ > 0 是一个很小的正数，称为“障碍参数”。-ln(c_i(x)) 是关键：当 c_i(x) 从正值趋向于 0（即接近边界）时，-ln(c_i(x)) 会急剧趋向于正无穷大，从而在目标函数中施加一个巨大的惩罚，有效地在边界上树立起一道“屏障”，阻止迭代点越界。这样，原约束问题就转化为了一个关于 x 的无约束（或仅有等式约束）问题：最小化 B(x, μ)，并满足等式约束 c_i(x)=0, i∈E。
第二步：引入松弛变量与扰动KKT条件
为了系统地导出算法，我们引入松弛变量 s_i，将不等式约束转化为等式约束和非负性约束：
c_i(x) - s_i = 0, 且 s_i ≥ 0, 对于 i ∈ I
现在，问题的拉格朗日函数为：
L(x, λ, s, z) = f(x) - Σ_{i∈E} λ_i c_i(x) - Σ_{i∈I} λ_i (c_i(x) - s_i) - Σ_{i∈I} z_i s_i
其中，λ 是对应于等式（以及转换后的等式）的拉格朗日乘子，z_i ≥ 0 是专门对应于松弛变量非负性约束 s_i ≥ 0 的乘子。
原问题的一阶最优性条件是KKT条件。而原始-对偶内点法的精髓在于，它不仅要求解满足这些KKT条件，还要在求解过程中始终保持对原始可行性、对偶可行性，以及最重要的——严格正性条件 s_i > 0, z_i > 0。为此，它引入一个“扰动”：
将互补松弛条件 s_i z_i = 0 替换为：
s_i z_i = μ, 对于 i ∈ I
这里的 μ 就是之前的障碍参数。这个 μ 的扰动是关键一步：它放松了严格的互补性，允许 s_i 和 z_i 都为正，只要它们的乘积是一个小的正数 μ。这样，迭代点就可以在可行域内部（s_i > 0）沿着一条被称为“中心路径”的轨迹行进。
第三步：构造“扰动KKT系统”与牛顿方向
现在，我们需要求解的方程组（即“扰动KKT系统”）是：
∇f(x) - A_E(x)^T λ - A_I(x)^T λ_I = 0 （稳定性条件）
c_i(x) = 0, i ∈ E （原始等式可行）
c_i(x) - s_i = 0, i ∈ I （原始不等式可行，以等式形式）
S Z e - μ e = 0 （扰动互补松弛条件）
s_i ≥ 0, z_i ≥ 0 （对偶可行）
其中，A_E(x) 和 A_I(x) 分别是等式和不等式约束的雅可比矩阵，S 和 Z 是以 s_i 和 z_i 为对角元素的对角矩阵，e 是全1向量。
对于固定的 μ，我们想要求解这个关于变量 (x, λ, s, z) 的非线性方程组。牛顿法是自然的工具。我们对上述方程组在当前点 (x_k, λ_k, s_k, z_k) 处进行一阶泰勒展开（线性化），得到其牛顿方程：
[ ∇²ₓₓL -A_E^T -A_I^T 0 ] [ Δx ] = - [ ∇f - A_E^Tλ - A_I^Tλ_I ]
[ A_E 0 0 0 ] [ Δλ_E ] - [ c_E ]
[ A_I 0 0 -I ] [ Δλ_I ] - [ c_I - s ]
[ 0 0 Z_k S_k ] [ Δs ] - [ SZe - μe ]
这是一个关于搜索方向 (Δx, Δλ_E, Δλ_I, Δs) 的大型线性方程组。解出这个方向，我们就能更新迭代点。Δz 可以通过其他变量表示出来。这个搜索方向就是“原始-对偶牛顿方向”。
第四步：回溯直线搜索与障碍参数更新策略
得到牛顿方向 (Δx, Δλ, Δs, Δz) 后，我们不能简单地进行全步长更新（即 x_{k+1} = x_k + Δx），因为需要保持 s_i 和 z_i 的严格正性。
我们采用回溯直线搜索。选择一个步长 α ∈ (0, 1]，使得：
- 原始对偶可行性改善：更新后的点更接近满足等式约束。
- 正性条件保持：
s_{k+1} = s_k + α Δs > 0且z_{k+1} = z_k + α Δz > 0。
通常会取一个略小于1的初始步长（如0.995），然后通过一个衰减因子（如0.5）不断回溯，直到满足条件。
最后，我们需要一个策略来更新障碍参数 μ，驱动它逐渐减小到0。常用的策略是根据当前点的“对偶间隙”（衡量最优性的指标，在非线性问题中近似为 s^T z）来设定：
μ_{k+1} = σ * (s_k^T z_k) / m_I
其中，m_I 是不等式约束的个数，σ ∈ (0, 1) 是一个中心参数（如0.1）。当 μ 减小时，扰动互补松弛条件 s_i z_i = μ 就越来越接近真正的互补松弛条件 s_i z_i = 0，从而引导迭代点沿着中心路径趋近于原问题的最优解。
第五步：算法框架与意义总结
将以上步骤整合，原始-对偶内点法的框架如下：
- 初始化：选择初始点
(x_0, λ_0, s_0, z_0)，满足s_0 > 0, z_0 > 0，初始障碍参数μ_0 > 0，以及参数σ ∈ (0,1)，设定容差ε > 0。 - 主循环（当对偶间隙
s_k^T z_k > ε时）：
a. 设置当前μ：μ_k = σ * (s_k^T z_k) / m_I。
b. 计算方向：求解上述牛顿方程，得到原始-对偶搜索方向(Δx, Δλ, Δs, Δz)。
c. 计算步长：通过回溯直线搜索，确定一个保证正性的最大步长α_k。
d. 更新迭代点：x_{k+1} = x_k + α_k Δx， 类似地更新λ, s, z。 - 输出：满足精度要求的近似最优解。
它的核心优势在于：
- 全局和局部快速收敛：在适当条件下，当迭代点靠近解时，由于牛顿法的性质，它能实现超线性甚至二次收敛。
- 对问题规模相对不敏感：与活动集法相比，其每次迭代的计算量（求解牛顿方程）虽然较大，但迭代次数较少，且对约束数量的敏感度较低，特别适合大规模、稠密约束的非线性问题。
- 理论基础坚实：与线性规划的对应算法一脉相承，具有良好的理论收敛性保证。
通过引入障碍函数、松弛变量、扰动KKT条件，并系统化地应用牛顿法和回溯搜索，原始-对偶内点法为求解复杂的非线性约束优化问题提供了一个强大而统一的数值框架。