共查询到16条相似文献,搜索用时 62 毫秒
1.
通过解线性规划问题,寻找包含原问题可行域的超矩形,利用剖分技术对这个超矩形进行分枝和收缩以减少算法的迭代次数,从而用线性规划松弛方法来确定原问题在每个小超矩形上的最优值的下界,提出一种新的带有二次约束的二次规划问题的收缩分枝定界算法,并证明了该算法是收敛的. 相似文献
2.
《合肥工业大学学报(自然科学版)》2021,44(1)
二次约束二次规划(quadratically constrained quadratic programming,QQP)问题目标函数和约束条件均是非凸的,是一类NP难问题,目前还没有通用的全局收敛准则,从而使得求该问题的全局最优解面临着严峻挑战。文章通过引入辅助乘积变量,将QQP问题等价地转化为带有乘积等式约束的非线性规划(nonlinear programming,NLP)问题;进而在NLP问题中利用二元均值不等式结合函数的性质松弛乘积等式约束后,产生QQP问题的带有辅助变量的松弛线性规划(relaxation linear programming,RLP)问题,由此确定QQP问题的全局最优值的下界,利用超矩形基于线性函数的缩减策略,以增强子超矩形的紧致删除能力;最后给出了该算法的收敛性分析,数值实验结果表明所提出的算法是可行且有效的。 相似文献
3.
考虑带有二次约束的一般二次规划问题的求解,当约束条件为非凸二次函数时,对原问题中的某个二次约束进行凸二次松驰,或在原问题的约束条件中增加一个球约束,使得原问题的可行域包含在松驰二次规划问题的可行域内。采用椭球剖分策略剖分可行域为小 椭球,用投影次梯度算法解松驰二次规划问题的拉格朗日对偶问题,从而获得原问题的一个下界。原问题最优值的一个上界可从迭代过程中的可行点得到,并在迭代过程中得到调整。该算法或在原问题最优值的一个上下界相同时终止,得到原问题的整体最优解;或产生一无限序列,其任一聚点都是原问题的整体最优解。 相似文献
4.
针对非凸二次约束二次规划(QCQP)问题,将问题中二次函数的凸函数部分保留,达到所得松弛规划的可行域更加紧致的目的,得到原问题更好的下界.利用正交变换的方法得到原问题的一个凸规划松弛模型,再利用分支定界算法求其全局最优解.根据问题的最优性和可行性原则,提出一种能整体删除或缩小算法迭代过程中产生的分割子区域的区域删减策略... 相似文献
5.
目的为求目标函数为一般二次函数的二次规划问题,提出一个新的加速算法。方法通过结合两个加速技巧,并将其置于分支定界算法框架下,给出一个新的全局优化算法。结果该方法可以有效地确定出不定二次规划问题的全局最优解。结论理论上证明了算法的收敛性,数值算例表明算法是有效可行的。 相似文献
6.
通过构造二次函数的线性下界函数给出非凸二次约束二次规划问题(QP)的松弛线性规划,提出分支定界算法,数值计算表明算法是有效可行的. 相似文献
7.
研究球约束二次规划问题 .将一般的球约束二次规划问题转化为球约束凸二次规划问题 ,并给出了该问题的KT点和全局最优解的计算方法 相似文献
8.
利用拉格朗目函数和L次微分的方法,研究了带有二次约束的一类特殊三次规划问题的全局最优性条件。首先刻画出该类三次规划问题的拉格朗日函数的抽象次微分,从而得到了带有二次约束的三次规划问题的全局最优性充分条件。最后举例说明如何利用本文所给出的全局最优性充分条件来判定当前可行解就是全局最优解。 相似文献
9.
带有二次约束的一些非凸二次规划问题的全局最优性条件 总被引:3,自引:1,他引:3
利用Z.Y.W u等人最近提出的一种新的研究全局优化问题的全局最优性条件的方法,研究了一些带有二次约束的非凸二次规划问题的全局最优性条件,得到了一些带有二次约束的非凸二次规划问题的全局最优性充分条件,同时也得到了一些无约束非凸二次规划问题的全局最优性充分条件,并证明了在一些特殊情况下,本文的一些结果与文献中的一些结论是一致的。在有些情况下,本文的有些结果还推广了现有文献中的一些结论。 相似文献
10.
研究了一类带有二次目标函数及二次等式约束的优化问题.假定约束是可行、规范的,对于目标函数为正定或半正定的情形,得到了全局最优解的充要条件. 相似文献
11.
给出一类多乘积问题(P)的全局优化方法.首先将(P)转化为其等价问题(Q),利用变量代换,把(Q)写成(EQ)形式,然后建立(EQ)松弛线性规划(RLEQ),通过求解一系列线性规划问题,不断更新最优值的上下界,证明了所给算法的收敛性,数值实验表明算法是可行的. 相似文献
12.
凸约束不定二次规划问题的分枝定界方法 总被引:1,自引:0,他引:1
针对凸约束不定二次规划问题,给出一个分枝界定方法。通过将凸约束不定二次规划问题等价地转化为凸凹规划问题,利用超矩形体的二分技术和锥剖分技术,在超矩形体上确定原问题的最优解,并进行了收敛性分析。 相似文献
13.
线性比式和问题的全局优化算法 总被引:3,自引:2,他引:1
为求解线性分式规划问题(P),提出一个分枝定界算法.首先通过转化技巧,导出问题(P)的等价问题(Q),然后利用线性化方法,得到(Q)的线性松弛规划问题(RLP).从而,初始非凸规划问题归结为一系列线性规划问题的求解.数值试验表明算法是可行的. 相似文献
14.
对广泛应用于金融、证券投资等实际问题中的带指数的多项式函数的极小值问题(P1)提出了一种有效的全局优化算法.从理论上证明了本算法的收敛性,数值实验表明提出的方法是可行和有效的. 相似文献
15.
线性分式规划全局最优解的确定性方法 总被引:1,自引:1,他引:0
针对分式规划问题的求解,给出一个确定性全局优化算法.首先将原问题转化为一个等价问题,然后利用线性化技巧,建立等价问题的松弛线性化问题.通过对可行域的不断剖分以及一系列松弛线性化问题的求解,逐步求得原问题的最优解.理论上证明了算法的收敛性,数值算例表明算法是可行的. 相似文献
16.
首先利用对数函数和指数函数的凹凸性构造目标函数的线性下界函数,从而建立问题(P)的松弛线性规划,然后给出求解问题(P)的分支定界算法。最后数值算例表明算法是可行的。 相似文献