半正定规划的罚函数法与内点法联合策略
字数 2335 2025-12-11 01:54:00

半正定规划的罚函数法与内点法联合策略

第一步：回顾半正定规划的基本框架
半正定规划（SDP）是优化变量为半正定矩阵的凸优化问题。其标准形式通常表示为：
极小化：\(C \bullet X\)（矩阵内积 \(C \bullet X = \text{tr}(C^T X)\)）
约束条件：\(A_i \bullet X = b_i, \quad i=1,\ldots,m\)
且 \(X \succeq 0\)（表示 \(X\) 为对称半正定矩阵）。

这里的难点在于处理半定约束 \(X \succeq 0\)，它不同于线性约束，直接求解较困难。传统方法主要有内点法和罚函数法。

第二步：单独理解罚函数法（Penalty Function Method）的核心思想
罚函数法通过将约束条件转化为目标函数中的惩罚项，把约束问题转化为一系列无约束问题求解。对于半定约束 \(X \succeq 0\)，需要构造一个惩罚函数 \(P(X)\) 满足：

  • 当 \(X\) 半正定时，\(P(X) = 0\)；
  • 当 \(X\) 不半正定时，\(P(X) > 0\) 且值越大惩罚越重。
    常用的一种罚函数基于最小特征值：\(P(X) = \mu \cdot \max(0, -\lambda_{\min}(X))^2\)，其中 \(\lambda_{\min}(X)\) 是 \(X\) 的最小特征值，\(\mu > 0\) 为惩罚参数。通过逐渐增大 \(\mu\)，迫使解满足半定性。

第三步：单独理解内点法（Interior-Point Method）的核心思想
内点法通过引入障碍函数，确保迭代点始终在可行域内部（即 \(X \succ 0\) 严格正定）。典型障碍函数是对数行列式 \(-\log \det(X)\)，将其加到目标函数中：
极小化：\(C \bullet X - \tau \log \det(X)\)
约束：\(A_i \bullet X = b_i\)
其中 \(\tau > 0\) 为障碍参数。随着 \(\tau \to 0\)，解趋近原问题最优解。内点法需求解一系列优化子问题，通常利用牛顿法。

第四步：联合策略的动机与基本架构
单独使用罚函数法可能遇到病态条件数问题；单独使用内点法则严格保持可行性，但子问题求解复杂度高。联合策略旨在结合两者优点：

  1. 外层框架采用罚函数法：将半定约束 \(X \succeq 0\) 作为惩罚项 \(P(X)\) 处理，而等式约束 \(A_i \bullet X = b_i\) 仍显式保留。这样将原问题转化为仅含线性等式约束的问题。
  2. 内层求解采用内点法思想：对每个固定的惩罚参数 \(\mu\)，求解子问题：
    极小化：\(C \bullet X + \mu \cdot P(X)\)
    约束：\(A_i \bullet X = b_i\)。
    由于子问题没有半定约束，但惩罚项 \(P(X)\) 可能非光滑（如基于特征值的罚函数）。为此，可引入内点法的光滑障碍函数对 \(P(X)\) 进行光滑近似，或直接对子问题构建拉格朗日函数并应用内点法求解其 KKT 系统。

第五步：一个典型联合策略——光滑化罚函数结合原-对内点法
具体实施步骤如下：

  1. 构造光滑罚函数：使用一个可微函数近似半定约束。例如，用 \(P_{\epsilon}(X) = \mu \cdot \sum_{i=1}^n \max(0, -\lambda_i(X) + \epsilon)^2\)，其中 \(\epsilon > 0\) 为光滑参数，通过逐渐减小 \(\epsilon\) 逼近原罚函数。
  2. 形成子问题：对给定的 \(\mu\) 和 \(\epsilon\)，求解：
    极小化：\(C \bullet X + P_{\epsilon}(X)\)
    约束：\(A_i \bullet X = b_i\)。
  3. 用原-对内点法求解子问题：写出子问题的拉格朗日函数 \(L(X, y) = C \bullet X + P_{\epsilon}(X) + \sum_{i=1}^m y_i (b_i - A_i \bullet X)\)，其 KKT 条件构成一个光滑方程组。应用内点法（如牛顿法）求解该方程组，得到当前 \((\mu, \epsilon)\) 下的近似解。
  4. 参数更新：逐渐增大惩罚参数 \(\mu\) 以加强半定约束的满足程度，同时减小光滑参数 \(\epsilon\) 以提高近似精度，并减小内点法的障碍参数 \(\tau\)（若子问题使用障碍函数）。迭代直至满足收敛准则。

第六步：策略的优势与收敛性
联合策略的优势在于：

  • 灵活性：等式约束和半定约束分开处理，可针对不同约束类型选择最适合的数值方法。
  • 数值稳定性：内点法处理子问题时能利用问题的凸结构，避免罚函数法单独使用时的数值病态。
  • 全局收敛：在适当条件下（如罚参数趋于无穷、光滑参数趋于零），序列收敛到原问题的最优解。

第七步：应用场景与扩展
该策略适用于大规模半正定规划，特别是当约束矩阵 \(A_i\) 具有特殊结构（如稀疏性）时，内点法求解子问题可高效利用。扩展方向包括：

  • 与非精确内点法结合，降低子问题求解成本。
  • 与一阶方法（如梯度法）结合，用于超大规模问题。
  • 推广到更一般的矩阵锥规划，如二阶锥规划与半定规划的混合问题。
