好的，根据你提供的庞大列表，我选择了一个尚未出现且具有代表性的算法题目。请注意，你提供的列表中包含了如“序列仿射缩放内点法基础题”这样的标题，但根据上下文“尚未出现”似乎是误输入的一部分。为了避免混淆，我将为你讲解一个经典的、列表中没有明确提及的内点法家族分支。
序列原对偶内点法基础题
题目描述
考虑一个标准形式的非线性规划问题：
\[\begin{align*} \min_{x \in \mathbb{R}^n} \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{align*} \]
其中，\(f(x)\) 和 \(c_i(x)\) 是二阶连续可微函数，\(\mathcal{E}\) 和 \(\mathcal{I}\) 分别表示等式和不等式约束的指标集。
目标：运用序列原对偶内点法的核心思想，构造求解该问题的迭代框架，并解释其关键步骤（屏障参数、扰动KKT条件、牛顿步计算、步长选择）的原理。
解题过程详解
序列原对偶内点法是目前求解大规模非线性规划最有效的算法之一。它的核心思想是将原问题的约束条件通过一个“对数屏障函数”吸收到目标函数中，并同时求解原变量和对偶变量（拉格朗日乘子），通过迭代使一个“扰动”的KKT条件得到满足。
步骤1：引入松弛变量与屏障函数
首先，处理不等式约束 \(c_i(x) \ge 0\)。我们引入松弛变量 \(s_i \ge 0\)，将不等式转化为等式：
\[c_i(x) - s_i = 0， \quad s_i \ge 0， \quad i \in \mathcal{I}. \]
现在，问题的难点在于 \(s_i \ge 0\) 这个非负约束。为了在迭代中自然地保持 \(s_i > 0\)（内点性），我们使用对数屏障函数。屏障函数 \(\mu \sum_{i \in \mathcal{I}} \ln(s_i)\) 在 \(s_i > 0\) 时有定义，当 \(s_i \to 0^+\) 时，函数值趋向于 \(-\infty\)，从而像一道“屏障”阻止 \(s_i\) 越过边界。参数 \(\mu > 0\) 称为屏障参数。
于是，我们构造屏障问题：
\[\begin{align*} \min_{x， s} \quad & \phi_{\mu}(x， s) = f(x) - \mu \sum_{i \in \mathcal{I}} \ln(s_i) \\ \text{s.t.} \quad & c_i(x) = 0， \quad i \in \mathcal{E}， \\ & c_i(x) - s_i = 0， \quad i \in \mathcal{I}， \\ & s_i > 0， \quad i \in \mathcal{I}. \end{align*} \]
当 \(\mu \to 0^+\) 时，屏障问题的最优解趋近于原问题的最优解。
步骤2：构造拉格朗日函数与KKT条件
为求解屏障问题，我们构造其拉格朗日函数。引入拉格朗日乘子 \(\lambda_i\)（对应所有等式约束，包括 \(c_i(x)=0\) 和 \(c_i(x)-s_i=0\)）。记 \(\lambda = [\lambda_{\mathcal{E}}； \lambda_{\mathcal{I}}]^T\)。
\[\mathcal{L}_{\mu}(x， s， \lambda) = f(x) - \mu \sum_{i \in \mathcal{I}} \ln(s_i) - \sum_{i \in \mathcal{E}} \lambda_i c_i(x) - \sum_{i \in \mathcal{I}} \lambda_i (c_i(x) - s_i). \]
根据一阶最优性条件（KKT条件），在最优解 \((x^*， s^*， \lambda^*)\) 处，梯度应为零，并且原可行性成立。对 \(\mathcal{L}_{\mu}\) 求偏导：
- 关于原变量 \(x\) 的稳定性条件：
\[ \nabla_x \mathcal{L}_{\mu} = \nabla f(x) - \sum_{i \in \mathcal{E}} \lambda_i \nabla c_i(x) - \sum_{i \in \mathcal{I}} \lambda_i \nabla c_i(x) = 0. \]
记 $A(x)^T = [\nabla c_1(x)， ...， \nabla c_m(x)]$，这可以简洁地写为：
\[ \nabla f(x) - A(x)^T \lambda = 0。 \quad (1) \]
- 关于松弛变量 \(s\) 的稳定性条件：
\[ \nabla_{s_i} \mathcal{L}_{\mu} = -\frac{\mu}{s_i} + \lambda_i = 0， \quad \forall i \in \mathcal{I}. \]
即：
\[ \lambda_i s_i = \mu， \quad \forall i \in \mathcal{I}。 \quad (2) \]
这个条件非常关键，它被称为**互补松弛条件**。在原问题的最优KKT条件中，它应是 $\lambda_i s_i = 0$（即要么乘子为0，要么约束紧）。这里被“扰动”为等于一个正数 $\mu$，使得在迭代中 $s_i$ 和 $\lambda_i$ 可以同时保持为正（内点性），只有当 $\mu \to 0$ 时才趋近于真正的互补松弛。
- 原始可行性条件：
\[ c_i(x) = 0， \quad i \in \mathcal{E}， \\ c_i(x) - s_i = 0， \quad i \in \mathcal{I}。 \quad (3) \]
步骤3：求解扰动KKT系统的牛顿步
我们当前有一个迭代点 \((x_k， s_k， \lambda_k)\)，满足 \(s_k > 0， \lambda_{\mathcal{I}， k} > 0\)，但通常不满足上面的方程组（1）-（3）。我们的目标是找到修正量 \((\Delta x， \Delta s， \Delta \lambda)\)，使得新的点 \((x+\Delta x， s+\Delta s， \lambda+\Delta \lambda)\) 能更好地满足这些条件。
我们对（1）-（3）在当前点进行一阶泰勒展开（即应用牛顿法），得到一个线性系统。记 \(g = \nabla f(x)\)， \(W = \nabla_{xx}^2 \mathcal{L} = \nabla^2 f(x) - \sum \lambda_i \nabla^2 c_i(x)\)（拉格朗日函数的Hessian阵）， \(A = A(x)\)。
经过推导（将（2）式 \(F_{\mu} = \lambda_i s_i - \mu = 0\) 线性化），得到的牛顿方程为：
\[\begin{bmatrix} W & 0 & -A^T \\ 0 & \Lambda & S \\ A & -I_{\mathcal{I}} & 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta s \\ \Delta \lambda \end{bmatrix} = - \begin{bmatrix} g - A^T \lambda \\ S \Lambda e - \mu e \\ c(x) - \hat{s} \end{bmatrix}. \]
这里：
- \(S = \text{diag}(s_i)\)， \(\Lambda = \text{diag}(\lambda_i)\) 是对角矩阵。
- \(\hat{s}\) 是一个向量，其 \(\mathcal{E}\) 部分为零（因为等式约束无松弛变量），\(\mathcal{I}\) 部分为 \(s\)。
- \(e\) 是全1向量。
- \(-I_{\mathcal{I}}\) 是一个矩阵，其 \(\mathcal{E}\) 部分为零块，\(\mathcal{I}\) 部分为负单位矩阵。
这个系统称为增广系统。通过代数消元（例如，从第二个方程解出 \(\Delta s\)，代入第三个方程），通常可以将其简化为一个更小的、只关于 \((\Delta x， \Delta \lambda)\) 的对称系统（称为紧缩系统），然后再回代求出 \(\Delta s\)。
步骤4：计算步长与迭代更新
直接采用牛顿步 \((\Delta x， \Delta s， \Delta \lambda)\) 可能破坏 \(s>0\) 和 \(\lambda_{\mathcal{I}}>0\) 的内点性。因此，我们需要回溯线搜索来确定步长 \(\alpha \in (0， 1]\)。
我们不仅要减小某个价值函数（如增广拉格朗日函数或原始对偶残差），还必须保证 \(s\) 和 \(\lambda_{\mathcal{I}}\) 的正性。因此，步长 \(\alpha\) 通常取为：
\[\alpha = \tau \cdot \min( \alpha_s^{\max}， \alpha_{\lambda}^{\max}， 1 )， \]
其中 \(\tau \in (0， 1)\) 是一个安全系数（如0.995），而：
\[\alpha_s^{\max} = \min_{i \in \mathcal{I}} \{ 1， -s_i / \Delta s_i \ \text{if} \ \Delta s_i < 0 \}， \\ \alpha_{\lambda}^{\max} = \min_{i \in \mathcal{I}} \{ 1， -\lambda_i / \Delta \lambda_i \ \text{if} \ \Delta \lambda_i < 0 \}. \]
这保证了 \(s + \alpha \Delta s > 0\) 且 \(\lambda_{\mathcal{I}} + \alpha \Delta \lambda_{\mathcal{I}} > 0\)。
迭代更新为：
\[x_{k+1} = x_k + \alpha \Delta x_k， \\ s_{k+1} = s_k + \alpha \Delta s_k， \\ \lambda_{k+1} = \lambda_k + \alpha \Delta \lambda_k. \]
步骤5：更新屏障参数与收敛判断
算法的主体是一个序列（Sequence）的过程：固定一个屏障参数 \(\mu\)，用牛顿法迭代若干步，求解对应的屏障问题近似解；然后减小 \(\mu\)（例如 \(\mu_{k+1} = \sigma \mu_k\)， \(\sigma \in (0， 1)\)， 如0.2），并以当前解为起点，开始求解下一个屏障问题。如此反复，直到 \(\mu\) 足够小，且原始对偶残差（即方程组（1）-（3）的左端范数）小于预设精度。
收敛判断通常基于原始可行性误差和对偶可行性误差的范数是否小于容忍度 \(\epsilon\)：
\[\|c(x)\| \le \epsilon， \quad \|\nabla f(x) - A(x)^T \lambda\| \le \epsilon， \quad \|\Lambda S e\| \le \epsilon. \]
总结
序列原对偶内点法的核心流程如下：
- 初始化：给定初始点 \((x_0， s_0 > 0， \lambda_0)\)，初始屏障参数 \(\mu_0 > 0\)，缩小因子 \(\sigma\)，精度 \(\epsilon\)。
- 主循环（外层）：当 \(\mu_k > \epsilon\) 或最优性误差未达标时：
a. 内层牛顿迭代：在当前 \(\mu_k\) 下，求解扰动KKT系统的牛顿方程，得到搜索方向 \((\Delta x， \Delta s， \Delta \lambda)\)。
b. 线搜索：计算保证正性的步长 \(\alpha_k\)，更新迭代点。
c. 收敛检查：检查当前点对应当前 \(\mu_k\) 的KKT残差是否足够小。若是，则进入步骤d；否则，返回步骤a继续内层迭代（实践中，内层通常只执行一次牛顿步，即与 \(\mu\) 更新同步进行）。
d. 更新屏障参数： \(\mu_{k+1} = \sigma \mu_k\)， \(k = k+1\)。 - 终止：输出满足精度的近似最优解 \((x_k， s_k， \lambda_k)\)。
这个算法的强大之处在于它通过扰动互补条件，将困难的互补性转化为光滑的非线性方程，再利用牛顿法快速收敛，同时通过逐步减小 \(\mu\) 来逼近真正的边界解。它结合了内点法的健壮性和牛顿法的快速局部收敛性。