非线性规划中的内点障碍函数法进阶题：非凸、大规模、等式与不等式混合约束的求解策略
字数 6875 2025-12-21 11:06:26

非线性规划中的内点障碍函数法进阶题：非凸、大规模、等式与不等式混合约束的求解策略

题目描述

考虑一个带有非凸目标函数、非线性等式和不等式约束的大规模非线性规划问题，其标准形式如下：

\[\begin{aligned} \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) \geq 0, \quad i \in \mathcal{I} \end{aligned} \]

其中，目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 是二阶连续可微但非凸的。等式约束索引集为 \(\mathcal{E}\)，不等式约束索引集为 \(\mathcal{I}\)，且 \(|\mathcal{E}| + |\mathcal{I}| = m\)，其中 \(m\) 可以很大，但雅可比矩阵 \(J(x) = [\nabla c_1(x), \ldots, \nabla c_m(x)]^T\) 通常是稀疏的。此外，可行域可能是非凸的，并且存在严格内点（即满足所有不等式严格大于0的点）。目标是利用内点障碍函数法，特别是其原始-对偶框架，设计一个高效、鲁棒的求解策略，以处理问题的非凸性、大规模性和混合约束特性。

解题过程

我们将循序渐进地讲解求解此问题的内点障碍函数法进阶策略，核心思想是将约束优化问题转化为一系列更容易求解的、只含等式约束的子问题，并通过调整障碍参数来控制对原始可行域的逼近程度。

第一步：问题重构与障碍函数引入

  1. 障碍函数转换：首先处理不等式约束。内点法通过在目标函数中添加一个“障碍项”来惩罚靠近不等式约束边界的点，从而将原问题转化为一系列只有等式约束的问题。最常用的是对数障碍函数：

\[ B(x; \mu) = f(x) - \mu \sum_{i \in \mathcal{I}} \ln(c_i(x)) \]

这里，$ \mu > 0 $ 称为**障碍参数**。当 $ c_i(x) \to 0^+ $ 时，$ -\ln(c_i(x)) \to +\infty $，从而阻止迭代点违反不等式约束（即保持 $ c_i(x) > 0 $）。这个性质是“内点”名称的由来。
  1. 带等式约束的障碍子问题：对于每个给定的 \(\mu\)，我们求解一个只含等式约束的优化问题：

\[ \begin{aligned} \min_{x \in \mathbb{R}^n} \quad & B(x; \mu) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E} \end{aligned} \]

理论上，当 $ \mu \to 0^+ $ 时，这个障碍子问题的最优解序列会收敛到原问题的最优解。

第二步：构建子问题的拉格朗日函数与最优性条件

  1. 拉格朗日函数：为上述障碍子问题引入拉格朗日乘子 \(\lambda \in \mathbb{R}^{|\mathcal{E}|}\) 对应等式约束，其拉格朗日函数为：

\[ \mathcal{L}_{\mu}(x, \lambda) = B(x; \mu) - \sum_{i \in \mathcal{E}} \lambda_i c_i(x) \]

更清晰地写出：

\[ \mathcal{L}_{\mu}(x, \lambda) = f(x) - \mu \sum_{i \in \mathcal{I}} \ln(c_i(x)) - \sum_{i \in \mathcal{E}} \lambda_i c_i(x) \]

  1. KKT条件（一阶最优性条件）：障碍子问题的稳定点（在非凸情况下，可能是局部极小点）满足以下KKT条件：
    a. 梯度平稳条件：

\[ \nabla_x \mathcal{L}_{\mu}(x, \lambda) = \nabla f(x) - \sum_{i \in \mathcal{I}} \frac{\mu}{c_i(x)} \nabla c_i(x) - \sum_{i \in \mathcal{E}} \lambda_i \nabla c_i(x) = 0 \]

   定义**松弛变量** $ s_i = c_i(x) $ 对于 $ i \in \mathcal{I} $，并引入**对偶变量** $ z_i = \mu / s_i $ 对于 $ i \in \mathcal{I} $。这个定义源于最优性条件的自然推导（互补松弛条件的扰动形式）。于是梯度平稳条件可重写为更对称的形式：

