解凸规划问题的一种半内点法

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:Manjay
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
1984年,Karmarkar提出求解线性规划的新方法称为内点法,并证明该方法不但具有多项式复杂性,而且实际计算对大规模线性规划问题的效果优于单纯形方法.该算法发表后,掀起研究内点法的热潮.但是内点法要求解集有界性和对数障碍函数的一致凸性,为此冯果忱、于波、林正华提出了利用牛顿同伦和不动点同伦组合的组合同伦内点法,该算法对凸规划问题取消了解集有界性和对数障碍函数的一致凸性并且可以求解非凸规划问题,并在一定条件下证明了同伦路径的存在性和收敛性.但是组合同伦内点法需要可行内点作为初始点. 最近,于波、商玉凤提出动边界组合同伦算法,该算法取消了初始点必须为内点的限制,并能够求解更广泛的非凸规划问题.由于动边界组合同伦路径有可能从可行域外部趋近最优解,近似计算可能使得最后得到的近似解不满足约束条件,对很多实际问题不能满足要求.本文我们给出一种改进的动边界组合同伦算法,使得同伦路径对任意初始点,同伦路径的后半段都在可行域的内部,这样可以通过数值跟踪同伦路径得到在可行域内的近似解.我们给出同伦路径的存在性和收敛性证明,并通过数值实验验证新算法的有效性.
其他文献
随着随机微分方程的一般理论只是最近才发展起来的,它的非线民生情况始于上个世纪九十年代初,由Pardoux和Peng引入了一般形式的倒向随机微分方程并在Lipschitz条件下证明了适应
学位
基于身份的密码体制一直是公钥密码学中的研究热点。现存的大多数基于身份的加密与签名方案都是采用双线性对的,双线性对不仅运算非常耗时,大大降低了方案的效率,而且在如今量子
在全球经济一体化发展的市场环境中,企业的持续发展离不开高素质的人才队伍和科学高效的人力资源管理.而国有企业更应起带头的模范作用,革新管理理念,“科学发展观”为指导,
现代组合投资理论是关于在收益不确定条件下投资行为的理论,它是由美国经济学家马柯维茨在1952年首先提出的。此后人们做了不懈的研究,将该理论进行推广、改进、发展和完善。