二次约束二次规划问题的松弛定界算法研究

发布时间：2021-10-17 06:33

　　二次约束二次规划问题来源于科学与工程、经济与社会许多领域,如无线通信、网络安全、数据挖掘、图像处理、经济金融、生态环保等.二次约束二次规划问题一般都是N-P难问题,往往都有多个极值点,很难用最速下降法、牛顿法、共轭梯度法、拟牛顿法、罚函数方法等传统优化方法求出其全局最优解.因此,研究二次约束二次规划问题全局最优解的计算方法具有重要的理论意义和应用价值.本文针对非凸二次约束二次规划问题,给出了三个松弛定界技术和三种不同的分支方法,由此提出了求该问题全局最优解的三个分支定界算法,并进行了收敛性分析.数值实验表明所提出的算法都是可行的和有效的.具体内容如下:一是通过引入辅助乘积变量,将二次约束二次规划问题等价地转化为仅带有辅助变量和决策变量乘积的线性组合非线性规划问题,给出了辅助变量界松弛技术,同时给出了辅助变量空间中超矩形的中点二分法,引入了超矩形的基于线性函数和基于二次函数的缩减策略,以增强超矩形的紧致删除能力.由此提出了一个二次约束二次规划问题的辅助变量界松弛定界算法.二是仍然通过引入辅助乘积变量,将二次约束二次规划问题等价地转化为仅带有辅助变量和决策变量乘积的线性组合非线性规划问题;... 

【文章来源】：北方民族大学宁夏回族自治区

【文章页数】：69 页

【学位级别】：硕士

【部分图文】：

关于变量抛物线–直线围成的面积

北方民族大学2020届硕士学位论文第四章二次约束二次规划问题的决策变量界松弛定界算法图4.1关于变量抛物线–直线围成的面积用表示问题(QQP2())的当前最优解,对应的(RLP2())的最优解为(,),易知,∈.按以下形式的对=[,]进行剖分:Step1计算:=max{(,):=1,2,···,},if<14,then=+2;else=,endifStep2令′=(1,2,···,1,,+1,···,),′′=(1,2,···,1,,+1,···,).利用点′及′′的连线或是连线所在平面把分成两个超矩形1=[1,1],2=[2,2],则这两个子超矩形分别为:1=1∏=1[1,1]×[1,1]×∏=+1[1,1],2=1∏=1[2,2]×[2,2]×∏=+1[2,2].为了加快本章算法的收敛速度,这里同样采用2.4.2中基于线性约束的超矩形缩减技术.4.4算法的描述及收敛性证明首先,为了方便叙述本节所提出的算法,当算法迭代到第步时,有以下记号:–49–

【参考文献】：
期刊论文
[1]基于单纯形剖分确定非线性比式和问题全局解的新方法[J]. 汪春峰,刘三阳.  系统工程理论与实践. 2013(03)
[2]反凸规划的分枝定界方法[J]. 布和额尔敦,陈国庆,刘菊红.  运筹学学报. 2011(02)
[3]不定整数二次规划的一个新的分支定界算法[J]. 黎健玲,马林,王鹏.  工程数学学报. 2010(05)
[4]解带有二次约束非凸二次规划问题的一个分枝缩减方法(英文)[J]. 高岳林,尚有林,张连生.  运筹学学报. 2005(02)



本文编号：3441297