\[ \nabla f(x) - J_{\mathcal{E}}(x)^T \lambda - J_{\mathcal{I}}(x)^T z = 0 \]

   其中 $ J_{\mathcal{E}}(x) $ 和 $ J_{\mathcal{I}}(x) $ 分别是等式和不等式约束的雅可比矩阵，$ z = [z_i]_{i \in \mathcal{I}} $。
b. **原始可行性条件**：

\[ c_i(x) = 0, \quad i \in \mathcal{E} \quad \text{(等式约束)} \]

\[ s_i = c_i(x), \quad s_i > 0, \quad i \in \mathcal{I} \quad \text{(松弛变量与严格不等式)} \]

c. **对偶可行性条件**：

\[ z_i \geq 0, \quad i \in \mathcal{I} \]

d. **互补条件（扰动形式）**：

\[ S_i Z_i e = \mu e, \quad i \in \mathcal{I} \]

   这里，$ S_i = \text{diag}(s_i) $， $ Z_i = \text{diag}(z_i) $， $ e $ 是全是1的向量。这个条件是由定义 $ z_i = \mu / s_i $ 自然导出的，它是标准互补条件 $ s_i z_i = 0 $ 的一个“扰动”，当 $ \mu \to 0 $ 时，它趋近于标准的互补松弛条件。

我们将满足上述所有条件的点 $ (x(\mu), \lambda(\mu), s(\mu), z(\mu)) $ 构成的轨迹称为**中心路径**。内点法的核心思想就是沿着这条中心路径，随着 $ \mu $ 的减小，追踪到原始问题的最优解。

第三步：推导原始-对偶牛顿方向（求解KKT系统）

为了找到对于给定 \(\mu\) 的中心路径点，我们通常使用牛顿法来求解上述KKT方程组。我们记当前迭代点为 \((x, \lambda, s, z)\)，目标是找到搜索方向 \((\Delta x, \Delta \lambda, \Delta s, \Delta z)\)。

  1. 线性化KKT系统：对KKT条件在当前点进行一阶泰勒展开，忽略高阶项，得到一个线性方程组（牛顿方程）：

\[ \begin{bmatrix} H & -J_{\mathcal{E}}^T & -J_{\mathcal{I}}^T & 0 \\ J_{\mathcal{E}} & 0 & 0 & 0 \\ J_{\mathcal{I}} & 0 & 0 & -I \\ 0 & 0 & Z & S \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta \lambda \\ \Delta s \\ \Delta z \end{bmatrix} = - \begin{bmatrix} \nabla f - J_{\mathcal{E}}^T \lambda - J_{\mathcal{I}}^T z \\ c_{\mathcal{E}}(x) \\ s - c_{\mathcal{I}}(x) \\ S Z e - \mu e \end{bmatrix} \]

其中，$ H = \nabla_{xx}^2 \mathcal{L}(x, \lambda, z) $ 是原问题（非障碍问题）拉格朗日函数 $ \mathcal{L} = f(x) - \lambda^T c_{\mathcal{E}}(x) - z^T c_{\mathcal{I}}(x) $ 的Hessian矩阵。注意，在推导中，障碍项 $ -\mu \sum \ln(s_i) $ 的Hessian贡献被吸收进了互补条件线性化后的 $ S $ 和 $ Z $ 矩阵中，最终体现在右侧残差向量的最后一行 $ SZe - \mu e $。
  1. 简化与求解：这是一个大型、稀疏的对称不定线性系统。通常通过代数消元来简化。从第四个方程 \(Z \Delta s + S \Delta z = - (SZe - \mu e)\)，可以解出 \(\Delta z\)：

\[ \Delta z = -Z e - S^{-1} (SZe - \mu e) - S^{-1} Z \Delta s \]

但更常用的策略是直接消去 $ \Delta z $。从第四个方程解出 $ \Delta z = -z - \mu S^{-1} e - S^{-1} Z \Delta s $。然后将 $ \Delta z $ 的表达式代入第一个方程，并与第二、三个方程联立，得到一个更小的关于 $ (\Delta x, \Delta \lambda, \Delta s) $ 的对称系统。对于大规模问题，我们通常使用**对称不定分解**（如LDL^T分解）或**迭代法**（如共轭梯度法、GMRES）来求解这个线性系统。矩阵的稀疏性在这里至关重要，可以极大地节省存储和计算成本。

