基于梯度展开点优化辅助的内部线性化增强方法

《Algorithms》：Enhancing Inner Linearizations Assisted by Gradient-Based Expansion Point Optimization

　　

非线性连续全局优化问题（NCOPs）广泛存在于工程与机器人等领域，分支定界（Branch & Bound）法是求解此类问题至全局最优的常用途径，常结合二分与过滤技术。该方法的关键在于在搜索早期识别可行解，以有效剪枝搜索树并避免不必要计算。以AbsTaylor策略为代表的内部线性松弛技术在识别可行域方面表现有效，但其严重依赖启发式选择的展开点（常为盒子中点），直接影响解质量与松弛成功率。研究人员提出一种新颖的基于梯度的策略，动态优化该展开点的选取。通过采用梯度下降（Gradient Descent）最小化仅在活跃约束上构造的均方误差（MSE）目标，系统性地将展开点从边界安全推离至严格可行的内部区域。为控制计算开销，研究人员在受限迭代预算下评估算法变体，具体引入用于热启动的点继承（point inheritance）策略，并比较批量（Batch）与增量（Incremental）梯度更新。在知名基准集上的实验表明，该基于梯度的方法降低了松弛失败概率，相比原始策略显著增强了剪枝效果与求解器整体效率。

研究背景方面，非线性连续全局优化问题（NCOPs）在机器人、车辆定位、传感器网络定位、最优轨迹规划、化工过程设计及神经网络形式化验证等领域广泛存在。区间分支定界（Interval Branch & Bound）求解器因能严谨处理浮点舍入误差并提供不可行证明与解认证而被普遍采用。该类求解器在搜索树每个节点构造盒子并评估目标区间，配合全局上界维护与剪枝。内部凸线性化方法（如X-Taylor）利用一阶泰勒展开在盒子角点构造内部多面体，但角点限制使其即便存在严格内部可行解也可能构造失败；AbsTaylor策略放宽展开点至盒子内任意点（常取中点），提升了内部区域构造概率，但静态中点选择在非凸或边界邻近场景下仍可能次优，导致松弛失败与剪枝乏力。因此，研究人员开展本项研究，旨在以数据驱动方式动态优化AbsTaylor中的展开点位置，从而提升内部线性松弛成功率与分支定界整体效率，论文发表于《Algorithms》。

主要关键技术方法方面，研究人员在IbexOpt全局优化器中实现所提梯度下降（GD）策略，基准实例取自COCONUT全局优化集合，筛选执行时间大于2秒且超时限定3600秒的40个实例，每实例跑10次取平均。核心方法包括：定义活跃约束集（区间上界非负），在其上构造均方误差（MSE）损失；以符号方式求约束函数值与梯度，采用固定学习率η=0.05；设迭代预算K∈{5,10,25}；展开点越界时用ProjectToBox算子按分量夹回盒子；初始化分标准中点重启与父节点点继承（warm-start）两种；更新方式分批量（Batch）平均全活跃约束梯度单步下降与增量（Incremental）逐约束顺序下降两类，均设单调改进早停。

研究结果方面，第4.1节评估批量更新+标准初始化，显示K=5/10/25时平均盒子数减少分别约5.91%、9.82%、12.37%，但CPU时间在K=25时转负；K=10兼顾剪枝与速度（平均时间降约4.83%）。第4.2节评估批量更新+点继承，K=5/10/25盒子削减约6.77%、11.45%、13.88%，K=10时间省约6.91%；深树问题（avion2、hs093）继承策略显著提速，但hs100等案例因父节点次优位置传播而退化。第4.3节增量更新+继承在K=5获平均盒子减5.95%、时间罚微乎其微，复杂边界（avion2）达79.20%减盒，但紧约束（hs113）因逐约束过冲致盒子增约50%。第4.4节汇总指出K=10为各范式最优平衡点；重剪枝选增量（K=25峰值削盒），重时效选批量+继承（K=10削盒并加速）。

讨论与结论翻译方面，研究人员提出基于梯度优化AbsTaylor展开点选取的新策略，通过对活跃约束最小化MSE将展开点推入严格可行内部。在K∈{5,10,25}下评估批量/增量与点继承变体，证实替代启发式中点可根本提升分支定界剪枝效率。增量更新在K=25获最大平均削盒（达79.20%于avion2）但伴轻微时间罚；批量+继承在K=10削盒约11.45%且净加速约6.91%，为最实用稳定配置；K=10跨范式皆优。未来工作可动态调K与η、按局部梯度幅值或区间宽做约束归一化、引入二阶信息或机器学习预测活跃约束。该研究为区间松弛框架提供了可扩展的梯度驱动增强方案。