序列内点法（Sequential Interior Point Method）基础题
我注意到您已经学习过许多非线性规划算法，包括内点法、序列二次规划等，但还没有系统讲解过序列内点法。这个算法是内点法（特别是原始对偶内点法）在求解序列凸近似子问题时的系统化应用，特别适合处理大规模不等式约束问题。下面我将详细讲解其原理、步骤和一个具体例题。
问题描述
考虑一个标准形式的非线性规划问题：
\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) \ge 0, \quad i = 1, \ldots, m \\ & Ax = b \end{aligned} \]
其中，\(f(x)\) 和 \(c_i(x)\) 是二次连续可微函数，且可能非凸。约束包括 \(m\) 个不等式和线性等式约束。序列内点法的核心思想是：在每一步，将原问题在当前迭代点 \(x^k\) 附近进行凸近似（例如，利用一阶泰勒展开构造线性化或二次近似模型），形成一个更容易求解的凸子问题（通常是线性规划LP或二次规划QP），然后使用原始对偶内点法精确且高效地求解这个子问题，从而得到一个搜索方向，沿此方向进行线搜索更新迭代点，并逐步逼近原问题的最优解。
循序渐进讲解
第一步：构造序列凸近似子问题
在第 \(k\) 次迭代，在当前点 \(x^k\) 处，对目标函数和约束进行近似。最常用的两种方式是：
- 序列线性规划（SLP）：用一阶泰勒展开线性化。
\[ \begin{aligned} \min_{d \in \mathbb{R}^n} \quad & f(x^k) + \nabla f(x^k)^T d \\ \text{s.t.} \quad & c_i(x^k) + \nabla c_i(x^k)^T d \ge 0, \quad i=1,\ldots,m \\ & A(x^k + d) = b \\ & \|d\|_\infty \le \Delta^k \end{aligned} \]
这里 $ d = x - x^k $ 是搜索方向，$ \Delta^k > 0 $ 是信赖域半径或移动限制，用于保证近似在小范围内有效，避免因线性化误差过大导致迭代发散。
- 序列二次规划（SQP）：用二阶近似，但通常利用拟牛顿法（如BFGS）近似Hessian矩阵 \(B^k \approx \nabla^2 L(x^k, \lambda^k)\) 以保持正定性，确保子问题是凸QP。
\[ \begin{aligned} \min_{d \in \mathbb{R}^n} \quad & \frac{1}{2} d^T B^k d + \nabla f(x^k)^T d \\ \text{s.t.} \quad & c_i(x^k) + \nabla c_i(x^k)^T d \ge 0, \quad i=1,\ldots,m \\ & A(x^k + d) = b \end{aligned} \]
无论哪种近似，得到的子问题都是一个凸优化问题（线性或二次目标，线性约束），且包含不等式约束。这正是内点法最擅长的领域。
第二步：使用原始对偶内点法求解子问题
以SLP子问题为例，其标准形式为：
\[\begin{aligned} \min_{d} \quad & g^T d \\ \text{s.t.} \quad & \bar{c}_i + a_i^T d \ge 0, \quad i=1,\ldots,m \\ & \tilde{A} d = \tilde{b} \\ & \|d\|_\infty \le \Delta \end{aligned} \]
其中 \(g = \nabla f(x^k)\)， \(\bar{c}_i = c_i(x^k)\)， \(a_i = \nabla c_i(x^k)\)， \(\tilde{A} = A\)， \(\tilde{b} = b - A x^k\)。注意，界约束 \(\|d\|_\infty \le \Delta\) 可以转化为 \(-\Delta \le d_j \le \Delta\)，即一组线性不等式。
原始对偶内点法的求解过程（对该子问题）：
- 引入松弛变量和对数障碍函数：将不等式约束 \(\bar{c}_i + a_i^T d \ge 0\) 写为 \(\bar{c}_i + a_i^T d - s_i = 0, \, s_i \ge 0\)，其中 \(s\) 是松弛变量。内点法通过将松弛变量的非负性约束用对数障碍函数 \(-\mu \sum_{i=1}^m \ln s_i\) 替代（\(\mu > 0\) 是障碍参数），将其吸收进目标函数，从而转化为等式约束问题。
- 构建拉格朗日函数与KKT系统：对于子问题，其障碍问题为：
\[ \min_{d, s} g^T d - \mu \sum_{i=1}^m \ln s_i \quad \text{s.t.} \quad \bar{c}_i + a_i^T d - s_i = 0, \, \tilde{A} d = \tilde{b}, \, -\Delta \le d_j \le \Delta \]
界约束也可用障碍函数处理。写出拉格朗日函数，并推导其最优性条件（KKT条件），得到一个非线性方程组。
- 牛顿迭代求解：在给定的 \(\mu\) 下，用牛顿法求解KKT方程组，得到搜索方向 \((\Delta d, \Delta s, \Delta \lambda, \Delta \nu)\)（其中 \(\lambda, \nu\) 是对应约束的拉格朗日乘子），更新原始变量、松弛变量和对偶变量。
- 障碍参数缩减与迭代：牛顿迭代至当前 \(\mu\) 下的近似解后，减小 \(\mu\)（例如 \(\mu \leftarrow \tau \mu, \, \tau \in (0,1)\)），重复牛顿迭代，直到满足子问题的收敛容差。由于子问题是凸的，内点法能快速收敛到高精度解，得到搜索方向 \(d^k\) 和对应的乘子估计 \(\lambda^{k+1}\)。
第三步：线搜索与迭代更新
得到子问题的解 \(d^k\) 后，将其作为原问题的候选搜索方向。但需要检查该方向是否能改善原问题的目标并满足可行性。通常采用价值函数（Merit Function） 如 \(\phi(x; \rho) = f(x) + \rho \sum_{i=1}^m \max(0, -c_i(x))\) 来衡量，其中 \(\rho > 0\) 是惩罚参数。
沿方向 \(d^k\) 进行线搜索（如Armijo回溯），找到步长 \(\alpha^k \in (0, 1]\)，使得价值函数充分下降：
\[\phi(x^k + \alpha^k d^k; \rho^k) \le \phi(x^k; \rho^k) + \eta \alpha^k D(\phi(x^k; \rho^k), d^k) \]
其中 \(D\) 是价值函数在 \(d^k\) 方向的导数估计，\(\eta \in (0,1)\)。
然后更新迭代点：
\[x^{k+1} = x^k + \alpha^k d^k \]
第四步：自适应调整与收敛检查
- 更新近似精度：根据子问题模型与实际函数行为的匹配程度，调整信赖域半径 \(\Delta^k\) 或移动限制。如果实际下降与预测下降比值好，则增大 \(\Delta^{k+1}\)；否则减小。
- 更新乘子估计：使用子问题求解得到的乘子 \(\lambda^{k+1}\) 作为下一次迭代的乘子初值，以提高子问题近似的准确性。
- 收敛判断：检查原问题的KKT条件的残差（如梯度残差、约束违反度）是否小于预设容差。若是，则停止；否则返回第一步，构造新的近似子问题。
算法特点与优势
- 高效处理不等式：内点法求解凸子问题能有效处理大量不等式约束，且具有多项式时间复杂性。
- 全局收敛：通过线搜索或信赖域框架（控制 \(\Delta^k\)）保证算法能从任意初始点收敛到稳定点。
- 灵活近似：可与SLP、SQP、SCP（序列凸规划）等多种框架结合。
- 适用于大规模问题：内点法对稀疏结构友好，适合大规模优化。
简单示例
考虑问题：
\[\min f(x) = (x_1 - 3)^2 + (x_2 - 2)^2 \quad \text{s.t.} \quad x_1 + x_2 \ge 1, \, x_1 \ge 0, \, x_2 \ge 0 \]
- 初始化：取 \(x^0 = (0.5, 0.5)\)， \(\Delta^0 = 0.5\)。
- 构造SLP子问题：在 \(x^0\) 处线性化。目标梯度 \(\nabla f = (-5, -3)\)。约束 \(c_1 = x_1 + x_2 - 1\)，梯度 \((1,1)\)；\(c_2 = x_1\)，梯度 \((1,0)\)；\(c_3 = x_2\)，梯度 \((0,1)\)。加上移动限制 \(\|d\|_\infty \le 0.5\)。
- 内点法求解子问题：得到一个线性规划，用内点法解得 \(d^0 \approx (0.5, 0.0)\)（向约束边界移动）。
- 线搜索：沿 \(d^0\) 搜索，取 \(\alpha=1\)，得 \(x^1 = (1.0, 0.5)\)，价值函数下降。
- 迭代：更新 \(\Delta^1\)，在 \(x^1\) 处构造新的线性化子问题，重复。经数次迭代后逼近最优解 \(x^* = (1, 0)\)。
通过这种“序列凸近似 + 内点法求解”的框架，序列内点法能系统、稳健地求解具有非线性不等式约束的优化问题，尤其适合约束条件较多、函数非线性的情况。