第四步：迭代算法框架与自适应策略

  1. 基本算法循环：
    a. 初始化：选取一个初始点 \(x^0\) 满足 \(c_{\mathcal{I}}(x^0) > 0\)（严格内点），初始对偶变量 \(\lambda^0, z^0 > 0\)，初始障碍参数 \(\mu^0\)，以及容差 \(\epsilon > 0\)。
    b. 迭代（对于k=0,1,2,...）：
    • 求解牛顿方向：在当前点 \((x^k, \lambda^k, s^k, z^k)\) 和当前障碍参数 \(\mu^k\) 下，求解第三步中描述的线性系统，得到搜索方向 \(d^k = (\Delta x^k, \Delta \lambda^k, \Delta s^k, \Delta z^k)\)。
    • 计算步长：由于需要保持 \(s > 0, z > 0\)，步长 \(\alpha^k\) 通常通过分数到边界规则确定：

\[ \alpha_{\text{max}}^s = \min(1, \min_{i: \Delta s_i < 0} (-s_i / \Delta s_i) \cdot \eta) \]

\[ \alpha_{\text{max}}^z = \min(1, \min_{i: \Delta z_i < 0} (-z_i / \Delta z_i) \cdot \eta) \]

     其中 $ \eta \in (0,1) $ 是一个安全系数（如0.995），确保新点严格保持正性。然后取 $ \alpha^k = \min(\alpha_{\text{max}}^s, \alpha_{\text{max}}^z) $。
   * **更新迭代点**：

\[ x^{k+1} = x^k + \alpha^k \Delta x^k, \quad \lambda^{k+1} = \lambda^k + \alpha^k \Delta \lambda^k, \quad s^{k+1} = s^k + \alpha^k \Delta s^k, \quad z^{k+1} = z^k + \alpha^k \Delta z^k \]

   * **更新障碍参数**：这是“自适应”的核心之一。一种常见的策略是根据当前互补间隙 $ C_k = (s^k)^T z^k / |\mathcal{I}| $ 来更新：

\[ \mu^{k+1} = \sigma_k \cdot C_k \]

     其中 $ \sigma_k \in (0,1) $ 称为**中心参数**。一个**自适应**的策略是：如果牛顿步长 $ \alpha^k $ 接近1（表明当前模型拟合得很好），可以选择更小的 $ \sigma_k $（如0.1），从而更激进地减小 $ \mu $；如果步长很小，则选择更大的 $ \sigma_k $（如0.5或0.8），以更保守的方式接近中心路径，避免振荡。
   * **收敛性检查**：检查以下停机准则（原始-对偶残差和互补间隙）：

\[ \|\nabla f(x) - J_{\mathcal{E}}^T \lambda - J_{\mathcal{I}}^T z\|_{\infty} \leq \epsilon, \quad \|c_{\mathcal{E}}(x)\|_{\infty} \leq \epsilon, \quad \|SZe\|_{\infty} \leq \epsilon \]

     如果满足，则停止并输出 $ (x^{k+1}, \lambda^{k+1}, z^{k+1}) $ 作为近似解。
  1. 处理非凸性与Hessian修正：由于目标函数和约束可能非凸，拉格朗日函数的Hessian矩阵 \(H\) 可能不定，这会导致牛顿方程系统不稳定，牛顿方向可能不是下降方向。常见的处理策略是对Hessian进行修正，例如：
    • 添加正则化项：在牛顿方程中，用 \(H + \delta I\) 代替 \(H\)，其中 \(\delta > 0\) 使得矩阵正定。\(\delta\) 可以自适应调整，当 \(H\) 有负特征值时增大 \(\delta\)。
    • 使用拟牛顿法：对于大规模问题，计算精确Hessian代价高，可以用BFGS或L-BFGS等拟牛顿法来构造 \(H\) 的正定近似。在约束优化中，这通常应用于简化空间或精确Hessian的近似计算。

