AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs¶

会议: NeurIPS 2026
arXiv: 2609.30088
OpenReview: https://openreview.net/forum?id=sSAcXhJXvH
领域: 优化/理论
关键词: 线性硬约束满足, 采样Kaczmarz-Motzkin方法, 动态图优化, 乔列斯基更新, 异构图神经网络

一句话总结¶

针对动态图结构线性硬约束优化中传统投影与采样开销巨大的瓶颈，AT-SKM-Net 将增量低秩乔列斯基更新与拓扑感知异构 GNN 引导的有效集混合采样相结合，在严格保证零约束违验的前提下实现 2.95× 至 7.29× 的端到端投影加速。

研究背景与动机¶

在电网调度、交通流控制以及管网传输等关键物理基础设施中，图结构优化问题构成了自动化决策的核心支柱。这类实际工程场景面临着严苛的双重挑战：一方面，系统状态受物理守恒定律和设备运行安全极限的支配，决策变量必须严格满足线性等式与不等式硬约束，任何微小的越限都可能引发级联故障；另一方面，实际网络处于高度动态变化中，电力线路的突发开断或管网拓扑的瞬时切换会频繁改变约束流形，迫使求解器必须在毫秒级时限内完成可行解生成与动作下发。

为了突破传统运筹求解器在面临大规模网络时计算耗时高、难以满足实时控制的瓶颈，深度学习近似求解器成为近年来的研究热点。然而，现有的端到端神经网络无法直接保证输出的物理可行性：基于拉格朗日乘子罚项的软约束方法缺乏硬性安全保障，极易产生致命越限；基于可微优化层或交替投影的硬约束方法，往往需要求解高维凸二次规划子问题，计算开销随网络规模呈爆炸式增长。近期提出的可训练采样卡兹马兹-莫茨金网络（T-SKM-Net）通过零空间投影结合随机 SKM 迭代，成功实现了严格满足线性等式和不等式的端到端训练。但在动态拓扑场景下，T-SKM-Net 暴露出两大根本性计算瓶颈：每次拓扑摄动都需要重新对等式约束矩阵进行全局奇异值分解（SVD），带来 \(\mathcal{O}(n^3)\) 的立方级重构开销；在不等式约束迭代阶段，传统方法采用无偏均匀采样，而实际系统解往往仅由极少数有效约束（Active Constraints）决定，导致海量计算预算被浪费在远离边界的冗余松弛约束上。

针对上述两阶段的结构性冗余，本文的核心切入点在于将动态图优化的物理拓扑先验显式引入约束校正流水线：线路开断引起的约束变化本质上是低秩摄动，而高维多面体内部的有效边界具有极强的空间稀疏性。核心 idea：将低秩摄动下的增量乔列斯基更新与异构 GNN 预测的紧致有效集混合采样深度协同，在保证等式投影由 \(\mathcal{O}(n^3)\) 降至 \(\mathcal{O}(n^2)\) 的同时将不等式迭代收缩至局部活跃流形，实现严格零违验的超线性端到端加速。

方法详解¶

整体框架¶

AT-SKM-Net 接收包含动态拓扑摄动的图优化实例，端到端输出严格满足物理硬约束的可行解。整个流水线分为神经预测热启动、等式约束低秩增量投影、以及有效集引导的不等式零空间 SKM 迭代三大阶段。首先，拓扑感知异构图神经网络（HGNN）对动静态参数进行解耦编码，回归出原始决策变量的初始热启动候选解，并并行输出所有约束的活跃概率打分；随后，针对拓扑变动诱发的等式约束低秩摄动，算法执行乔列斯基增量更新维护三角分解因子，通过两次高效的三角代换将热启动解拉回等式可行流形，并利用豪斯霍尔德变换瞬时更新零空间正交基；最后，在等式约束诱导的低维零空间中，算法基于预测活跃度执行探索-利用混合采样，聚焦于高违验概率的边界约束完成 SKM 投影修正，最终合并输出完全可行的最优解。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入: 动态摄动图实例与约束矩阵"] --> B["拓扑感知异构GNN编码与预测<br/>动静态特征解耦 + 结构归一化"]
    B --> C["输出解耦表征与双头预测<br/>热启动变量 + 约束活跃概率分布"]
    C --> D["低秩摄动乔列斯基增量更新<br/>秩1更新/降秩维护三角因子 + 两次前向后向代换"]
    D --> E["零空间正交基高效维护<br/>豪斯霍尔德反射旋转 + 纠偏向量对齐"]
    E --> F["有效集引导的混合采样不等式SKM<br/>利用概率聚焦边界 + 均匀探索兜底全局收敛"]
    F --> G["输出严格物理硬约束可行解<br/>零等式违验与零不等式违验"]

