论文部分内容阅读
自从Karmarkar在1984年提出了求解线性规划问题的多项式时间内点算法:一个里程碑性的工作,由于对大规模优化问题求解的有效性及在多领域的应用使得内点算法成为数学规划最活跃的研究领域之一.大步校正方法和小步校正方法是两类重要的多项式时间内点算法.在理论上,基于经典对数障碍函数小步校正方法的理论复杂性以√n优越于大步校正方法,其中n是问题的不等式约束个数.但是在实践中,大步校正方法的实现远比小步校正方法有效.这就是所谓的内点算法的不合理性(IronyofInterior-PointMethods)问题.
本文介绍一类新的基于Non-Self-Regular核函数半正定规划问题的原始-对偶内点算法而且减小了大步校正方法在理论与实践之间的间隙(Gap).由Non-Self-Regular核函数构造新障碍函数,并用新障碍函数代替经典对数障碍函数.分析显示新障碍函数不仅可以定义搜索方向而且可以控制内迭代的过程.和Self-Regular核函数相比,Non-Self-Regular核函数缺少了强凸性.为了克服这个困难,作者根据新障碍函数的性质,介绍了新的分析工具来分析算法的复杂性.并成功地应用到半正定规划的原始-对偶内点算法的复杂性分析中,相比中基于Self-Regular核函数的分析,作者的分析方法是简单和直观的.最后,分别得出迄今为止关于半正定规划问题的大步校正和小步校正原始-对偶内点算法的最好理论迭代界为:O(√nlogn)logn/ε和O(√n)logn/ε.
完成半正定规划问题的原始-对偶内点算法的设计和复杂性分析后,作者又转向研究二次锥规划问题的原始-对偶内点算法.类似在半正定规划中的设计和分析方法,用障碍函数代替经典对数障碍函数并介绍新的分析工具.最后,成功地应用到二次锥规划的原始-对偶内点算法的设计和复杂性分析中,得到迄今为止关于二次锥规划问题的大步校正和小步校正原始-对偶内点算法的最好理论迭代界为:O(√NlogN)logN/ε和O(√N)logN/ε.
综上所述,本文分别设计和分析了关于半正定规划及二次锥规划的原始-对偶内点算法.新的算法不仅缩小了大步校正原始-对偶内点算法在理论与实践之间的间隙(Gap),而且分别得出迄今为止关于半正定规划及二次锥规划的大步校正和小步校正原始-对偶内点算法的最好理论迭代界.数值试验结果亦表明基于Non-Self-Regular核函数的半正定规划和二次锥规划的原始-对偶内点算法是非常有效的.
全文安排如下:第一章,引言;第二章,新核函数;第三章,基于新核函数的半正定规划的原始-对偶内点算法;第四章,基于新核函数的二次锥规划的原始-对偶内点算法;最后,在第五章,总结了本文的研究成果及今后研究课题的展望.