第五步：针对大规模和稀疏性的高级技巧

  1. 稀疏线性求解器：牛顿方程的系数矩阵通常是稀疏的。应利用其稀疏结构，使用稀疏矩阵存储格式（如CSR、CSC）和稀疏直接求解器（如MA57、PARDISO、KLU）或迭代求解器（如MINRES、SYMMLQ处理对称不定系统）。
  2. 内点法与线性化技巧结合：对于非线性程度很高的约束，单纯的牛顿步可能不够。可以采用信赖域或线搜索策略来全局化牛顿法。在内点法中，这通常通过求解一个带有信赖域约束或线搜索的二次规划子问题来实现，而不是直接使用牛顿步。
  3. 处理等式与不等式混合约束的统一框架：如前所述，引入松弛变量和对偶变量，将不等式转化为等式和界约束，从而在统一的原始-对偶框架下处理所有约束。
  4. 自适应策略的扩展：
    • 自适应障碍参数更新：除了基于互补间隙和步长的策略，还可以根据预测-校正方法。在预测步使用一个更激进的 \(\mu\) 计算方向，在校正步通过求解额外的线性系统来补偿高阶误差，这可以加快收敛。
    • 自适应正则化：如前所述，自适应调整Hessian修正项 \(\delta\)，以在保证矩阵正定性和算法鲁棒性的前提下，尽可能保持二阶信息。

总结

本进阶题目详细阐述了一种用于求解非凸、大规模、带混合约束非线性规划的自适应内点障碍函数法。其核心路径是：通过引入对数障碍函数将不等式约束吸收进目标，构建一系列等式约束子问题；利用原始-对偶框架和牛顿法求解每个子问题的中心点；通过自适应地更新障碍参数和可能地修正Hessian矩阵，在保持迭代点严格可行（内点）的同时，稳健、高效地追踪中心路径至原问题的最优解。针对大规模和稀疏性，强调了稀疏线性代数求解和全局化策略（如信赖域）的重要性。该方法是非线性规划中处理复杂约束问题的强大工具，尤其在拥有良好稀疏结构的工程优化问题中表现出色。

