点击数: 更新日期: 2022-12-20
中文题目：非凸灵敏性广义Benders分解
论文题目：Nonconvex sensitivity-based generalized Benders decomposition
录用期刊：Journal of Global Optimization (JCR Q2)
原文DOI：https://doi.org/10.1007/s10898-022-01254-9
录用/见刊时间：2022-11-16/2022-11-29
作者列表：
1） 林嘉奖 中国石油大学（北京）信息科学与工程学院 自动化系教师
2） 许锋 中国石油大学（北京）信息科学与工程学院 自动化系教师
3） 罗雄麟 中国石油大学（北京）信息科学与工程学院 自动化系教师
背景与动机:
当统筹优化所有层级的决策变量时，集成优化问题可能包含多种类型的决策变量。这时的集成优化问题一般具有可分解结构，因此通常会用GBD算法求解，特别是复杂变量为整型变量时。但是GBD算法只有对于凸问题才能保证收敛到最优解。对于一般的非凸问题，GBD算法甚至不能保证收敛到局部极小点。对于特定的非凸问题，可以对非凸函数进行凸松弛，得到其代理模型，然后再对代理模型使用GBD算法求解。虽然GBD算法能够保证得到代理模型的最优解，但是近似误差取决于代理模型和原始模型的接近程度。考虑到标准的NLP求解器可以保证求得一般伪凸问题的最优解，所以通用的分解算法应该能求得一般的可分伪凸问题的最优解。
设计与实现:
考虑以下的集成优化问题：
问题1：
其中f:X×Y->R和G:X×Y->Rm是连续可微函数；集合X和Y由下限和/或上限约束描述。假设y是复杂变量，x是普通变量。那么NSGBD算法如算法1和图1所述。
图1 NSGBD的算法流程图
本文通过增大病态Benders割的“斜率”来生成有效的下低估。通过构造支撑超平面的方法来逼近复杂变量的可行域。
NSGBD算法对于可分伪凸问题可以保证求得最优解。且在数值求解时，由于难以严格生成拐点处的Benders割，所以NSGBD算法对于可分拟凸问题一般也可以求得最优解。
实验结果及分析:
本节将NSGBD算法应用到非凸的双线性规划问题中：
该NLP问题xy空间的可行域如图2a所示。因为原问题是LP问题，所以可以用解析的方法求解，进而得到目标函数投影函数的解析表达式（9）式（如图2b所示）。
图2 NLP问题(8)：a) 可行域；b) v(y)
因为约束条件（8b）是非凸的，所以优化问题8是非凸的（图2b）。该优化问题的最优解是，最优目标函数值是。因为该优化问题是非凸的，所以无法由GBD算法求解。由图2a可知虽然的可行区域是非凸的，但是y的可行域是凸的，固定任意y时x的可行域也是凸的。虽然v(y)是非凸的，但是是拟凸的，即该问题满足可分拟凸条件。NSGBD算法在第10次迭代时收敛，算法收敛于和，其中，且除了y2(1)以外都是可行点。通过求解关于不可行点y2(1)的不可行最小化问题，可以得到新可行点y2(2)和y-空间可行域的支撑超平面。因为v(y)在处不可导，所以会在最优解附近振荡。第4、6和8次迭代得到的是错误的下界，所以相应的病态Benders割的“斜率”会被乘以γ以生成有效下界。
由本例可知，NSGBD算法能够很容易地处理可分拟凸问题。即使对于更一般的具有多个局部极小点的非凸问题，NSGBD算法也能保证得到KKT点，也可以与其他的全局算法结合使用。
通讯作者简介:
罗雄麟，博士生导师。北京人工智能学会理事会常务理事、北京自动化学会理事会理事。从事控制理论及应用、过程控制工程和过程系统工程等研究工作，同时从事炼油化工过程软测量仪表与先进控制、过程流程模拟与实时优化等技术开发与工程应用工作。主持和参加“六五”至“九五”国家重点科技攻关项目多项、“十五”国家863项目1项、国家自然科学基金项目5项（主持2项）、国家重点基础研究发展计划（973计划）项目1项，主持和参加省部级科研项目和炼油化工公司科技开发项目30多项。获省部级奖5次。出版专著3部，发表教学和科研学术研究论文490多篇，SCI、ISTP和EI检索收录380多篇次，获国家发明专利授权11项