关键设计¶

1. 低秩摄动增量乔列斯基更新与零空间基维护：将等式投影从 \(\mathcal{O}(n^3)\) 彻底降至 \(\mathcal{O}(n^2)\)

在动态图优化中，偶发的线路故障或重连仅会引起图拉普拉斯矩阵或关联矩阵局部的行/列变动。若沿用 T-SKM-Net 的全量奇异值分解（SVD），每次摄动都需要付出庞大的三次幂耗时。为此，AT-SKM-Net 将拓扑摄动建模为等式矩阵的秩一变化 \(\tilde{\mathbf{C}}=\mathbf{C}+\mathbf{u}\mathbf{v}^\top\)。这一摄动直接诱导其对称正定格拉姆矩阵（Gram Matrix）\(\mathbf{G}=\mathbf{C}\mathbf{C}^\top\) 发生对称秩二摄动：

\[\tilde{\mathbf{G}}=\mathbf{G}+\frac{1}{2}(\mathbf{u}+\mathbf{m})(\mathbf{u}+\mathbf{m})^\top-\frac{1}{2}(\mathbf{u}-\mathbf{m})(\mathbf{u}-\mathbf{m})^\top\]

其中辅助向量 \(\mathbf{m}=\mathbf{C}\mathbf{v}+\frac{\|\mathbf{v}\|_2^2}{2}\mathbf{u}\)。算法完全避免了显式构造新矩阵 \(\tilde{\mathbf{G}}\)，而是直接对原有的下三角乔列斯基因子 \(\mathbf{L}\)（满足 \(\mathbf{G}=\mathbf{L}\mathbf{L}^\top\)）依次调用标准的秩一增加（Rank-1 Update）与秩一削减（Rank-1 Downdate），得到更新后的三角因子 \(\tilde{\mathbf{L}}\)。在残差投影时，显式求逆操作被直接转化为两次计算复杂度为 \(\mathcal{O}(n_{\text{eq}}^2)\) 的前向与后向三角代换 \(\tilde{\mathbf{L}}\mathbf{k}=\tilde{\mathbf{C}}\mathbf{x}_0-\mathbf{d}\) 与 \(\tilde{\mathbf{L}}^\top\mathbf{y}=\mathbf{k}\)，投影解直接写作 \(\tilde{\mathbf{x}}_{\text{eq}}=\mathbf{x}_0-\tilde{\mathbf{C}}^\top\mathbf{y}\)。针对后续 SKM 迭代所需的零空间正交基 \(\tilde{\mathbf{Z}}\)，算法采用豪斯霍尔德变换构造正交反射算子 \(\mathbf{H}\)，将原基底 \(\mathbf{Z}\) 旋转至使后 \(n-m-1\) 个维度完全正交于摄动方向 \(\mathbf{v}\)，仅对第一列使用已维护的 \(\tilde{\mathbf{L}}\) 进行轻量修正即可完成正交化更新。为了遏制连续拓扑更新在单精度浮点运算下累积的数值不稳定，模型进一步引入自适应尺度重缩放，使中间更新向量范数严格平衡，消除了高阶故障场景下的数值失效。

2. 预测有效集引导的探索-利用混合采样：将收敛依赖从全局霍夫曼常数压缩至局部紧致流形

高维线性不等式约束多面体 \(\mathcal{P}=\{\mathbf{x} \mid \mathbf{A}\mathbf{x} \le \mathbf{b}\}\) 在最优解附近的几何性质高度稀疏，绝大多数约束处于严格松弛（Slack）状态，仅有极少数紧约束（Binding / Active Constraints）\(\mathcal{A}^*\) 起作用。传统 SKM 方法在全局 \(m\) 个约束中盲目均匀抽样，抽中有效约束的概率极低，收敛极度迟缓。AT-SKM-Net 提出了一种预测有效集驱动的自适应采样机制。设神经网络输出各不等式约束的无量纲激活对数几率 \(\mathbf{z}\)，全局 Softmax 归一化后得到活跃概率分布：

\[p_i = \frac{\sigma(z_i)}{\sum_{j=1}^m \sigma(z_j)}, \quad \forall i \in \{1,\dots,m\}\]

