共查询到14条相似文献,搜索用时 265 毫秒
1.
针对一类非负整数二次规划问题,提出了一个新的分枝定界缩减方法.在这个方法里,使用了一个新的超矩形二分技术和一个新的线性规划松弛定下界技术,同时为了提高逼近程度和加快收敛速度,使用了超矩形缩减策略.数值结果表明所提出的算法是可行的和有效的. 相似文献
2.
3.
4.
5.
本文提出了一个求不定二次规划问题全局最优解的新算法.首先,给出了三种计算下界的方法:线性逼近法、凸松弛法和拉格朗日松弛法;并且证明了拉格朗日对偶界与通过凸松弛得到的下界是相等的;然后建立了基于拉格朗日对偶界和矩形两分法的分枝定界算法,并给出了初步的数值试验结果. 相似文献
6.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献
7.
解带有二次约束二次规划的一个整体优化方法 总被引:1,自引:0,他引:1
在本文中,我们提出了一种解带有二次约束二次规划问题(QP)的新算法,这种方法是基于单纯形分枝定界技术,其中包括极小极大问题和线性规划问题作为子问题,利用拉格朗日松弛和投影次梯度方法来确定问题(QP)最优值的下界,在问题(QP)的可行域是n维的条件下,如果这个算法有限步后终止,得到的点必是问题(QP)的整体最优解;否则,该算法产生的点的序列{v^k}的每一个聚点也必是问题(QP)的整体最优解。 相似文献
8.
9.
本文提出了一种求解带二次约束和线性约束的二次规划的分支定界算法.在算法中,我们运用Lipschitz条件来确定目标函数和约束函数的在每个n矩形上的上下界,对于n矩形的分割,我们采用选择n矩形最长边的二分法,同时我们采用了一些矩形删除技术,在不大幅增加计算量的前提下,起到了加速算法收敛的效果.从理论上我们证明了算法的收敛性,同时数值实验表明该算法是有效的. 相似文献
10.
一个解凸二次规划的预测-校正光滑化方法 总被引:1,自引:0,他引:1
本文为凸二次规划问题提出一个光滑型方法,它是Engelke和Kanzow提出的解线性规划的光滑化算法的推广。其主要思想是将二次规划的最优性K-T条件写成一个非线性非光滑方程组,并利用Newton型方法来解其光滑近似。本文的方法是预测-校正方法。在较弱的条件下,证明了算法的全局收敛性和超线性收敛性。 相似文献
11.
12.
13.
14.
Hong-Xuan Huang Panos M. Pardalos Oleg A. Prokopyev 《Computational Optimization and Applications》2006,33(2-3):187-208
In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations
we describe four different kinds of strategies for estimating lower bounds of the objective function, which can be integrated
into a branch and bound algorithm for solving the quadratic binary programming problem. We also give a theoretical explanation
for forcing rules used to branch the variables efficiently, and explore several properties related to obtained subproblems.
From the viewpoint of the number of subproblems solved, new strategies for estimating lower bounds are better than those used
before. A variant of a depth-first branch and bound algorithm is described and its numerical performance is presented. 相似文献