论文部分内容阅读
单纯形算法和内点算法是线性规划的经典算法,虽然线性规划单纯形算法在实际应用中是一种高效的方法,然而在理论上它并不是多项式算法,因而吸引了无数学者去试图设计线性规划的多项式算法.1978年,L.G.Khachiyan提出了第一个多项式算法——椭球算法.1984年N.Karmarkar提出了线性规划的一种新的多项式算法.与单纯形算法沿着可行区域的边界寻优不同,Karmarkar算法是建立在单纯形结构之上的,它是从初始内点出发,沿着最速下降方向,从可行区域内部逐渐走向最优解,因此Karmarkar算法又被称为内点算法,自从Karmarkar划时代的论文发表以来,内点算法一直是数学规划领域一个非常活跃的研究方向.
但是内点算法必须从问题的可行域的内部出发,并且在迭代过程中通过适当的线性搜索来保证迭代点的非负性,这就给算法的启动带来了一定的困难.近年来提出了一类非内点算法一光滑算法,其中研究得最多的是非内点路径跟踪算法,这类算法中引入了光滑函数,利用光滑函数的性质,算法过程中不必要保证迭代点的非负性,但最后得到的最优解能自动保证非负.
本文致力于预估校正光滑算法的研究,提出了凸二次规划的预估校正算法.算法中首先将问题的中心线条件改造为一个非线性方程组,然后对它应用牛顿法,这样光滑算法避免了不等式约束而且算法中的迭代点也不必保证大于零,给算法的启动性带来了极大的便利.对于本文中的算法,我们证明了它的全局收敛性和局部二次收敛性.并用MATLAB编程进行了数值实验,数值结果表明本文提出的算法在实际应用中有一定的优越性.