半正定规划的罚函数法与内点法联合策略 第一步：回顾半正定规划的基本框架 半正定规划（SDP）是优化变量为半正定矩阵的凸优化问题。其标准形式通常表示为： 极小化：\( C \bullet X \)（矩阵内积 \( C \bullet X = \text{tr}(C^T X) \)） 约束条件：\( A_ i \bullet X = b_ i, \quad i=1,\ldots,m \) 且 \( X \succeq 0 \)（表示 \( X \) 为对称半正定矩阵）。 这里的难点在于处理半定约束 \( X \succeq 0 \)，它不同于线性约束，直接求解较困难。传统方法主要有内点法和罚函数法。 第二步：单独理解罚函数法（Penalty Function Method）的核心思想 罚函数法通过将约束条件转化为目标函数中的惩罚项，把约束问题转化为一系列无约束问题求解。对于半定约束 \( X \succeq 0 \)，需要构造一个惩罚函数 \( P(X) \) 满足： 当 \( X \) 半正定时，\( P(X) = 0 \)； 当 \( X \) 不半正定时，\( P(X) > 0 \) 且值越大惩罚越重。 常用的一种罚函数基于最小特征值：\( P(X) = \mu \cdot \max(0, -\lambda_ {\min}(X))^2 \)，其中 \( \lambda_ {\min}(X) \) 是 \( X \) 的最小特征值，\( \mu > 0 \) 为惩罚参数。通过逐渐增大 \( \mu \)，迫使解满足半定性。 第三步：单独理解内点法（Interior-Point Method）的核心思想 内点法通过引入障碍函数，确保迭代点始终在可行域内部（即 \( X \succ 0 \) 严格正定）。典型障碍函数是对数行列式 \( -\log \det(X) \)，将其加到目标函数中： 极小化：\( C \bullet X - \tau \log \det(X) \) 约束：\( A_ i \bullet X = b_ i \) 其中 \( \tau > 0 \) 为障碍参数。随着 \( \tau \to 0 \)，解趋近原问题最优解。内点法需求解一系列优化子问题，通常利用牛顿法。 第四步：联合策略的动机与基本架构 单独使用罚函数法可能遇到病态条件数问题；单独使用内点法则严格保持可行性，但子问题求解复杂度高。联合策略旨在结合两者优点： 外层框架采用罚函数法 ：将半定约束 \( X \succeq 0 \) 作为惩罚项 \( P(X) \) 处理，而等式约束 \( A_ i \bullet X = b_ i \) 仍显式保留。这样将原问题转化为仅含线性等式约束的问题。 内层求解采用内点法思想 ：对每个固定的惩罚参数 \( \mu \)，求解子问题： 极小化：\( C \bullet X + \mu \cdot P(X) \) 约束：\( A_ i \bullet X = b_ i \)。 由于子问题没有半定约束，但惩罚项 \( P(X) \) 可能非光滑（如基于特征值的罚函数）。为此，可引入内点法的光滑障碍函数对 \( P(X) \) 进行光滑近似，或直接对子问题构建拉格朗日函数并应用内点法求解其 KKT 系统。 第五步：一个典型联合策略——光滑化罚函数结合原-对内点法 具体实施步骤如下： 构造光滑罚函数 ：使用一个可微函数近似半定约束。例如，用 \( P_ {\epsilon}(X) = \mu \cdot \sum_ {i=1}^n \max(0, -\lambda_ i(X) + \epsilon)^2 \)，其中 \( \epsilon > 0 \) 为光滑参数，通过逐渐减小 \( \epsilon \) 逼近原罚函数。 形成子问题 ：对给定的 \( \mu \) 和 \( \epsilon \)，求解： 极小化：\( C \bullet X + P_ {\epsilon}(X) \) 约束：\( A_ i \bullet X = b_ i \)。 用原-对内点法求解子问题 ：写出子问题的拉格朗日函数 \( L(X, y) = C \bullet X + P_ {\epsilon}(X) + \sum_ {i=1}^m y_ i (b_ i - A_ i \bullet X) \)，其 KKT 条件构成一个光滑方程组。应用内点法（如牛顿法）求解该方程组，得到当前 \( (\mu, \epsilon) \) 下的近似解。 参数更新 ：逐渐增大惩罚参数 \( \mu \) 以加强半定约束的满足程度，同时减小光滑参数 \( \epsilon \) 以提高近似精度，并减小内点法的障碍参数 \( \tau \)（若子问题使用障碍函数）。迭代直至满足收敛准则。 第六步：策略的优势与收敛性 联合策略的优势在于： 灵活性 ：等式约束和半定约束分开处理，可针对不同约束类型选择最适合的数值方法。 数值稳定性 ：内点法处理子问题时能利用问题的凸结构，避免罚函数法单独使用时的数值病态。 全局收敛 ：在适当条件下（如罚参数趋于无穷、光滑参数趋于零），序列收敛到原问题的最优解。 第七步：应用场景与扩展 该策略适用于大规模半正定规划，特别是当约束矩阵 \( A_ i \) 具有特殊结构（如稀疏性）时，内点法求解子问题可高效利用。扩展方向包括： 与非精确内点法结合，降低子问题求解成本。 与一阶方法（如梯度法）结合，用于超大规模问题。 推广到更一般的矩阵锥规划，如二阶锥规划与半定规划的混合问题。