在每轮 SKM 批次大小为 \(\beta\)、混合比例为 \(\rho \in (0,1)\) 的迭代中，采样集合拆解为互补的两部分：利用分支 \(\tau_{\text{learn}}\) 依据概率分布 \(\mathbf{p}\) 加权抽取 \(\lfloor\rho\beta\rfloor\) 个索引，直接对齐高置信度紧约束候选集 \(\hat{\mathcal{A}}\)；探索分支 \(\tau_{\text{unif}}\) 则从剩余全集中无偏均匀抽取 \(\beta - \lfloor\rho\beta\rfloor\) 个索引，作为算法的安全冗余兜底。理论分析严格证明：只要保留均匀探索成分（\(\rho < 1\)），算法就享有严格的全局期望线性收敛保证；而在局部线性区域内，当预测候选集完整覆盖真实有效集（\(\mathcal{A}^* \subseteq \hat{\mathcal{A}}\)）且保持高度紧凑（\(|\hat{\mathcal{A}}| \ll m\)）时，单步误差收敛率的压缩界从依赖全局全量约束数 \(m\) 及全局霍夫曼常数 \(\mathcal{H}^2(\mathbf{A})\)：

\[\mathbb{E}[\|\mathbf{e}_{k+1}\|^2] \le \left(1 - \frac{1}{m \cdot \mathcal{H}^2(\mathbf{A})}\right)\|\mathbf{e}_k\|^2\]

大幅跃升为由紧凑子集规模 \(|\hat{\mathcal{A}}|\) 及有效子矩阵最小非零奇异值 \(\sigma_{\min}^2(\mathbf{A}_{\mathcal{A}^*})\) 决定的超速收敛率：

\[\mathbb{E}[\|\mathbf{e}_{k+1}\|^2] \le \left(1 - \frac{\sigma_{\min}^2(\mathbf{A}_{\mathcal{A}^*})}{|\hat{\mathcal{A}}|}\right)\|\mathbf{e}_k\|^2\]

3. 拓扑感知的动静态解耦异构 GNN：保留边级约束并实现跨摄动泛化

为了准确捕捉节点级功率平衡与边级线路热极限的异构特性，模型构建了异构二部图计算体系，将节点与边建模为独立的表征实体，打破了传统同质 GNN 将边特征平滑吸收至节点所导致的耦合约束判别力退化问题。针对拓扑动态演变时的泛化难题，模型将输入特征显式解耦为决定约束系数矩阵结构的不变静态几何拓扑参数 \(\mathbf{z}_{\text{stat}}\)，以及决定约束边界向量的动态负荷运行条件 \(\mathbf{z}_{\text{dyn}}\)。在多层异构消息传递之间，设计了结构感知自适应特征归一化层：

\[\mathbf{h}^{(l+1)} = \gamma(\mathbf{h}^{(l)}, \mathbf{z}_{\text{stat}}) \odot \frac{\mathbf{h}^{(l)} - \mu}{\sigma} + \beta(\mathbf{h}^{(l)}, \mathbf{z}_{\text{stat}})\]

将深层动态隐藏状态与全局物理拓扑条件强绑定，确保预测解在突发断线拓扑下依然保持良好的结构物理自洽性。主干抽取出的深度表征接入回归头与分类头，前者输出等式投影的初始热启动坐标，后者通过焦点损失函数（Focal Loss）对长尾不平衡的约束活跃性给出极具辨识度的打分。

损失函数与训练策略¶

网络训练采用回归与分类联合的多任务复合损失函数。针对决策变量回归，模型沿用投影前后的加权均方误差以兼顾空间映射与物理流形对齐：\(\mathcal{L}_{\text{reg}} = 0.9 \cdot \text{MSE}(\hat{\mathbf{y}}_{\text{pre}}, \mathbf{y}) + 0.1 \cdot \text{MSE}(\hat{\mathbf{y}}_{\text{proj}}, \mathbf{y})\)。针对真实有效约束样本极端稀缺的正负样本失衡痛点，分类头采用参数为 \(\gamma=2.0\)、\(\alpha=0.5\) 的二值焦点损失函数 \(\mathcal{L}_{\text{focal}}\)。整体训练目标定义为 \(\mathcal{L}_{\text{total}} = \mathcal{L}_{\text{reg}} + \lambda(t) \cdot \mathcal{L}_{\text{cls}}\)，其中平衡权重 \(\lambda(t)\) 在前 40 个 epoch 中从 0 线性增加至 1，使模型在前期先充分建立原始特征映射回归能力，后期平滑过渡至精细有效约束分类。当缺乏高保真商业求解器生成真实标签时，框架支持迁移学习配合伪标签自监督迭代机制，仅依赖模型自我纠偏的 SKM 投影产物即可完成自适应微调。

实验关键数据¶

主实验¶

