求线性比式和问题全局解的输出空间分枝定界算法

来源：计算数学杂志2022年第2期北京时间：

作者：张博, 高岳林

单位：1. 宁夏大学数学统计学院, 银川 750021;2. 北方民族大学数学与信息科学学院, 银川 750021;3. 宁夏智能信息与大数据处理重点实验室, 银川 750021

摘要：基于对p-1维输出空间进行剖分的思想,提出了一种求解线性比式和问题的分枝定界算法.通过一种两阶段转换方法得到原问题的一个等价问题,该问题的非凸性主要体现在新增加的p-1个非线性等式约束上.利用双线性函数的凹凸包络对这些非线性约束进行凸化,这就为等价问题构造了凸松弛子问题.将凸松弛子问题中的冗余约束去掉并进行等价转换,从而获得了一个比凸松弛子问题规模更小、约束更少的线性规划问题.证明了算法的理论收敛性和计算复杂性.数值实验表明该算法是有效可行的.

关键词：全局优化,线性比式和问题,分枝定界,输出空间,计算复杂性

基金资助：国家自然科学基金项目(11961001),宁夏高等教育一流学科建设资助项目(NXYLXK2017B09),北方民族大学重大专项(ZDZX201901)资助.