共查询到16条相似文献，搜索用时 31 毫秒
1.
2.
对顶点覆盖问题的一种等价模型,利用一般的松弛方法,得到了一个半定规划松弛模型．通过引入算子hsvec,把这个等价模型进行提升,得到了一个强化半定规划松弛模型,并从理论上证明了所得到强化松弛模型能比一般松弛模型提供更好的下界,同时数值实验也证明了这一点． 相似文献
3.
对二次背包问题提出两种半定规划松驰SDP1和SDP2,从理论上证明了SDP2能给出更好的上界,数值实验也说明了这点。 相似文献
4.
半定规划的一种新算法 总被引：2，自引：2，他引：0
将半定规划转化为一个变分不等式,在满足单调性的假设下,提出了一种新算法,并给出算法的收敛性分析,该算法简便易行且具有直观的几何意义,数值实验结果表明此方法是有效的。 相似文献
5.
半定规划是线性规划的推广,内点算法是目前最有效的求解半定规划算法。研究了基于内点算法的半定规划的灵敏度分析,即右端向量和费用矩阵变化时对可行解的影响,并给出了在单步内点迭代时,保持可行域内和近似最优解时的参数变化的界限,以及一般情形的灵敏度分析。 相似文献
6.
构造半定规划的一个扰动问题.相比半定规划的标准问题,该扰动问题具有严格可行解.这对于设计和分析半定规划的不可行内点算法具有重要作用. 相似文献
7.
半定规划有着广泛的应用领域,例如系统论,控制论,模式识别等领域.为了更好地求解这些领域中遇到的半定规划问题,给出了半定规划的原始对偶预估校正内点算法.该算法由不同的搜索方向构成,利用牛顿法得到了3个搜索方向,数值实验表明:基于NT方向的算法最为稳健. 相似文献
8.
基于凝聚函数的半定规划光滑化牛顿法 总被引：1，自引：0，他引：1
针对线性半定规划不可微的问题,将最大熵函数原理应用到半定规划互补问题中,得到扩充的凝聚函数。结合光滑化思想,将半定规划问题的最优条件转化为一个等价的光滑方程组,构造出半定规划的光滑化牛顿法,并证明了该算法的全局收敛性和局部二阶收敛性。 相似文献
9.
史娜;潘晋孝;穆学文 《中北大学学报(自然科学版)》2010,31(6):543-547
半定可行性问题是运筹研究领域中一个很重要的问题.针对此问题提出了一种使用多割的分析中心割平面算法.该算法改进了使用单割的分析中心割平面算法,在解决实际问题时比较有效.通过对该算法收敛性的讨论,证明了该算法是二次收敛的. 相似文献
10.
利用半定规划松驰法对无线传感器网络进行初始定位。由于半定规划松驰内点法产生的解具有高秩性,因此结合梯度局部搜索法,进一步改善半定规划松驰解。计算机仿真结果证明：半定规划松驰方法具有良好的可行性和有效性。 相似文献
11.
研究了工件可拒绝排序问题．考虑目标函数是拒绝费用与带权总完工时间之和,应用线性规划松弛方法设计了近似算法,当工件之间没有优先关系时得到3-近似算法,当工件之间具有优先关系时得到4-近似算法. 相似文献
12.
带预处理的半定规划多用户检测器 总被引：1，自引：1，他引：0
基于多用户检测问题的二次整数规划模型,提出了一种带预处理的半定规划多用户检测方法．该方法利用预处理方法把多用户检测问题的模型等价为一个规模较小的二次整数规划模型。给出简化模型的半定规划松弛,结合随机扰动方法得到多用户检测问题的次优解．这种方法改善了用户多时半定规划方法误码率高的状况,同时也缩短了直接利用半定规划方法的检测时间． 相似文献
13.
研究了工件可拒绝排序问题.考虑目标函数是拒绝费用与带权总完工时间之和,应用线性规划松弛方法设计了近似算法,当工件之间没有优先关系时得到3-近似算法,当工件之间具有优先关系时得到4-近似算法. 相似文献
14.
为有效求得背包约束条件下下模函数的解,往往采取不同的方式,以获得最优解,但更多情况下无法找出其精确最优解。针对这个问题,选取两种不同的方法,先对所求解通过添加变量进行约束,再应用贪婪算法,以获得该问题的最优近似解;利用线性规划的知识,分析最大化非减下模集函数在单背包约束下的近似算法,得出当σ>0.19时,算法(III)的性能保证大于0.732,并且随着σ的增大而接近最优解,算法(III)中的参数θ对某种大规模情形将不起作用。 相似文献
15.
一类全局优化问题的线性松弛方法 总被引：1，自引：0，他引：1
对一类全局优化问题(P)提出了一种线性松弛方法.利用线性化技术建立了问题(P)的松弛线性规划(RLP),通过对(RLP)可行域的细分以及一系列(RLP)的求解过程,提出算法收敛问题(P)全局最优解.数值实验表明,该方法是可行的. 相似文献
16.
张峰 《上海第二工业大学学报》2009,26(1):1-5
讨论了具有就绪时间与先后约束的工件可拒绝排序,其目标函数是所拒绝加工工件的总拒绝费用与加工工件的带权总完工时间之和。应用线性规划松弛方法设计了近似算法,得到（3＋√3）-近似算法。 相似文献