在包含突发 N-1 线路开断故障的 IEEE 57-Bus、118-Bus 及 300-Bus 安全约束直流最优潮流（N-1 SC DC-OPF）基准测试中，AT-SKM-Net 与传统内点法求解器（PyPower）、无约束深度学习模型（标准 NN、纯 HGNN）、带等式投影的可微优化方法（DC3）以及原始 T-SKM-Net 进行了全面对比。下表呈现了不可见拓扑场景下的求解耗时、迭代轮数与物理硬约束违验表现：

测试系统规模	方法	端到端总耗时 (ms)	SKM 迭代轮数 (均值 / 最大)	SKM 耗时 (ms)	SKM 相对加速比	最优性间隙 (%)	最大等式违验	最大不等式违验
IEEE 57-Bus (\(n=64\), \(n_{\text{eq}}=58\), \(n_{\text{ineq}}=174\))	PyPower NN HGNN DC3 T-SKM-Net AT-SKM-AC (本文)	14.785 0.048 4.735 6.278 5.831 5.009	- - - - 6.93 (148) 1.42 (11)	- - - - 1.096 0.274	- - - - 1.00× 4.00×	0.00 / 0.00 0.17 / 5.38 0.07 / 0.06 0.01 / 0.01 0.01 / 0.01 0.01 / 0.01	0 / 0 24.77 / 53.07 17.52 / 5.16 0 / 0 0 / 0 0 / 0	0 / 0 0.10 / 192.71 0.06 / 0.04 0.07 / 0.05 0 / 0 0 / 0
IEEE 118-Bus (\(n=172\), \(n_{\text{eq}}=119\), \(n_{\text{ineq}}=480\))	PyPower NN HGNN DC3 T-SKM-Net AT-SKM-AC (本文)	31.557 0.057 6.938 8.040 10.251 8.060	- - - - 34.60 (141) 15.68 (57)	- - - - 3.313 1.122	- - - - 1.00× 2.95×	0.00 / 0.00 0.14 / 1.48 0.02 / 0.02 0.02 / 0.02 0.03 / 0.03 0.03 / 0.03	0 / 0 72.59 / 93.21 61.06 / 67.36 0 / 0 0 / 0 0 / 0	0 / 0 0.03 / 664.11 0.01 / 0.05 0.01 / 0.01 0 / 0 0 / 0
IEEE 300-Bus (\(n=369\), \(n_{\text{eq}}=301\), \(n_{\text{ineq}}=960\))	PyPower NN HGNN DC3 T-SKM-Net AT-SKM-AC (本文)	64.398 0.078 9.390 16.138 18.382 10.623	- - - - 24.72 (285) 3.69 (9)	- - - - 8.992 1.233	- - - - 1.00× 7.29×	0.00 / 0.00 0.06 / 0.37 0.07 / 0.07 0.10 / 0.10 0.11 / 0.11 0.11 / 0.11	0 / 0 2.00e3 / 9.44e3 64.61 / 62.36 0 / 0 0 / 0 0 / 0	0 / 0 1.53e3 / 8.52e3 537.66 / 0.09 0.47 / 0.47 0 / 0 0 / 0

消融实验¶

为了独立厘清有效集采样加速与乔列斯基投影更新对整体效能的贡献，作者在 IEEE 57、118 及 300 节点系统上对消融变体进行了严格剖析：AT-SKM-A（仅引入有效集预测采样，保留全量 SVD 重分解）、AT-SKM-C（仅引入乔列斯基增量更新，保留无偏均匀采样）以及完整模型 AT-SKM-AC。

测试系统	模型配置	等式投影耗时 (ms)	等式阶段加速比	不等式迭代均值 (最大值)	不等式阶段耗时 (ms)	SKM 层总耗时 (ms)	端到端 SKM 加速比
IEEE 57-Bus	基线 T-SKM-Net 仅有效集采样 (AT-SKM-A) 仅乔列斯基更新 (AT-SKM-C) 完整模型 (AT-SKM-AC)	0.56 ± 0.34 0.56 ± 0.34 0.18 ± 0.02 0.18 ± 0.02	1.00× 1.00× 3.11× 3.11×	6.93 (148) 1.42 (11) 6.93 (148) 1.42 (11)	0.41 ± 1.20 0.06 ± 0.07 0.41 ± 1.20 0.06 ± 0.07	1.096 0.467 0.618 0.274	1.00× 2.35× 1.77× 4.00×
IEEE 118-Bus	基线 T-SKM-Net 仅有效集采样 (AT-SKM-A) 仅乔列斯基更新 (AT-SKM-C) 完整模型 (AT-SKM-AC)	1.56 ± 0.06 1.56 ± 0.06 0.30 ± 0.03 0.30 ± 0.03	1.00× 1.00× 5.20× 5.20×	34.60 (141) 15.68 (57) 34.60 (141) 15.68 (57)	2.13 ± 2.51 1.01 ± 1.38 2.13 ± 2.51 1.01 ± 1.38	3.313 2.411 2.004 1.122	1.00× 1.37× 1.65× 2.95×
IEEE 300-Bus	基线 T-SKM-Net 仅有效集采样 (AT-SKM-A) 仅乔列斯基更新 (AT-SKM-C) 完整模型 (AT-SKM-AC)	7.65 ± 1.54 7.65 ± 1.54 0.70 ± 0.02 0.70 ± 0.02	1.00× 1.00× 10.92× 10.92×	24.72 (285) 3.69 (9) 24.72 (285) 3.69 (9)	2.07 ± 4.59 0.32 ± 0.20 2.07 ± 4.59 0.32 ± 0.20	8.992 7.874 2.789 1.233	1.00× 1.14× 3.22× 7.29×

