共查询到19条相似文献,搜索用时 115 毫秒
1.
李跃明 《南京邮电大学学报(自然科学版)》1987,(2)
本文介绍一种新的线性规划多项式算法——Karmarkar算法,并演示了它的产生过程。然后,给出了一种Karmarkar的扩充算法,这种算法在不要求已知原问题的最优值的情况下同时产生原问题与其对偶问题的解。 相似文献
2.
艾文宝 《西安交通大学学报》1998,32(4):80-83
对标准线性规划问题给出了一个新的多项式时间的投影内点算法.该算法无需事先知道目标函数的一个初始下界,因此它优于同为投影类的ToddBurel算法和Gay算法,是目前为止投影类内点算法方面的最好结果. 相似文献
3.
能否把一个非线性规划的算法进行改造后用于线性规划,使算法在解线性规划时的时间为问题大小的一个多项式阶,这是一个很有意义的研究方向。为了讨论这种改进,就要对本来是针对连续优化问题的算法以及问题本身的表达引入组合特性。本文通过对目前存在的线性规划的多项式时间算法的组合特性的分析,提出对一般算法引入组合特性的可能途径。这种途径主要是利用广义的二分搜索的一些性质。文中还分析了Karmarkar算法的非线性收敛性质。 相似文献
4.
给出了求解凸二次规划的一种二阶Mehrotra型预估一校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O(n^3/2log(x^0)^TS^0/ε). 相似文献
5.
给出了求解凸二次规划的一种二阶Mehrotra型预估-校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O{n3/2log((x0)Ts0)/ε}。 相似文献
6.
吉训仁 《中山大学学报(自然科学版)》1997,(1)
对一类线性规划问题提出了一个强多项式算法.此算法可进行双向搜索.可行解集、目标函数的两个目标值以及相应的最优解,全部可行基与最优基可以一步求得,无需迭代.算法的复杂性为O(n3+n2+n),其中n为线性规划问题变量的个数 相似文献
7.
框式线性规划的不可行内点算法 总被引:1,自引:0,他引:1
王浚岭 《三峡大学学报(自然科学版)》2001,23(2):169-174
对框式线性规划提出了一个原始-对偶不可行内点算法,并证明了该算法的迭代复杂性为多项式时间性. 相似文献
8.
9.
根据目标函数的梯度向量在可行域内低维界面上的投影,给出线性规划逐维选优(强多项式)算法的表上作业法,并且用若干具体实例详细描述了表上作业法。 相似文献
10.
11.
指出“线性规划的符号跟踪算法”实际上是第一阶段单纯形算法的一种变式,所获得的初始基有4种可能情况,并通过反例进行了说明。由此初始基出发,为使符号跟踪算法能正常运行下去,对该算法的步骤作了修正和补充。为了进一步验证符号跟踪算法的计算性能,通过MATLAB编程在计算机上实现大规模数值试验。结果表明,与经典单纯形算法相比,符号跟踪算法平均每次迭代花费更多的执行时间,计算效率较低。 相似文献
12.
吴福祥 《北京化工大学学报(自然科学版)》1993,(2)
线性互补问题的投影Jacobi松弛算法应用于求解不等式约束的二次规划问题,对称半正定的二次规划问题由K-T条件可以转化为P_0-矩阵的非对称线性互补问题(LCP),通过求解带扰动项的P-矩阵的非对称线性互补问题得到二次规划的最优解。最后给出一些数值结果。 相似文献
13.
Zhao对线性规划提出了一种基于邻近度量函数最小值的宽邻域预估-校正算法, 并证明了算法的多项式复杂性。基于他的思路,将此方法拓展到凸二次规划,设计了一种新的基于邻近度量函数最小值的宽邻域预估-校正算法。由于新算法的迭代方向向量Δx,Δs不再满足正交性,因此算法的收敛性分析不同于线性规划的情形,同时也证明了新算法具有 已知的最好迭代复杂性Onln(x0)Ts0ε,初步数值实验验证了算法的有效性。 相似文献
14.
15.
提出了公用工程系统参数优化的改进模型,结合算例给出了详细的建模方法,模型包含非凸线性费用目标函数和复杂非线性约束方程,在传统优化算法难以求解的情况下,采用改进的连续化遗传算法获得了理想的结果。 相似文献
16.
17.
18.
19.
针对内点方法在理论和实践之间存在着计算效果好的算法在理论上具有较差复杂性的矛盾,提出一种求解线性规划问题的Mehrotra型预估-矫正内点算法,并证明了该算法的迭代复杂性是O((√)nL).数值实验结果验证了算法的有效性. 相似文献