非线性规划中的内点障碍函数法进阶题：非凸、大规模、等式与不等式混合约束的求解策略 题目描述 考虑一个带有非凸目标函数、非线性等式和不等式约束的大规模非线性规划问题，其标准形式如下： $$ \begin{aligned} \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) \geq 0, \quad i \in \mathcal{I} \end{aligned} $$ 其中，目标函数 \( f: \mathbb{R}^n \to \mathbb{R} \) 是二阶连续可微但非凸的。等式约束索引集为 \( \mathcal{E} \)，不等式约束索引集为 \( \mathcal{I} \)，且 \( |\mathcal{E}| + |\mathcal{I}| = m \)，其中 \( m \) 可以很大，但雅可比矩阵 \( J(x) = [ \nabla c_ 1(x), \ldots, \nabla c_ m(x)]^T \) 通常是稀疏的。此外，可行域可能是非凸的，并且存在严格内点（即满足所有不等式严格大于0的点）。目标是利用 内点障碍函数法 ，特别是其原始-对偶框架，设计一个高效、鲁棒的求解策略，以处理问题的非凸性、大规模性和混合约束特性。 解题过程 我们将循序渐进地讲解求解此问题的内点障碍函数法进阶策略，核心思想是将约束优化问题转化为一系列更容易求解的、只含等式约束的子问题，并通过调整障碍参数来控制对原始可行域的逼近程度。 第一步：问题重构与障碍函数引入 障碍函数转换 ：首先处理不等式约束。内点法通过在目标函数中添加一个“障碍项”来惩罚靠近不等式约束边界的点，从而将原问题转化为一系列只有等式约束的问题。最常用的是对数障碍函数： \[ B(x; \mu) = f(x) - \mu \sum_ {i \in \mathcal{I}} \ln(c_ i(x)) \] 这里，\( \mu > 0 \) 称为 障碍参数 。当 \( c_ i(x) \to 0^+ \) 时，\( -\ln(c_ i(x)) \to +\infty \)，从而阻止迭代点违反不等式约束（即保持 \( c_ i(x) > 0 \)）。这个性质是“内点”名称的由来。 带等式约束的障碍子问题 ：对于每个给定的 \( \mu \)，我们求解一个只含等式约束的优化问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & B(x; \mu) \\ \text{s.t.} \quad & c_ i(x) = 0, \quad i \in \mathcal{E} \end{aligned} \] 理论上，当 \( \mu \to 0^+ \) 时，这个障碍子问题的最优解序列会收敛到原问题的最优解。 第二步：构建子问题的拉格朗日函数与最优性条件 拉格朗日函数 ：为上述障碍子问题引入拉格朗日乘子 \( \lambda \in \mathbb{R}^{|\mathcal{E}|} \) 对应等式约束，其拉格朗日函数为： \[ \mathcal{L} {\mu}(x, \lambda) = B(x; \mu) - \sum {i \in \mathcal{E}} \lambda_ i c_ i(x) \] 更清晰地写出： \[ \mathcal{L} {\mu}(x, \lambda) = f(x) - \mu \sum {i \in \mathcal{I}} \ln(c_ i(x)) - \sum_ {i \in \mathcal{E}} \lambda_ i c_ i(x) \] KKT条件（一阶最优性条件） ：障碍子问题的稳定点（在非凸情况下，可能是局部极小点）满足以下KKT条件： a. 梯度平稳条件 ： \[ \nabla_ x \mathcal{L} {\mu}(x, \lambda) = \nabla f(x) - \sum {i \in \mathcal{I}} \frac{\mu}{c_ i(x)} \nabla c_ i(x) - \sum_ {i \in \mathcal{E}} \lambda_ i \nabla c_ i(x) = 0 \] 定义 松弛变量 \( s_ i = c_ i(x) \) 对于 \( i \in \mathcal{I} \)，并引入 对偶变量 \( z_ i = \mu / s_ i \) 对于 \( i \in \mathcal{I} \)。这个定义源于最优性条件的自然推导（互补松弛条件的扰动形式）。于是梯度平稳条件可重写为更对称的形式： \[ \nabla f(x) - J_ {\mathcal{E}}(x)^T \lambda - J_ {\mathcal{I}}(x)^T z = 0 \] 其中 \( J_ {\mathcal{E}}(x) \) 和 \( J_ {\mathcal{I}}(x) \) 分别是等式和不等式约束的雅可比矩阵，\( z = [ z_ i]_ {i \in \mathcal{I}} \)。 b. 原始可行性条件 ： \[ c_ i(x) = 0, \quad i \in \mathcal{E} \quad \text{(等式约束)} \] \[ s_ i = c_ i(x), \quad s_ i > 0, \quad i \in \mathcal{I} \quad \text{(松弛变量与严格不等式)} \] c. 对偶可行性条件 ： \[ z_ i \geq 0, \quad i \in \mathcal{I} \] d. 互补条件（扰动形式） ： \[ S_ i Z_ i e = \mu e, \quad i \in \mathcal{I} \] 这里，\( S_ i = \text{diag}(s_ i) \)， \( Z_ i = \text{diag}(z_ i) \)， \( e \) 是全是1的向量。这个条件是由定义 \( z_ i = \mu / s_ i \) 自然导出的，它是标准互补条件 \( s_ i z_ i = 0 \) 的一个“扰动”，当 \( \mu \to 0 \) 时，它趋近于标准的互补松弛条件。 我们将满足上述所有条件的点 \( (x(\mu), \lambda(\mu), s(\mu), z(\mu)) \) 构成的轨迹称为 中心路径 。内点法的核心思想就是沿着这条中心路径，随着 \( \mu \) 的减小，追踪到原始问题的最优解。 第三步：推导原始-对偶牛顿方向（求解KKT系统） 为了找到对于给定 \( \mu \) 的中心路径点，我们通常使用牛顿法来求解上述KKT方程组。我们记当前迭代点为 \( (x, \lambda, s, z) \)，目标是找到搜索方向 \( (\Delta x, \Delta \lambda, \Delta s, \Delta z) \)。 线性化KKT系统 ：对KKT条件在当前点进行一阶泰勒展开，忽略高阶项，得到一个线性方程组（牛顿方程）： \[ \begin{bmatrix} H & -J_ {\mathcal{E}}^T & -J_ {\mathcal{I}}^T & 0 \\ J_ {\mathcal{E}} & 0 & 0 & 0 \\ J_ {\mathcal{I}} & 0 & 0 & -I \\ 0 & 0 & Z & S \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta \lambda \\ \Delta s \\ \Delta z \end{bmatrix} = - \begin{bmatrix} \nabla f - J_ {\mathcal{E}}^T \lambda - J_ {\mathcal{I}}^T z \\ c_ {\mathcal{E}}(x) \\ s - c_ {\mathcal{I}}(x) \\ S Z e - \mu e \end{bmatrix} \] 其中，\( H = \nabla_ {xx}^2 \mathcal{L}(x, \lambda, z) \) 是原问题（非障碍问题）拉格朗日函数 \( \mathcal{L} = f(x) - \lambda^T c_ {\mathcal{E}}(x) - z^T c_ {\mathcal{I}}(x) \) 的Hessian矩阵。注意，在推导中，障碍项 \( -\mu \sum \ln(s_ i) \) 的Hessian贡献被吸收进了互补条件线性化后的 \( S \) 和 \( Z \) 矩阵中，最终体现在右侧残差向量的最后一行 \( SZe - \mu e \)。 简化与求解 ：这是一个大型、稀疏的对称不定线性系统。通常通过代数消元来简化。从第四个方程 \( Z \Delta s + S \Delta z = - (SZe - \mu e) \)，可以解出 \( \Delta z \)： \[ \Delta z = -Z e - S^{-1} (SZe - \mu e) - S^{-1} Z \Delta s \] 但更常用的策略是直接消去 \( \Delta z \)。从第四个方程解出 \( \Delta z = -z - \mu S^{-1} e - S^{-1} Z \Delta s \)。然后将 \( \Delta z \) 的表达式代入第一个方程，并与第二、三个方程联立，得到一个更小的关于 \( (\Delta x, \Delta \lambda, \Delta s) \) 的对称系统。对于大规模问题，我们通常使用 对称不定分解 （如LDL^T分解）或 迭代法 （如共轭梯度法、GMRES）来求解这个线性系统。矩阵的稀疏性在这里至关重要，可以极大地节省存储和计算成本。 第四步：迭代算法框架与自适应策略 基本算法循环 ： a. 初始化 ：选取一个初始点 \( x^0 \) 满足 \( c_ {\mathcal{I}}(x^0) > 0 \)（严格内点），初始对偶变量 \( \lambda^0, z^0 > 0 \)，初始障碍参数 \( \mu^0 \)，以及容差 \( \epsilon > 0 \)。 b. 迭代（对于k=0,1,2,...） ： 求解牛顿方向 ：在当前点 \( (x^k, \lambda^k, s^k, z^k) \) 和当前障碍参数 \( \mu^k \) 下，求解第三步中描述的线性系统，得到搜索方向 \( d^k = (\Delta x^k, \Delta \lambda^k, \Delta s^k, \Delta z^k) \)。 计算步长 ：由于需要保持 \( s > 0, z > 0 \)，步长 \( \alpha^k \) 通常通过 分数到边界规则 确定： \[ \alpha_ {\text{max}}^s = \min(1, \min_ {i: \Delta s_ i < 0} (-s_ i / \Delta s_ i) \cdot \eta) \] \[ \alpha_ {\text{max}}^z = \min(1, \min_ {i: \Delta z_ i < 0} (-z_ i / \Delta z_ i) \cdot \eta) \] 其中 \( \eta \in (0,1) \) 是一个安全系数（如0.995），确保新点严格保持正性。然后取 \( \alpha^k = \min(\alpha_ {\text{max}}^s, \alpha_ {\text{max}}^z) \)。 更新迭代点 ： \[ x^{k+1} = x^k + \alpha^k \Delta x^k, \quad \lambda^{k+1} = \lambda^k + \alpha^k \Delta \lambda^k, \quad s^{k+1} = s^k + \alpha^k \Delta s^k, \quad z^{k+1} = z^k + \alpha^k \Delta z^k \] 更新障碍参数 ：这是“自适应”的核心之一。一种常见的策略是根据当前互补间隙 \( C_ k = (s^k)^T z^k / |\mathcal{I}| \) 来更新： \[ \mu^{k+1} = \sigma_ k \cdot C_ k \] 其中 \( \sigma_ k \in (0,1) \) 称为 中心参数 。一个 自适应 的策略是：如果牛顿步长 \( \alpha^k \) 接近1（表明当前模型拟合得很好），可以选择更小的 \( \sigma_ k \)（如0.1），从而更激进地减小 \( \mu \)；如果步长很小，则选择更大的 \( \sigma_ k \)（如0.5或0.8），以更保守的方式接近中心路径，避免振荡。 收敛性检查 ：检查以下停机准则（原始-对偶残差和互补间隙）： \[ \|\nabla f(x) - J_ {\mathcal{E}}^T \lambda - J_ {\mathcal{I}}^T z\| {\infty} \leq \epsilon, \quad \|c {\mathcal{E}}(x)\| {\infty} \leq \epsilon, \quad \|SZe\| {\infty} \leq \epsilon \] 如果满足，则停止并输出 \( (x^{k+1}, \lambda^{k+1}, z^{k+1}) \) 作为近似解。 处理非凸性与Hessian修正 ：由于目标函数和约束可能非凸，拉格朗日函数的Hessian矩阵 \( H \) 可能不定，这会导致牛顿方程系统不稳定，牛顿方向可能不是下降方向。常见的处理策略是 对Hessian进行修正 ，例如： 添加正则化项 ：在牛顿方程中，用 \( H + \delta I \) 代替 \( H \)，其中 \( \delta > 0 \) 使得矩阵正定。\( \delta \) 可以自适应调整，当 \( H \) 有负特征值时增大 \( \delta \)。 使用拟牛顿法 ：对于大规模问题，计算精确Hessian代价高，可以用BFGS或L-BFGS等拟牛顿法来构造 \( H \) 的正定近似。在约束优化中，这通常应用于 简化空间 或 精确Hessian 的近似计算。 第五步：针对大规模和稀疏性的高级技巧 稀疏线性求解器 ：牛顿方程的系数矩阵通常是稀疏的。应利用其稀疏结构，使用稀疏矩阵存储格式（如CSR、CSC）和稀疏直接求解器（如MA57、PARDISO、KLU）或迭代求解器（如MINRES、SYMMLQ处理对称不定系统）。 内点法与线性化技巧结合 ：对于非线性程度很高的约束，单纯的牛顿步可能不够。可以采用 信赖域 或 线搜索 策略来全局化牛顿法。在内点法中，这通常通过求解一个带有信赖域约束或线搜索的二次规划子问题来实现，而不是直接使用牛顿步。 处理等式与不等式混合约束的统一框架 ：如前所述，引入松弛变量和对偶变量，将不等式转化为等式和界约束，从而在统一的原始-对偶框架下处理所有约束。 自适应策略的扩展 ： 自适应障碍参数更新 ：除了基于互补间隙和步长的策略，还可以根据 预测-校正 方法。在预测步使用一个更激进的 \( \mu \) 计算方向，在校正步通过求解额外的线性系统来补偿高阶误差，这可以加快收敛。 自适应正则化 ：如前所述，自适应调整Hessian修正项 \( \delta \)，以在保证矩阵正定性和算法鲁棒性的前提下，尽可能保持二阶信息。 总结 本进阶题目详细阐述了一种用于求解 非凸、大规模、带混合约束非线性规划 的 自适应内点障碍函数法 。其核心路径是：通过引入对数障碍函数将不等式约束吸收进目标，构建一系列等式约束子问题；利用原始-对偶框架和牛顿法求解每个子问题的中心点；通过自适应地更新障碍参数和可能地修正Hessian矩阵，在保持迭代点严格可行（内点）的同时，稳健、高效地追踪中心路径至原问题的最优解。针对大规模和稀疏性，强调了稀疏线性代数求解和全局化策略（如信赖域）的重要性。该方法是非线性规划中处理复杂约束问题的强大工具，尤其在拥有良好稀疏结构的工程优化问题中表现出色。