关键发现¶

规模放大下的瓶颈转移与超线性协同：在 57 节点小规模网络中，不等式约束迭代搜索是主要耗时源，有效集预测将平均迭代步数降低 80% 并带来 2.35× 加速；而在 300 节点大规模网络中，瓶颈彻底转移至高维矩阵代数重分解，乔列斯基更新将等式投影耗时从 7.65 ms 压减至 0.70 ms（单阶段加速达 10.92×）。双模块协同产生了超线性的端到端叠加效应（总加速比 7.29× 显著超越两模块孤立加速的乘积 \(1.14 \times 3.22 = 3.67\)）。
长尾极端用例的高效抑制：在 300 节点系统中，基线 T-SKM-Net 的最差迭代步数高达 285 轮，而 AT-SKM-Net 成功将最大迭代步数压制到 9 轮以内，且在高负荷压力测试下（负荷区间偏移至 \([1.0, 1.2]\)）依然将最大迭代轮数稳定在 28 轮以内，极大改善了实时控制任务的尾部延迟保障。
预测误差的不对称性鲁棒机理：在针对预测失真的消融扰动实验中，虚警率（将非活跃约束误判为活跃）的增加仅温和稀释采样概率，而漏警率（漏判真实活跃约束）对迭代收敛的损害极为显著。HGNN 分类器在所有系统上均保持了 98% 以上的召回率，完美契合了该非对称鲁棒性边界。

亮点与洞察¶

物理拓扑摄动的代数映射转化：将动态网络结构中物理开断诱导的局部约束跳变精确建模为格拉姆矩阵的对称秩二摄动，绕开了全局重构，将经典矩阵更新技巧与现代几何深度学习流水线无缝焊接。
带安全兜底的自适应维度压缩：混合采样策略以理论为锚，既通过神经网络注意力先验将搜索流形从全空间压缩到活跃面，又通过保留极小比例的均匀随机探索消除深度学习盲区，在保持理论收敛保证的同时收割了极大的经验加速。
可迁移的自监督伪标签微调框架：摆脱了对昂贵求解器全集标签的绝对依赖，通过已投影纠偏可行解作为伪标签自我迭代，展示了将该框架推广至缺乏高精度求解器的超大规模复杂工业系统的可能。

局限与展望¶

高阶多重拓扑故障下的累积数值风险：尽管自适应尺度重缩放显著提升了单精度数值稳定性，但在面对 \(N-3\) 以上极高阶并发开断时，连续秩一降秩更新在极端病态矩阵下仍存在分解退化风险，未来需探索基于部分对角重置的在线误差恢复机制。
非线性物理约束扩展的适用边界：当前方法立足于直流潮流等线性化硬约束模型。对于交流潮流（AC-OPF）等高阶非线性非凸物理约束流形，如何构造动态自适应正交投影切空间仍是未解的技术挑战。

评分¶

新颖性: ⭐⭐⭐⭐☆ [将物理拓扑低秩摄动特性与活跃流形采样先验自然融合进 SKM 硬约束流水线，理论与算法设计扎实优雅]
实验充分度: ⭐⭐⭐⭐⭐ [覆盖 RGG 合成图、多规模 N-1 SC DC-OPF 及天然气管网系统，消融分析涵盖扰动鲁棒性、高载荷与伪标签迁移]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严丝合缝，动机阐述自然流畅，方法与实验细节极其详实清晰]
价值: ⭐⭐⭐⭐⭐ [攻克了深度求解器落地高安全等级实时能源调控系统的硬约束与动态拓扑双重咽喉问题，工业价值显著]